伝説とともに語られるパズル
ハノイの塔は1883年、フランスの数学者エドゥアール・リュカによって発表されました。64枚の黄金の円盤を僧侶たちが動かし続け、それが完了したときに世界が終わるという伝説が添えられていたと伝えられています。実際、円盤64枚の最小手数は1800京回を超え、1秒に1手動かしたとしてもおよそ5850億年かかる計算になり、指数関数的な増加のすさまじさを象徴する例になっています。
なぜ再帰的な戦略が常に通用するのか
この再帰戦略が機能するのは、パズルのルールが「小さな山がどのようにしてその杭の上に積まれたか」をまったく問題にせず、「正しい降順で積まれているかどうか」だけを問題にしているからです。つまり、n-1枚の円盤を正しく移動させる方法さえあれば、それをそのままn枚を解くための部品として再利用できます。だからこそ、同じ単純な3ステップのパターンが、何枚の円盤に対してもそのまま通用するのです。
よくある質問
なぜ2のn乗マイナス1が「最小」だと言えるのですか、単なる目安ではないのですか?
一番下(最大)の円盤を動かすには、まずその上にあるn-1枚をすべて別の1本の杭に移す必要があり、動かした後は、そのn-1枚を再びその上に移動させる必要があります。つまりn枚の手数は必ずn-1枚の手数のちょうど2倍に1を足した数になり、これを数式的に展開すると2のn乗引く1になります。
開始する杭や目的の杭によって必要な手数は変わりますか?
変わりません。最小手数は円盤の枚数だけで決まり、どの杭から始めてどの杭を目的にするかには左右されません。杭の選び方にかかわらず、公式「2のn乗引く1」がそのまま成り立ちます。