コピー子孫問題 - げっかんにっき

画質は良く、ゴーストも起きず、音もCD並みという地上デジタル放送。
新しいテレビを買うなら、やっぱり地デジで視聴したいものです。

しかし、綺麗なバラにはトゲがある、の言葉の通り、地デジにもトゲがあります。
業界が身を守るために視聴者に向けた、鋭いトゲが。
それが、コピーワンス制限です。

ご存知の通り、地デジの映像音声は、デジタル信号です。
デジタル信号は何度コピーしても劣化しないため、無制限のコピーを許すと、世の中に「モノホンと全く同じ」海賊版が出回ってしまうおそれがある。そうなったら商売あがったりだな！という論理です。そのため、日本の地上デジタル放送番組にはすべて、コピーを1世代のみ許可するというコピーワンス制限*1が掛けられています。

1回だけですよ。1回。
もしHDDからDVDへのダビングが失敗してしまったら（DVDの焼き不良なんて珍しいことじゃありません）、もうHDDから取り出すことができません。HDDに永遠に残すか、消すかの2択です。なんということでしょう！

コンテンツを作ってお金を稼ぐ側からすれば、こうでもしないと安心できないのでしょうが、善良な視聴者からすれば面倒なだけの制限です。これだけでもう、「地デジ…うーん、ちょっとなぁー」と感じる人もいるんじゃないかと思います。

さて、昨6日に総務省がとある方針転換を発表しました。

デジタル放送番組、コピー９回までＯＫ…総務省が要請へ
デジタル放送のテレビ番組をＤＶＤレコーダーに１回しか録画できないよう、特殊な信号を使って制限している「コピーワンス」について、総務省は６日、ＤＶＤなどに９回までのダビングを認めるよう、放送局などに要請する方針を明らかにした。
Yomiuri Online

まあ、前よりは使いやすくなるのかなあ、というところでしょうか。
「自滅遺伝子」テロメアが短くなっていくように、ダビングをするごとに回数ビットが減っていく…というようなシステムをHDDレコーダに実装しなければならないので、既存の機器では相変わらずコピーワンス制限がかかるそうです。

ところで、私が言いたかったのは、コピー制限の是非を論じることでも、不便に文句を言うことでもありません。ここで問題です。

9回のコピーが可能なDVDが1枚あります。
これを親としてDVDを複製していくとき、同じ内容のDVDを最大何枚作ることができますか。
（親DVDを複製した子DVDをさらに複製して、孫DVDを作ることもできるとします）

解答編に続きます。

（上の読売記事を読むと書いてありますが、かりに9回までコピーできるようにしたとしても、HDDレコーダから作成した子DVDをさらにコピーして孫DVDを作ることは、これまで通り禁止されるようです。したがって、この問題の条件は架空のものです。誤解のなきよう。）

解答編

まずは、考え方から。

1枚のDVDを9回コピーできるんだから、なんとなく、おそろしい数のコピーDVDが出来そうな気もします。そうすると、えーっと、9の階乗？それとも、9の9乗かな。そうすると387,420,489枚ですか。うわあ、凄い。
…ちょっと待ってください。そうはならないことはわかりますね。
1回コピーしたDVDは、そのあと9回コピーすることはできません。8回です。
あと8回コピーできるDVDをコピーして出来たDVDは、あと7回しかコピーできません。
そう考えると、案外早くすべてのDVDが「もうコピーできないDVD」になりそうな気がしてきます。

まずは実際の例で考えてみることにしましょう。
実際の問題では、9回までコピーをすることができますが、ここは簡単にするために、0回コピー可能なDVDを考えます。
0回コピー可能なDVDは、もうそれ以上コピーすることはできません。
つまり、0回コピー可能なDVDが1枚あったら、どんなにがんばっても1枚のDVDのままです。
このことを、

$f(0) = 1$

と表すことにします。
この関数 $f(n)$ は、コピー可能な回数 $n$ から、最終的なDVDの枚数を求める関数です。

