Hatena::ブログ(Diary)

げっかんにっき このページをアンテナに追加 RSSフィード

伺かゴースト「レチハルカ」等の更新記録と
鉄道旅行記と、列車コンセント情報がメインの日記です。
伺かゴーストって何? という方は外部解説サイトも御覧下さい。


本体サイト

ゴーストダウンロード

伺か最萌トーナメント終了

2007年7月7日(土) コピー制限はやっぱり嫌い

コピー子孫問題

| 00:15 |  コピー子孫問題を含むブックマーク  コピー子孫問題のブックマークコメント

画質は良く、ゴーストも起きず、音もCD並みという地上デジタル放送。

新しいテレビを買うなら、やっぱり地デジで視聴したいものです。


しかし、綺麗なバラにはトゲがある、の言葉の通り、地デジにもトゲがあります。

業界が身を守るために視聴者に向けた、鋭いトゲが。

それが、コピーワンス制限です。


ご存知の通り、地デジの映像音声は、デジタル信号です。

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


1回だけですよ。1回

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


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


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


デジタル放送番組、コピー9回までOK…総務省が要請へ

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

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}


というわけで、ようやく結論にたどりつきました。


f(n)=2^{n}


つまり、n回コピー可能な親DVD1枚から、最終的には2^{n}枚のコピーDVDが出来るということがわかりました。

ここで最初の問題を見てみましょう。


9回のコピーが可能なDVDが1枚あります。

これを親としてDVDを複製していくとき、同じ内容のDVDを最大何枚作ることができますか。

(親DVDを複製した子DVDをさらに複製して、孫DVDを作ることもできるとします。)


つまり、この問題では、n=9のときのf(n)を求めなさい、と言ってるわけです。したがって、


f(9)=2^{9}=512


が答えになります。512枚。

多いんだか、少ないんだか…。


閑話休題

ついさっきまで、2^9=128とか書いてました。

こういうのを、「画竜点睛を欠く」といいます。

いい勉強になりましたね!

コピー子孫問題 追記

| 06:16 |  コピー子孫問題 追記を含むブックマーク  コピー子孫問題 追記のブックマークコメント

上のコピー孫問題で、<9>について矢印グラフなんか描きたくないよね! って書いたわけですが、せっかくなので描いてみました。おそろしくでかいので、見てみたい方は続きを読むをクリック。


<9>→<8>→<7>→<6>→<5>→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   │   │   └→<0>
 │   │   │   │   │   │   ├→<1>→<0>
 │   │   │   │   │   │   └→<0>
 │   │   │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   │   │   └→<0>
 │   │   │   │   │   └→<1>→<0>
 │   │   │   │   │        └→<0>
 │   │   │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   │   │   └→<0>
 │   │   │   │   │   ├→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   │   └→<0>
 │   │   │   │   │   ├→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<5>→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   │   └→<0>
 │   │   │   │   │   ├→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   └→<1>→<0>
 │   │   │   │        └→<0>
 │   │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<6>→<5>→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   │   └→<0>
 │   │   │   │   │   ├→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0> 
 │   │   └→<0>
 │   ├→<5>→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<3>→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<2>→<1>→<0>
 │   │   └→<0>
 │   ├→<1>→<0>
 │   └→<0>
 ├→<7>→<6>→<5>→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   │   └→<0>
 │   │   │   │   │   ├→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<5>→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<3>→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<2>→<1>→<0>
 │   │   └→<0>
 │   ├→<1>→<0>
 │   └→<0>
 ├→<6>→<5>→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   │   └→<0>
 │   │   │   │   ├→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<3>→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<2>→<1>→<0>
 │   │   └→<0>
 │   ├→<1>→<0> 
 │   └→<0>               
 ├→<5>→<4>→<3>→<2>→<1>→<0>
 │   │   │   │   └→<0>
 │   │   │   ├→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<3>→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<2>→<1>→<0>
 │   │   └→<0>
 │   ├→<1>→<0>
 │   └→<0>
 ├→<4>→<3>→<2>→<1>→<0>
 │   │   │   └→<0>
 │   │   ├→<1>→<0>
 │   │   └→<0>
 │   ├→<2>→<1>→<0>
 │   │   └→<0>
 │   ├→<1>→<0>
 │   └→<0>
 ├→<3>→<2>→<1>→<0>
 │   │   └→<0>
 │   ├→<1>→<0>
 │   └→<0>
 ├→<2>→<1>→<0>
 │   └→<0>
 ├→<1>→<0>
 └→<0>

…んー。なんていうか、なんだろう、この感覚。

徒労?

コピー子孫問題 追記2

| 06:39 |  コピー子孫問題 追記2を含むブックマーク  コピー子孫問題 追記2のブックマークコメント

id:ponapalt:20070708:1183843159

天才が! 天才がいるよ!

コピー子孫問題 追記3

| 08:44 |  コピー子孫問題 追記3を含むブックマーク  コピー子孫問題 追記3のブックマークコメント

もうひとつ、コピー子孫問題に関する問題を。

9回のコピーが可能なDVDが1枚あります。

これを親としてDVDを複製していくとき、同じ内容のDVDを最大2^{9}枚作ることができます。

さて、2^{9}枚のコピーDVDを作るとき、コピー操作は何回必要になりますか。

(親DVDを複製した子DVDをさらに複製して、孫DVDを作ることもできるとします)

これ、簡単ですね。

最初は親DVDが1枚だけあります。

最後は、親DVDも含めて512枚のDVDがあります。

1回コピーするごとに、DVDは1枚増えます。

すなわち、コピー操作は、

2^{9}-1=512-1=511

必要になります。


では類題。

100チームが参加して、野球のトーナメント選をおこない、優勝チームを決めます。

引き分け再試合が1試合もないとき、全部で何試合が行われますか。

 

*1:一次録画デバイス(HDDレコーダーなど)から、DVDなどに1回だけダビングできる制限。

zizizizi 2007/07/08 00:23 ぼくは2の10じょうを1024(つまり2^9=512)とおぼえているのですが、おにいさんのくにではちがうですか?

hinoharuhinoharu 2007/07/08 00:24 あっははははは! 修正しました。なんでこうなったんだろう…。

トラックバック - http://d.hatena.ne.jp/hinoharu/20070707
638075
この日記のはてなブックマーク数