今日は「クイズの日」「とんちの日」（今日は何の日？ 1月9日）ということなので、クイズとは違いますが、あるゲームを紹介します。
有名なので知っている方も多いと思いますが、「ハノイの塔」というゲームです。
こちらのサイトでやれますので、挑戦してみてください。　→　ミニゲーム（フラッシュ） ハノイの塔

どういうゲームかと言うと、
三本の杭と中央に穴のあいた、大きさの異なる円盤がある。
左端に積まれた円盤を右端の杭に移動させるゲームです。
ただし、以下のルールに従って移動させて下さい。
・一度に移動できるのは1つ
・（それより）小さい円盤の上に置いてはいけない（大きいものが下にならなくてはいけない）

たとえば、3段の場合。
杭を左からＡ，Ｂ，Ｃとして、3つの円盤を大きいものから大、中、小とすると。
小をＡからＣへ
中をＡからＢへ
小をＣからＢへ
大をＡからＣへ
小をＢからＡへ
中をＢからＣへ
小をＡからＣへ
という具合です。


さて、このハノイの塔ですが、何段でも解けることは、高校数学の知識で証明できます。
数学的帰納法という証明方法をとります。
まず、1段のとき、解けることは明らかです。
次に、「ｎ段のときに解ける」と仮定します。
この仮定の下で、ｎ+1段について考えます。
仮定から、上のｎ段はＡからＣへ移動できるのですから、それをＡからＢへ移動することも可能です。
すると、Ａには一番大きい円盤が一つだけ残りますから、それをＣへ移動させます。
そして、初めと同様に、Ｂにあるｎ段をＣへ移動させることは可能ですので、ｎ段で解けるならば、ｎ+1段でも解けることがわかります。
Ｑ．Ｅ．Ｄ

ちょっと待てという人のために補足すれば、
ｎ段のときに解けるならば、ｎ+1段でも解けるわけですから、
1段のときに解けるならば、2段でも解ける。
2段でも解けるなら3段でも。3段も解けるなら4段でも。・・・・・・・・
というように何段でも解けるということが証明できるわけです。


このハノイの塔を調べると面白いことがわかります。
毎日24時間ずっと1秒に1個ずつ移動させていくと、1年間で何段のハノイの塔が解けるでしょうか？
1秒間に1個は遅くないと思います。
考えてる時間もないのですから、むしろ速いです。
それを1年間、寝ないで、食事もしないで続けるんです。
100段くらいいけるんじゃないか？って思った人もいるでしょう。僕もです。

ですが、答えは24段です。
え？それだけ？って思いませんか？
僕は思いました。

ｎ段のハノイの塔を解くには最低2^ｎ -1回移動させる必要があります。
一年＝60×60×24×365＝31,536,000秒です。
一方、
2²⁴ -1＝16,777,215回
2²⁵ -1＝33,554,431回
となり、25段は1年以内に解くことはできません。

ちなみに100段のハノイの塔を解くには、1,267,650,600,228,229,401,496,703,205,375回の移動が必要で、さっきの条件で移動させると、約40,196,936,841,331,475,186,983年（おおよそ402垓（ｶﾞｲ）年）かかるんですねｗ
ﾔｯｸ━━ΣΣ(ﾟДﾟ；)━━ﾃﾞｶﾙﾁｬｰ!!
「垓」とは、「兆」の次の「京」の次です。


指数関数の増加率のすごさと、数学的帰納法の威力がわかるゲームですね。