ハノイの塔
ハノイの塔は古典的な数学パズルです。3本の棒、大きさの違う円盤の山、そして2つの厳しいルール。円盤は1回に1枚ずつ動かし、大きな円盤を小さな円盤の上には決して置かないこと。
3本の棒と円錐形の円盤の山
盤には3本の棒があります。円盤はすべて大きさが違い、棒に差し込めます。最初はすべての円盤が1本の棒に、大きさの順に、いちばん大きいものを底に、いちばん小さいものを上にして積まれているので、山は円錐形になります。 目標は、その塔全体を別の棒に移すことです。
3つのルール
1. 円盤は1回に1枚だけ動かす。 2. 1手とは、山のいちばん上の円盤を取り、別の山か空いている棒に置くこと。 3. 大きな円盤を小さな円盤の上に置いてはいけない。 この3つのルールがゲームのすべてです。このルールのもとでは、合法な局面とはどれも、各棒の順序を保ったまま円盤を棒に振り分けたものになります。
最短の解は 2ⁿ − 1
n 枚の円盤の塔を解く最少手数は 2ⁿ − 1 です。 円盤1枚なら1手。2枚なら3手。3枚なら7手、4枚なら15手、5枚なら31手です。円盤が1枚増えるごとに、前の解が2倍になり、いちばん大きな円盤を運ぶ1手が加わります。n − 1 枚に T 手かかるなら、n 枚には 2T + 1 手かかります。この漸化式がちょうど 2ⁿ − 1 になります。 PictorX アプリで最も高い塔である8枚では 255 手かかります。これより短い合法な道筋はありません。
再帰のしくみ
残りの棒を補助に使って、n 枚の円盤を最初の棒からゴールの棒へ移すには： 1. 上の n − 1 枚を最初の棒から補助の棒へ移す。 2. いちばん大きな円盤を最初の棒からゴールの棒へ直接移す。 3. n − 1 枚を補助の棒からゴールの棒へ、いちばん大きな円盤の上に移す。 手順2が合法なのは、いちばん大きな円盤はどの棒にも置けるからです。手順1と3は、円盤が1枚少ない同じパズルです。呼び出しは円盤1枚まで来ると終わり、その1枚は1回だけ動きます。これを展開すると 2ⁿ − 1 手になり、どの手順でも大きな円盤が小さな円盤の上に置かれることはありません。
64枚の金の円盤の伝説
フランスの数学者エドゥアール・リュカは1883年にこのパズルを発表しました。その際、彼はインドのカーシー・ヴィシュワナートにある寺院の伝説を語りました。そこでは僧侶たちが同じルールで64枚の金の円盤の山を動かしていて、最後の1手が指されたとき世界は終わる、というものです。 64枚の円盤には 2⁶⁴ − 1 手、つまり 18,446,744,073,709,551,615 手かかります。1秒に1手、昼も夜も間違えずに動かしても、約5850億年かかります。僧侶たちが終えることはありません。
PictorX で遊ぶ
ハノイの塔を開くと、最初の棒にはすでに円盤4枚の塔があります。最少は15手です。いちばん上の円盤を別の棒にドラッグするか、棒をクリックしてから移したい棒をクリックします。キー 1、2、3 でも同じ操作ができます。大きな円盤を小さな円盤の上に置こうとすると拒否されます。 「円盤」は1から8まで選べるので、1、3、7、15、31、63、127、255 を公式と照らし合わせられます。「ステップ」は最短の解の1手を再生します。「解く」は残りを再生します。「円盤3枚を見る」では再帰の手順が動くようすを見られます。「元に戻す」と「やり直す」で手を行き来できます。PNG を保存するか、盤を PictorX エディターで開きます。
よくある質問
ハノイの塔のルールは？
円盤は1回に1枚ずつ動かします。棒のいちばん上の円盤を取り、別の棒に置きます。大きな円盤を小さな円盤の上に置いてはいけません。塔全体は1本の棒から始まり、別の棒で終わらなければなりません。
最短の解は何手ですか？
2ⁿ − 1 手です。円盤1枚なら1手、2枚なら3手、3枚なら7手、4枚なら15手、5枚なら31手です。円盤が1枚増えるごとに、前の解が2倍になり1手が加わります。
ハノイの塔を考案したのは誰ですか？
フランスの数学者エドゥアール・リュカが1883年に発表しました。カーシー・ヴィシュワナートの僧侶と64枚の金の円盤の話は、彼がこのパズルに添えた伝説です。
64枚だとどれくらいかかりますか？
2⁶⁴ − 1 手、つまり 18,446,744,073,709,551,615 手です。1秒に1手なら約5850億年かかります。
関連ツール
ハノイの塔
ブラウザで円盤の塔を3本の棒の間で動かします。1回に1枚、大きな円盤を小さな円盤の上に置くことはできません。最短の解は 2ⁿ − 1 手です。
ビュフォンの針
ブラウザーで線の引かれた床に針を落とします。交差を数え、ビュフォンの1777年の実験が π を推定する様子を見てみましょう。
ビュフォンの針
ビュフォンの1777年の針の問題。平行線に落とした針がなぜ π を推定するのか、短い針の確率 2l/(πd) がサイン曲線の下の面積からどう導かれるのか、そしてなぜ実験の収束が遅いのかを解説します。
かけ算の円
円の上の各数をその倍数と結びます。紙に、チョークで、または木の上に、かけ算表やカージオイド、糸かけの図形を描きましょう。
コラッツ予想
ブラウザでコラッツの 3n+1 問題を探検しましょう。あられ数列をたどり、幾何学的なコラッツの木を育て、連続版コラッツ・フラクタルをズームできます。
ラングトンのアリ
ブラウザでラングトンのアリを動かしましょう。対称、カオス、104 ステップのハイウェイを観察し、多色の規則、複数のアリ、六角格子、ターマイトも試せます。
試してみますか？
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
ハノイの塔で遊ぶ