ハノイの塔は、数学的にもいろいろと考察されているパズルです。前回は、解き方のコツについて解説しました。ここでは、漸化式や最短手数などの数学的要素、歴史についてを解説します。64枚の時は世界滅亡というキーワードについても解説します。
ハノイの塔の漸化式の求め方
ハノイの塔の漸化式は、意外と簡単に求めることができます。
段数をnとして、解くのに必要な手数をAnとします。
[1]まず、段数が1枚の時は手数は明らかに1なので、A1=1が求まります。 [2]次に、n段の時の手数Anを考えます。n段の時、まず、n-1段をひとつの棒に移す必要があります。これはn-1段の時の手順An-1にほかなりません。
そのあと、一番下の円盤を余った棒に移すのに1回使います。
ついで、n-1段を一番大きな円盤に乗せるために再度n-1段の手順が必要です。
よって、An=An-1+1+An-1。これを変形してAn=2An-1+1
さらに両辺に1を足すと、An+1=2An-1+2=2(An-1+1)
つまり、An+1という数列は、公比が２で、初項はA1+1=2です。（A1=1は[1]で求めたものを使う）
あとはこれを数式に直せば、An+1=2^n、1を移動して
An=2^n-1とわかります。
ハノイの塔の最短手数
最短でどれくらいの手数が必要なのでしょうか？
これは上で求めた数列から求めることができます。
漸化式のnに、段数を代入したものが最短手数になるので、1段の時は1、2段の時は3、3段の時は7・・・となります。ようするには2の累乗（倍々ゲーム）から1引いたものです。
まとめると以下の表のようになります。
| 段数 | 最短手数 |
| １ | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
倍々ゲームよろしく、最初はたいして増えないように見えて、だんだんと爆発的に増加していくというパターンなのがわかります。
64枚のハノイの塔で世界滅亡？ハノイの塔の歴史
ハノイの塔について調べていると、64という数字や、世界滅亡というキーワードが見つかります。
これは、最初にハノイの塔が発売されたときの、説明書に書かれたおとぎ話が元になっています。
上の図およびサムネイルは19世紀末に発売されたオリジナルのハノイの塔のパッケージです。西洋人によるヘンテコアジア観っぽい絵のようにも見えます。
もとはフランスの数学者リュカが考案したものなので、原語はフランス語です。
インドのガンジス河の畔のヴァラナシに、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。
翻訳は日本語版wikipediaより
64段のハノイの塔を実際に動かす場合は、最短手数は1844京6744兆737億955万1615回となり、これは1回を1秒で動かすとして約5845億年もかかります。
宇宙が始まって138億年ですから、たしかに世界が滅亡してもおかしくはありません。
これはおそらくハノイの塔を制作した数学者リュカによる創造上のお話でしょう。ただし、手数が膨大になることを使ったうまい空想であることには変わりありません。
まとめ
- ハノイの塔は、前の段数を解くのに必要な手数をかんがえることで、漸化式を求めることができる。
- 倍々ゲームから1を引いたものが最短手数。
- 64枚で世界が滅亡するというのは、最初に発売された時のおとぎばなしが元ネタ。
仮に人間が移動するとして、現実的にパズルとしてできそうなのは10段（最短で1023回動かす）くらいまでじゃないでしょうか。
