ハノイの塔の最小移動回数と再帰公式 2ⁿ−1 を徹底解説

ハノイの塔の最小移動回数と再帰公式 2ⁿ−1 を徹底解説

結論から言うと、n 枚の円盤を移動する最小回数は 2ⁿ−1 です。1 枚なら 1 回、3 枚なら 7 回、10 枚なら 1023 回。この「一点の無駄もない」答えは、ごく短い再帰の推論で自分の手で導き出せます。この記事ではその「なぜ」を徹底的に解き明かし、最後にオンラインのハノイの塔で実際に確かめてもらいます。

最小移動回数（2ⁿ−1）とは

ハノイの塔のルールは次の 3 つだけです。

• 一度に動かせる円盤は1 枚だけ
• 動かせるのは、それぞれの棒のいちばん上の円盤
• 大きな円盤を小さな円盤の上に乗せてはいけない

この 3 つのルールの下で、n 枚の円盤を左の棒から右の棒へすべて移すとき、必要な移動回数には最小値が存在し、それが 2ⁿ−1 です。

円盤数 n	最小移動回数 2ⁿ−1
1	1
2	3
3	7
4	15
5	31
6	63
7	127
8	255
9	511
10	1023

ポイントは 2 つあります。第一に、これは「上手い人がやればもっと少なくできる」という経験則ではなく、厳密に証明できる下限です。最適解はどれもちょうど 2ⁿ−1 回で、1 回たりとも減らせません。第二に、n が 1 増えるたびに回数がほぼ倍増します。指数関数的な増加の最も分かりやすい実例です。

なぜ 2ⁿ−1 なのか：再帰による導出（簡単な手順つき）

n 枚の円盤を A から C へ移すことを考えます。最後の一手は必ず「最大の円盤（n 枚目）を A から C へ移す」です。この一手が合法になるためには、上の n−1 枚がすべて道を譲り、中間の棒 B にきれいに積まれている必要があります。

つまり作業全体は 3 つの区間に分けられます。

1. 上の n−1 枚を A から C を経由して B へ移す——これ自体が n−1 枚のハノイの塔の問題
2. 最大の円盤を A から C へ移す——1 回
3. n−1 枚を B から A を経由して C へ戻す——これも n−1 枚のハノイの塔の問題

n 枚の最小回数を f(n) とすると、漸化式はこうなります。

f(n) = 2·f(n−1) + 1（f(1) = 1）

順に展開すると次のようになります。

• f(2) = 2×1 + 1 = 3
• f(3) = 2×3 + 1 = 7
• f(4) = 2×7 + 1 = 15
• ……1 段上がるごとに「2 倍して 1 足す」が繰り返される。

この漸化式の解がちょうど 2ⁿ−1 になる理由を、いちばん直感的に見てみましょう。「2 倍して 1 足す」を繰り返す効果は、1+2+4+…+2ⁿ⁻¹ = 2ⁿ−1 という総和にほかなりません（2ⁿ−1 に 1 を足して半分に割る操作を n 回繰り返すと、ちょうど元に戻ります）。数学的帰納法で書けば、f(n−1) = 2ⁿ⁻¹−1 を仮定すれば f(n) = 2(2ⁿ⁻¹−1)+1 = 2ⁿ−1 が成り立ち、n=1 で成立し各段階で受け継がれるため、すべての n で成立します。

同時に「なぜそれ以上減らせないのか」も分かります。最大の円盤が大事な一手を指せるようになるには、上の n−1 枚は B と C のどちらにいても、最低一度は完全に道を譲らなければならず、それに最低 f(n−1) 回かかります。最大の円盤が C に着いた後、再び完全に元に戻すのにも最低 f(n−1) 回。最大の円盤自身の 1 回を加えた 2·f(n−1)+1 は、1 回も省略できません。

64 枚の円盤と世界終末の伝説

この漸化式には有名な「副産物」があります。伝説によれば、梵天の神殿には 3 本の宝石の柱と 64 枚の金の円盤があり、僧侶たちが昼も夜もルールに従って運び続け、64 枚すべての移動が完了したとき、世界は一瞬の雷鳴とともに終わるといいます。64 枚では何回必要か、公式に代入してみましょう。

2⁶⁴−1 = 18,446,744,073,709,551,615 回

約 1844 億の 1 億倍、つまり約 1.8×10¹⁹ 回です。この数字がどれほど大きいか。僧侶が 1 秒に 1 回動かして年中無休で働いても、1 年は約 3150 万秒しかないため、完了までには約 5845 億年かかります。宇宙の年齢（約 138 億年）の 40 倍以上です。だから「世界の終わり」を心配する必要はありません。世界のほうが先に老いてしまい、円盤の運搬はまだ半分も進みません。

指数関数的増加を理解する絶好の例でもあります。n=1 の 1 回から n=64 の 1.8×10¹⁹ 回まで、やっていたことは「2 倍して 1 足す」を 63 回繰り返しただけです。

3〜4 枚の円盤の実演

公式を暗記するより、まず 3 枚を実際に動かすほうがずっと早く理解できます。以下は最適解の完全な手順です（A=出発、B=補助、C=目標）。

