世界の終焉とハノイの塔

 ハノイの塔

ハノイの塔が完成すると世界が終焉を迎えると言われています。

インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し変えのルールが後述）。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。 

ハノイの塔のルール

下記の画像のように、３本の棒があり、大きさの異なる円盤が大きい順に、１本の棒に積み重ねられています。

これを下記のルールを守った上で他の棒に移し替えていきます。

1. 大きい円盤の上に小さい円盤を積む（小さい円盤の上に大きい円盤はおけない）
2. 一度に移動できる円盤は１つだけ
3. ３本の棒以外の場所に円盤を置くことはできない。
4. 一番右の棒に円盤を全て移す。

簡単な例題

円盤が1個の場合は、単純にそれを1回移動するだけで終わります。

なので円盤が２個の場合を考えましょう。

・初期状態

・１回目の移動

・2回目の移動

・3回目の移動

簡単に終わってしまいましたが雰囲気は理解できたでしょうか。

移動回数は3回です。

次には円盤を3個にしてみましょう。

円盤3個の問題

この手の問題は、数を少しずつ増やしていくと規則性が見えてきます。

・初期状態

・1回目

・2回目

・3回目

・4回目

・5回目

・6回目

ここまで来ると、実は円盤が2個の時の問題と全く同じ条件になっています。

円盤2個の問題では3回の移動で終了しています。

円盤3個の問題で6回目においては、「2つの円盤を移動する問題」としてみることができます。

この段階では「緑と青の2個の円盤を移動する問題」となっています。赤の円盤は一番大きいので、これが移動できた時点で、1個円盤が少ない問題の結果をそのまま流用できます。

従って、移動回数は6回＋3回で9回となります。

待ってください、本当にこれで良いのでしょうか。もっと早い方法は無かったのでしょうか？最初の青色の円盤を移動する際には、真ん中か右か、選択肢が2つあります。さっきとは違い方を選んで今一度試してみましょう。

・初期状態

・1回目

・２回目

・3回目

・4回目

案の定もっと早く終わりました。ここまでこれば円盤2つの方法で移動ができますので、従って円盤3つですと4回＋3回＝7回で移動ができると分かりました。これより早い方法はありません。他のパターンも試してみてください。

しかし、これ以上数が増えてくると、自力で探しだすのは難しそうです。

規則性をみる

これから円盤の個数が個としたときの、最小の移動回数をと書きます。現在のところについて調べましたから

ということが分かっています。ハノイの塔の実際の問題はですから、が知りたい値です。果てしなく遠いです。ここはの値に当たりをつけて、の値を予想したいところです。

という関係性があるように見えます。すると

となるのでしょうか。たった3つのデータだけからこの規則だと断定するのは早計です。

論理的に考える

私達は3個の円盤を移動するときに、以下の段階まで辿り着けば、2個の円盤を移動する問題に帰着されることを見ました。

一方で、その直前の状態はどうでしょうか。赤を移動し終わる前の状態です。

さて、初期状態からこの状態に至るまでのことを考えてみると、これも「2個の円盤を移動する問題」と見ることができます。ただし、一番右の円盤に赤色を置きたいので、（真ん中に）2個の円盤を移す問題です。そのように捉えようとも、右の棒を中継地点として捉えれば、移動回数自体に影響を及ぼすものではありません。

つまりまとめると、3つの円盤を移動する際には、以下の初期状態から、

2つの円盤を（真ん中の棒に）移動する操作を行い（回移動）、

赤色の円盤を右側に移動し（回移動）

再度2つの円盤を（右側の棒に）移動する操作を行い（回移動）、

合わせて回の操作によって移動が完了します。

これは円盤の数が個であっても同じです。真ん中の棒に、一番下以外の個の円盤を回の操作を用いて移動し、回の操作で最大の円盤を右側に移動し、回の操作で真ん中に積まれた円盤を右側に移動します。

従って、

だと結論付けることができます。もしかしたらこれより早い方法を誰かが見つけるかもしれません。しかし、というのは個の円盤を移動する最小の移動方法です。

今、操作を追って来た通り、一番下の円盤を一番右側に移動するためには、その他の円盤が全て真ん中になければならず、最大の円盤を除く全ての円盤が真ん中の棒にあるためには、それが大きい順に積まれていなければなりません。

円盤個ならば最初に個を移動しなければならないというのは絶対であり、は個をルールに従い移動させる最小の回数であり（それが具体的に何回かは知らなくとも）これより早い方法はありません。（棒が4本ならば、必ずしも個を順番通りに並べる必要がないため、の手数が不要になるでしょう）

世界の終焉はいつくるのか

漸化式として表現

について知りたければ、以下の漸化式を解く必要があります。そのあとを代入することで世界の終焉がいつ来るのか分かります。

    （は自然数）

非常に単純な形の漸化式なので以下のような変形で等比数列に持っていけます。

漸化式の解法

としてしまえば、と置くことで等比数列にできます。これを見計らって、

と置いてしまいます。（ここ実際にはとしたいので、を右辺に集めることでと変形し、 と比較したところでだと求めます）

初項2、公比2の等比数列ですから

と求まり、と分かりました。

世界の終焉

従って64個の円盤の移動回数は 

回

（1844京6744兆737億955万1615回）

です。一枚の移動に１秒掛かったと考えると、約5,845億年です。

しばらく世界の終焉はこなさそうです。

参考文献 

プログラマーならよく知る「ドナルド・E.クヌース」が自画自賛した書籍「CONCRETE MATHEMATICS」の日本語版「コンピュータの数学」（何だこの訳は）には上記のような面白い問題から始まり、離散数学の大部分がカバーされています。

コンピュータの数学