次に、1回コピー可能なDVDを考えてみます。
1回コピー可能なDVDは、1回コピーすると、もう二度とコピーすることはできなくなります。そして、やはりもうコピーできない子DVDが1枚できます。
つまり、矢印グラフを描いてみると、こういうことになる。

<1>→<0>

この図は、1回コピー可能なDVD（<1>）から、0回コピー可能なDVD（<0>）が作られたことを表しています。<1>は1度コピーされてしまったことで、もうコピーできなくなっています。（この図からは直接それを読みとることができませんが、ブラケット内の数字と、数字から出ている矢印の数を比較することで、それとわかります。）

一方で、さっきの関数 $f$ を使うと、こう書けます。

$f(1)=2$

さて、次です。
2回コピー可能なDVDについても同じように考えてみましょう。
まずは矢印グラフ。

<2>→<1>→<0>
 └→<0>

1回コピー可能なときと違って、一本線のグラフにはなりません。
2回コピー可能なDVDは、2回コピーが出来るからです。（当たり前か）
ただ、1回目にコピーしたDVDは、さらにもう一度コピーができますが、2回目にコピーしたDVDは、もうそれ以上コピーすることはできません。（なぜなら、「あと1回しかコピーできないDVD」をコピーしたものだから。）
というわけで、これで全部です。4枚まで増えましたね。

$f(2)=4$

なんとなく、わかってきたような気がしますね。

さて、3回コピー可能なDVDの場合です。
このへんから、矢印グラフを描くのが面倒になってきます。

<3>→<2>→<1>→<0>
 │   └→<0>
 ├→<1>→<0>
 └→<0>

$f(3)=8$

…んー？
よく見れば、これで全てだというのはわかります。
しかし、このグラフを、<9>について描くなんて、ごめんですよね。
少なくとも私はいやです。
さーて、どうしよう。

グラフをよく見てみよう

…む、ちょっと待てよ？

<3>→<2>→<1>→<0>
 │   └→<0>
 ├→<1>→<0>
 └→<0>

この赤い部分をよく見ると、さっき「2回コピー可能な場合」に出てきた、

<2>→<1>→<0>
 └→<0>

と似ています。っていうか、全く同じですね。 $f$ を使って書くと、 $f(2)=4$ です。
さらに、

<3>→<2>→<1>→<0>
 │   └→<0>
 ├→<1>→<0>
 └→<0>

この緑の部分はやっぱり、「1回コピー可能な場合」に出てきた

<1>→<0>

と全く同じです。つまり、 $f(1)=2$ 。

<3>→<2>→<1>→<0>
 │   └→<0>
 ├→<1>→<0>
 └→<0>

そうすると、この青い<0>も、「0回コピー可能な場合」の「どんなにがんばっても1枚」と見ることができそうです。 $f(0)=1$ ですね。
俄然面白くなってきたでしょう。

<3>→<2>→<1>→<0>
 │   └→<0>
 ├→<1>→<0>
 └→<0>

この図からわかることは、
3回コピー可能なDVDからできるコピーDVDの枚数は、

　2回コピー可能なDVDからできるコピーDVDの枚数（4枚）
＋1回コピー可能なDVDからできるコピーDVDの枚数（2枚）
＋0回コピー可能なDVDからできるコピーDVDの枚数（どんなにがんばっても1枚のまま）
＋1（親DVD自身のなれのはて）

で求められるということです。

よく考えてみれば、この足し算で正しいことがわかります。
3回コピー可能な親DVDを1回コピーすると、親DVDは2回コピー可能になり、同時に2回コピー可能なDVDが1枚できます。
2回コピー可能になった親DVDをさらに1回コピーすると、親DVDは1回コピー可能になり、同時に1回コピー可能なDVDが1枚できます。
1回コピー可能になった親DVDをさらに1回コピーすると、親DVDはこれ以上コピーすることはできません（なれのはて）。そして同時に、もうコピーできないDVDが1枚できます。