3 枚（7 回）

1. 小 A→C
2. 中 A→B
3. 小 C→B
4. 大 A→C
5. 小 B→A
6. 中 B→C
7. 小 A→C

ここから読み取れる暗記不要の法則が 2 つあります。奇数枚のとき、最初の一手は必ず目標の棒へ向かい、偶数枚のときは補助の棒へ向かう（3 枚なら C、4 枚なら B）。この 2 つを押さえれば、手順を暗記しなくても最短ルートを歩けます。もし途中で間違えたら、大きな円盤を誤った棒に「居座らせない」ためにも、取り消してやり直すほうが得です。

4 枚（15 回）

考え方はまったく同じで、「上の山」が 2 枚から 3 枚になっただけです。

1. 上の 3 枚を 3 枚の最適解で A から B へ（C を経由）移す——7 回
2. 最大の円盤を A から C へ——8 回目
3. 3 枚を B から C へ（A を経由）戻す——さらに 7 回

4 枚の 15 回は「3 枚の 7 回を 2 回やり、間に最大の円盤を 1 回挟む」だけです。各ステップで動くのは常に「その時点で合法的に動かせる最小の円盤」で、法則に従えば 15 回ちょうどで完成します。

紙の上で確認したら、オンラインのハノイの塔で実際に試しましょう。まず 3 段、次に 4 段。手数カウントを確認しながら、7 回・15 回をぴったり出せるか見てみてください。

よくある間違い

• 小さい円盤を往復させすぎる：小円盤は自由度が高いぶん、1 回ごとにカウントされます。最適解では意味のない往復はありません。小円盤を 3 回連続で行ったり来たりしているなら、どこかで道を誤ったサインです。
• 再帰を「山ごと同時移動」と勘違いする：再帰は作業の区切り方を示すもので、実際の 1 手は依然として 1 枚だけです。「3 枚まとめて運ぶ」は合法な 1 手ではありません。
• なんとなく動かして始める：目標を考えずに動かすと、大きな円盤を追い込みがちで、最後に 2ⁿ−1 を大きく超える手数で「窮地脱出」することになります。動かす前に自問しましょう。この一手は「最大の円盤の道を開ける」ことに役立っているか、と。
• 2ⁿ−1 より少なくできると思い込む：標準の 3 本柱ルールでは近道は存在しません。「もっと少ない手数」という主張は、ルール変更（4 本柱・飛び越し許可）のケースか、単純に誤りです。
• 大きな円盤を早すぎる段階で目標棒に置く：より小さい円盤が整っていないうちに置くと、後で「持ち上げて戻す」無駄が 2 回以上発生しがちです。

練習：公式を自分の手で検証する

ハノイの塔オンラインゲームを開いて、次の順で練習しましょう。

1. 3 段モードを 7 回でクリア。攻略を見ずに自力で歩けるか試す
2. 4 段モードを 15 回でクリア。「3 枚の手順を 2 回」のリズムを掴む
3. 5 段（31 回）、6 段（63 回）に挑戦し、法則どおり進めているか自分で検証
4. 8 段（255 回）以上に挑んで、指数関数的増加の速さを肌で感じる

FAQ

Q1：2ⁿ−1 という公式はどうやって導かれるのですか？ 漸化式 f(n) = 2·f(n−1) + 1 から来ています。n 枚を運ぶには、まず上の n−1 枚をどかし（f(n−1) 回）、最大の円盤を置き（1 回）、その後 n−1 枚を戻す（f(n−1) 回）必要があります。この漸化式を数学的帰納法で解けば f(n) = 2ⁿ−1 が得られます。

Q2：64 枚を運び終えると本当に世界が終わるのですか？ いいえ、伝説です。64 枚では 18,446,744,073,709,551,615 回必要で、1 秒 1 回としても約 5845 億年かかり、宇宙の年齢をはるかに超えます。終末伝説は、この数字の大きさを表現する昔の人の工夫です。

Q3：手順を暗記しないで済むコツや法則はありますか？ あります。核心は 2 つ。① 奇数枚なら最初の一手は目標の棒、偶数枚なら補助の棒へ。② 以降の各手では「その時点で合法的に動かせる最小の円盤」を動かし、直前と同じ場所には戻さない。この 2 つに従えば、何段でも最短手順で進められます。

Q4：再帰の考え方はプログラミングでどう使いますか？ 疑似コードはわずか 3 行です。まず n−1 枚を始点から補助棒へ移す（再帰）、次に最大の円盤を始点から目標棒へ移す（この一手を出力）、最後に n−1 枚を補助棒から目標棒へ移す（再帰）。再帰の深さは n、呼び出しの総数はちょうど 2ⁿ−1 で、公式と完全に一致します。

Q5：柱が 4 本のハノイの塔（Frame–Stewart 法）だと手数は減りますか？ 減ります。柱が 1 本増えるだけで必要回数は大幅に減り、64 枚問題でも 2⁶⁴−1 をはるかに下回ります。ただし 4 本柱の一般最適解には今なお単純な閉じた公式がなく（Frame–Stewart 法は一部の n で最適と証明済み）、本記事の公式 2ⁿ−1 は 3 本柱が前提です。