世界滅亡まであと何秒？【ハノイの塔】

ハノイの塔とは？

ハノイの塔とは、3本の棒のうち、いずれか1本の棒に64枚の円盤を下から大きい順にさした状態をスタートとし、他の棒へ全て移動させるパズルです。

　　

ルールは簡単。

・小さい円盤の上に大きい円盤を載せるのはNG。

・一回の移動で移動させれるのは1枚の円盤のみ。(同時に2枚以上は持てない。)

・全ての円盤を最初とは違う棒に移動させれたらクリア。

円盤が2枚のときを考える

説明のためにm番目に小さい円盤を$A_m$と呼ぶ。

円盤が2枚しかない時は簡単で、

①$A_1$を移動させる。

②$A_2$を$A_1$とは別の棒に移動させる。

③$A_1$を$A_2$の上におく。

よって円盤が2枚の時は3手でクリアすることができる。

漸化式を作る

では次に、円盤がn枚の時必要な手数を$a_n$とした時、円盤n+1枚では何手必要なのかを調べる。

n+1枚の円盤を移動させるには、

①$A_1$〜$A_n$の円盤を移動させる。

②$A_{n+1}$を$A_1$〜$A_n$とは別の棒に移動させる。

③$A_1$〜$A_n$を$A_{n+1}$の上に移動させる。

の手順でクリアすることができる。

ここで①・③には$a_n$手かかり、②は1手ですむので$a_{n+1}$は次のように表せる。

$$a_{n+1}=2a_n+1$$

一般項を求める

以上のことから、次の漸化式を解くことになる。

$$\left\{\begin{array}{l}a_{n+1}=2a_n+1\\a_2=3\end{array}\right.$$

これはごく一般的な漸化式なので等比数列型に帰着させて解きます。

漸化式$a_{n+1}=2a_n+1$は次のように変形出来ます。

$$a_{n+1}+1=2(a_n+1)$$

よって数列$a_n+1$は2項目が4、公比が2の等差数列なので、

$$a_n+1=2^n$$

つまり、

$$a_n=2^n-1$$

ハノイの塔は1兆年かかる！？

実際のハノイの塔は64段なので、n=64を代入すると、おおよそ$2^{64}$手必要なことになります。これは1秒間に1手行っても役1兆年かかるほどです。

我々が生きている間は当分大丈夫そうですね。（笑）

今回はハノイの塔について考えてみました。いかがだったでしょうか。数列はうまく使えば遥か先の未来のことを予想できる単元なので少しでも興味を持っていただけたら幸いです。