6 付録

これは重要な話ではあるが，これを講義で述べると寝てしまう(思考が停止する)者が多数 でそうである．興味のある者は，ここの付録をしっかり学習せよ．大学への編入試験問題 では，この程度の問題は出題される．

6.1 ハノイの塔の円盤の移動回数

図3に示したように，円盤が3枚の場合，円盤の移動回数は7回であった． 仮に，インドの坊主が1秒間に1枚の円盤を移動させているとすると，わずか7秒で世界の 終わりを迎えることになる．幸いなことに，円盤は64枚あり，もう少し世界の寿命は長そ うである．それでは，世界の寿命はどの程度であろうか?．

$n$ 枚の時の円盤の移動回数$f_n$ は、

$$f_n=f_{n-1}+1+f_{n-1}$$ (8)

となる。リスト3の関数move()を1回呼び出すと、必ず円盤の移動が 一回発生する。加えて、$n-1$ 枚の呼び出しを2回行っているからである。この式を変形す ると、

$$f_{n}+1=2(f_{n-1}+1)$$ (9)

となる。これは等比数列なので、一般項は簡単に求められる。$f_1=1$ なので、

$$f_n+1=2\times 2^{n-1}$$ (10)

となる。したがって、円盤の移動回数$f_n$ は、

$$f_n=2^n-1$$ (11)

と表すことができる。

$n=64$ のときの，移動回数は18446744073709551615回である．世界の終焉は，

$$18446744073709551615 =2.13504\times 10^{14} =5.89492\times 10^{11}$$

となる．5千8百億年後と言うことである．現在の宇宙の年齢は，およそ150憶年と言われ ていることを考えると，これは長すぎるように感じる．

エドゥアール・リュカも少し間違えたようで，円盤の数を60枚程度にしておけば，世界の 寿命は365臆年となり，いい線をいっているように気がする⁴．どちらにしても，世界の終わりなんか分から ないから，どうでも良いか．いつか，物理学が進歩して世界の終わりが予想できたならば，イン ドの坊主の仕事と比べてみたいものである．

ホームページ: Yamamoto's laboratory
著者: 山本昌志