ハノイの塔（再掲+α）

以前にも話題にしたことがある（以下、一部重複）

これは「ハノイの塔」というパズルだ。数学的でありまた芸術的でもあるパズルだ。ルールは簡単。

ゴール：全部の円盤を右の塔に移す。
（１）１回に１枚ずつしか動かせない。
（２）大きな円盤を小さな円盤の上に置いてはいけない。

このゲームのWEB版がインターネットで見つかった。自由に使ってよいというので、自分のHPに置いた。遊んでいただきたい。

http://takashiyoshida.com/hanoi.html

このゲームから、いろいろなことを考えることができる。代表的なものは次の通り。

(１）円盤がn枚の時には円盤を最少で何回移動すればゴールにたとりつくか。
(2）任意のnにおいて（nがいかなる自然数の場合にも）n枚の時に最低の回数でゴールにたどりつく手順を示すプログラムをつくれ。

（１）については私程度でも何とか自分で問題が解ける。現在の「高校数学B」の「数列」を理解すれば解ける。
① n=1のときは１回、n=2 の時３回、n=3のときは7回・・・という経験則から、2^n-1（^は累乗を表す。すなわち 2を n 乗して 1引いた数）が最少移動回数。これを数学的帰納法を用いて証明すればよい。
②漸化式を使う方法もある。本当は、TeXを使って表したいのだが、面倒だし使い方を忘れたので、手書きで示す。



（2）については「再帰」という考え方で作るらしいが、頭がまわらない。
そこでもっと単純化する方法を考えた。
次のように動かせば、かならずゴールにたどりつける。
一番大きな円盤から順番に数字をつける。（１〜N）
（１）奇数番号の円盤は、左→右　右→中　中→左としか動かせない。
（２）偶数番号の円盤は、左→中　中→右　右→左としか動かせない。
（３）連続して同じ円盤を動かせない。

このパズルのルールと合わせると不思議なことに（？）、動かせる円盤は１枚に限定される。そしてそしてその限定された１枚を限定された位置に動かす。これを続けるとゴールにたどり着く。ゴールにたどり着くと動かせる盤がなくなる。これならプログラミングも簡単である。実は昔のBasic 言語で作っているのだが、Webで公開する方法がわからない。

しかしなぜ上のルールによるとゴールにたどりつくのか証明ができない。もちろんNが限定された数なら１０だろうと２０だろうと証明できるのだが。上のルールも経験則なのだ。

ところで、 2^n-1と簡単に書いたが、これは実はすごい数なのだ。
上で紹介した 　Web　上のプログラムでは、　n=8　まで実行することが可能である。
このとき最少移動回数は、 2^8-1＝255　である。1秒間1枚動かせるとすれば4分15秒。10枚くらいならなんとかなるだろう。しかし、それを過ぎるともう大変だ。ほぼ、２倍ずつ増えていくのである。計算は省略するが、32枚で人間の一生を超える時間になる。そして100枚となるとどうなるか。エクセルで  "=2^100-1 "と入力すると、 "1.26765E+30" と出力される。これは 1.26765の10^30倍という意味なので31桁の数字である。これは宇宙の歴史さえ超える数値であり「天文学的」を超える数値なのである。

こうやって考えてみると、人間の一生がいかに小さいものであるかがよくわかる。こんな簡単なゲームでも一生かかって30枚程度しか動かせないのである。囲碁や将棋が瞬く間にAIに席巻されたのも当然といえば当然のことである。