つまり、3回コピーできる親DVDは、「2回コピーできるDVD」「1回コピーできるDVD」「もうコピーできないDVD」を産んだのち、もうコピーできなくなるわけです。
…それって、つまり、さっきの式ですよね。

ここまで納得できましたか。
そしたら、あとはこれを数式にして、いじくってやりましょう。

数式って便利！

関数 $f$ は、コピー可能な回数から、最終的なDVDの枚数を求める関数でした。
この $f$ を使って、今の関係をわかりやすく表してやりましょう。

$f(3)=f(2)+f(1)+f(0)+1$

ということになります。もちろん、さっきと同じに色分けをするなら、f(2)+f(1)+f(0)+1 ということになりますよ。

ここで、一気に高い次元へとジャンプしてみましょう。
2回とか3回とか具体的な数をとびこして、 $n$ 回です。
たとえ何回になっても考え方は同じでいいので、

$f(n)=f(n-1)+f(n-2)+\cdots+f(1)+f(0)+1$

途中の「…」でだまされたような気分にならないでください。ホントにこう書くこともあるんです。

ただ、これだけでは、 $f(n)$ を求めるのに、 $f(0)$ から $f(n-1)$ までを全部求めなくていけません。はてしなく面倒ですよね。

とりあえず、 $f(n-1)$ がわかっている時に、 $f(n)$ を求める式を考えてみましょう。そのために、ちょっと細工をします。

$\begin{eqnarray}f(n)&=&f(n-1)+&f(n-2)+\cdots+f(1)+f(0)+1\\f(n-1)&=&&f(n-2)+\cdots+f(1)+f(0)+1\end{eqnarray}$

上の式から下の式を引いてみます。

$f(n)-f(n-1) = f(n-1)$

む。きれいさっぱり右の方が消えました。
ちょっと移項をかまして、

$\begin{eqnarray}f(n) &=& f(n-1) + f(n-1) \\ &=& 2 \times f(n-1) \end{eqnarray}$

ようやく $f(n)$ が正体を現しました。
この数列（関数と呼ぶより、数列の方がふさわしいですね） $f$ は、一つ前の数の倍となる数列です。ここまで来ればあとはもう一息。
$n$ から直接 $f(n)$ の数字を求められるようにしたいですね。
それが出来れば、 $n$ 回コピー可能な親DVD1枚から、最大 $f(n)$ 枚のコピーDVDが出来るぞ！と、堂々と宣言できます。

$f(n) = 2 \times f(n-1)$

ということは、

$f(n-1) = 2 \times f(n-2)$

ということです。上の式の右辺に、下の式の左辺を代入してみましょう。

$f(n) = 2 \times f(n-1) = 2 \times 2 \times f(n-2)$

$f(n-2)$ が出てきました。しかし、 $f(n-2)=2 \times f(n-3)$ なので、もう怖くありません。

$\begin{eqnarray}f(n) &=& 2 \times f(n-1) \\ &=& 2 \times 2 \times f(n-2) \\ &=& 2 \times 2 \times 2 \times f(n-3) \end{eqnarray}$

調子に乗って、 $n$ が0になるまで繰り返しちゃいましょう。

$\begin{eqnarray} f(n) &=& 2 \times f(n-1) \\ &=& 2 \times 2 \times f(n-2) \\ &=& \underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ times}} \times f(n-n) \\ &=& \underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ times}} \times f(0) \end{eqnarray}$

ついに、 $n$ が0になってしまいました。でも、ちょっと待ってください？
さっき、（だいぶ上の方になっちゃいましたが） $f(0)$ は1だったはずです。

$\begin{eqnarray}f(n) &=& \underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ times}} \times f(0) \\ &=& \underbrace{2 \times 2 \times \cdots \times2 }_{n \text{ times}} \times 1 \\ &=& 2^{n} \end{eqnarray}$