ハノイの塔

たま～に読む科学雑誌『Newton』2月号に載っていた、フランスの数学者エドワード・リュカが考えた、数学を使ったゲームです。

・ 3本の棒と、順々に大きくなる複数の円盤から成る。（円盤の中央には穴がある）
・スタートは3本のうちの1本に、すべての円盤が大→小の順に積み重ねられている。
・円盤は一度に一枚づつ、棒のどれかに移動させることができるが、小さな円盤の上に大きな円盤を乗せることは出来ない。

上記のルールに従って、すべての円盤を左右どちらかの立棒に移動させられれば完成。当然ですが、重ねる円盤の数が増えるほど難しくなります。雑誌では正月らしく鏡餅を使ってました。

最小の移動回数については法則性があり、“最小移動回数＝2のｎ乗-1”となります。
ｎは円盤の枚数で、円盤が3枚の場合は2の3乗（2ｘ2ｘ2）-1＝7となり、７回で移動できます。

伝説では“インドの世界の中心を表す聖堂というところに、大理石の柱3本と黄金の円盤64枚がある。そこではバラモン僧たちがハノイの塔と同じルールに則り、円盤の移し替えを行っている。そして、全ての円盤の移し替えが終わったときに、この世は終焉を迎える”のだとか。

この64枚を移動するためにはどのくらいかかるか？
公式に当てはめた答えを、１枚動かすのに１秒かかるとして、換算すると約5,850億年かかるそうです。移し終わる前にこの世の終焉を迎えちゃいそうな時間ですね。