ハノイの塔のはなし - memotic forgotten

せっかくなので、ハノイの塔の最短解について調べてみました。案外簡単ですね。厳密さとかには難があると思うけれど、まぁ気にしないでほしいのです。

元ネタ

wikipedia:ハノイの塔
100年ほど前に作られた話なのに、なぜか伝説という形になっている。なぜでしょう。とにかく、次のような話だ。

神様がお坊さんに言いました。
「ここに三本の棒があって、そのうち一本には六十四枚の円盤が刺さっている。この円盤を一枚ずつ動かして、すべてを別の棒に移しなさい。それが終わったら、この世界は消滅するだろう」

かなり端折ったが、だいたいこんな話だ。もう少しルールを細かく説明する。

大きいものを下に、小さいものを上にして刺さっている円盤を動かして、六十四枚をすっかり同じように別の棒に移動させたい。また、その過程のどの段階でも、大きい円盤を小さい円盤の上にのせてはならない。それと、円盤は一枚ずつしか動かしてはならないから、棒の一番上以外の円盤を動かすことはできない。さて、最短でどのくらい時間がかかるか。

どうしてそんなことで世界を消滅させなければならないのかは謎だが、とにかくこういう問題である。

例

例えば、円盤が3枚だったら最短手数は7手だ。説明するのは難しいが、実際に紙に書いてやってみると簡単だと思う。4枚だと15手のようだ。さて、円盤の枚数がn枚の場合の最短手数 $a_n$ を計算したい、という話である。

解説

円盤がn枚の場合の最短手数を $a_n$ とする。
円盤が(n+1)枚の場合の手順は、最初の棒をA,残りをB,Cとすると、

n枚を棒Bに移動する
一番下の円盤を棒Cに移動する
棒Bから棒Cにn枚を移動する

という3ステップにわけられる(ただしnは1以上)。このうち、ステップ1と3は円盤がn枚のハノイの塔を解くことに他ならないわけで、これらの最短手数はともに $a_n$ である。また、ステップ2はどう考えても1手より短くはできない。つまり、(n+1)枚の場合の最短手数 $a_{n+1}$ と $a_n$ の間には、
$a_{n+1}=2a_n+1$
という関係が成立する。あとは漸化式を解くだけ。
$a_{n+1}+1=2(a_n+1)$
$%5Ctherefore a_n+1=2^{n-1}(a_1+1)$
$a_1=1$ より
$a_n+1=2^n$
$a_n=2^n-1$
つまり、円盤がn枚の場合の最短手数は $2^n-1$ である。

もっと小さくなるか

さて、これ未満の手数で解ける可能性はあるだろうか。漸化式を解く過程に問題はないのだから、問題があるとすれば

n枚を棒Bに移動する
一番下の円盤を棒Cに移動する
棒Bから棒Cにn枚を移動する

以外に手順が存在する可能性だけである。
ステップ2には問題はないだろう。一番下の円盤は必ず移動させなければならない。
ステップ1は、「一番上以外の円盤を動かしてはならない」というルールから、ステップ2の前にはそれ以外のn枚の円盤をすべて棒Bに移動しなければならないので確実に必要である。
ステップ3は、移動させた一番下の円盤の上に残りのn枚を乗せなければならないので必要である。
なお、ステップ1と3で、n枚を完全に移動させなければならない(適当にどけておくだけではいけない)のは、棒が3本しかないことから明らかである(どけておく場所が1本しかない)*1。
ということで、これ以外に手順は存在しない。よって、n枚の場合の最短手数は $2^n-1$ より小さくなることはない。

ところで

円盤が64枚ある場合、最短手数は18446744073709551615手である。なあんだ、たったそれだけか*2。熱的死は近いぞ。

*1:しかし、棒が4本以上ある場合はこの限りではない、かもしれない

*2:毎秒一手とすると、およそ六千億年で完了する。