ハノイの塔の最短手数の公式｜漸化式と2のn乗−1の求め方

ハノイの塔の最短手数の公式

円盤がn枚の時、ハノイの塔の最短手数は「2のn乗−1」手です。

a_n = 2ⁿ − 1a_n：円盤がn枚の時の最短手数

例えば、3枚なら2×2×2−1＝7手、4枚なら2×2×2×2−1＝15手です。枚数ごとの最短手数は以下の通りです。

ハノイの塔のルールと、実際に解く手順は『ハノイの塔のルールと解き方』の記事で紹介しています。

ハノイの塔の漸化式の立て方

最短手数の公式は、円盤が1枚増えた時の手数の関係（漸化式）から求めます。

n＋1枚の塔を左の棒から右の棒へ移す時は、次の3つの段階に分けられます。

• 上のn枚を、真ん中の棒へ移す（a_n手）
• 一番大きい円盤を、右の棒へ動かす（1手）
• 真ん中のn枚を、右の棒へ移す（a_n手）

この3つを足すと、次の漸化式になります。円盤が1枚増えると、最短手数は「前の手数の2倍＋1」手になります。

a_n+1 = 2a_n + 1はじめ：a₁ = 1（1枚なら1手で移せる）

例えば、a₂＝2×1＋1＝3、a₃＝2×3＋1＝7、a₄＝2×7＋1＝15 と順に求まります。

ハノイの塔の漸化式の解き方

漸化式 a_n+1＝2a_n＋1 は、両辺に1を足すと解けます。

a_n+1 + 1 = 2(a_n + 1)

ここで b_n＝a_n＋1 とおくと、b_n+1＝2b_n になります。b_nは、1枚増えるごとに2倍になる数（公比2の等比数列）です。

b₁＝a₁＋1＝2 なので、b_n＝2ⁿ です。

よって、a_n＝b_n−1＝2ⁿ−1 となります。

両辺に足す数（ここでは1）は、a_n+1＋c＝2(a_n＋c) となる c です。式を開くと 2c−c＝1 なので、c＝1 と求まります。

ハノイの塔の最短手数の証明

ハノイの塔の最短手数が「2のn乗−1」手になる理由は、2つの方法で確かめられます。

これより少なくできない理由

2のn乗−1手より少なくできないことは、一番大きい円盤に注目すると分かります。

一番大きい円盤を動かす直前には、他のn−1枚が全部、残りの1本の棒に集まっている必要があります。

一番大きい円盤の上と、置く先の棒には、他の円盤があってはいけないからです。ここまでに、少なくとも a_n−1 手かかります。

一番大きい円盤を最後に動かしたあとも、n−1枚をその上へ積み直すので、少なくとも a_n−1 手かかります。一番大きい円盤も、少なくとも1回は動かします。

合わせると、少なくとも 2a_n−1＋1 手です。この手数は、先ほどの3つの段階の手順でちょうど達成できるので、これが最短の手数です。

数学的帰納法で確かめる

公式 a_n＝2ⁿ−1 が全てのnで正しいことは、数学的帰納法で確かめられます。

• n＝1の時：a₁＝1＝2¹−1 なので正しい
• n＝kの時に正しいとすると：a_k+1＝2a_k＋1＝2(2^k−1)＋1＝2^k+1−1
• n＝k＋1の時も正しいので、全てのnで正しい

ハノイの塔で円盤ごとに動く回数

最短の手順では、小さい円盤ほどたくさん動きます。

n枚の時、一番小さい円盤は2ⁿ⁻¹回、一番大きい円盤は1回だけ動きます。4枚の時は以下の通りです。

1つ大きい円盤ほど、動く回数は半分になります。全部を足すと 1＋2＋4＋…＋2ⁿ⁻¹＝2ⁿ−1 となり、公式と同じになります。

ハノイの塔と2進数の関係

最短の手順で何手目にどの円盤を動かすかは、2進数で分かります。

手の番号を2進数で書いた時、右から何桁目に初めて1が出るかを見ます。その桁の数が、動かす円盤の番号（小さい方から数えて何番目か）です。

奇数番目の手は、2進数の1桁目が必ず1なので、いつも一番小さい円盤を動かします。最短の手順が「1手おきに小さい円盤」になるのは、このためです。

64枚のハノイの塔は何年かかる？

64枚の最短手数は、2⁶⁴−1＝18,446,744,073,709,551,615手（約1845京手）です。

1秒に1手ずつ休まず動かしても、約5845億年かかります。

宇宙が生まれてから今まで（約138億年）の、40倍以上の長さです。ハノイの塔には「64枚を移し終えた時、世界が終わる」という言い伝えがあります。

言い伝えのくわしい話は『ハノイの塔のルールと解き方』の記事の、伝説と由来の章で紹介しています。

変わりルールのハノイの塔の公式

ハノイの塔の変わりルールでも、同じ考え方で最短手数を求められます。

隣の棒にしか動かせない時

隣の棒へしか動かせない時、n枚の塔を左端から右端へ移す最短手数は「3のn乗−1」手です。

n＋1枚の塔を移す時、一番大きい円盤は、真ん中の棒を通って2回動きます。その前・間・あとに、上のn枚を端から端へ3回移します。

n枚を3回と一番大きい円盤を2回なので、次の漸化式になります。

a_n+1 = 3a_n + 2はじめ：a₁ = 2（1枚でも真ん中を通るので2手）

両辺に1を足すと a_n+1＋1＝3(a_n＋1) なので、a_n＝3ⁿ−1 です。3枚なら26手、4枚なら80手になります。

棒が4本の時

棒が4本の時の最短手数は、3本の時のような短い式では表せません。

まず、上の何枚かは、4本の棒を使って別の棒へ移します。残りの円盤を3本の棒の手順で右端へ移し、最後に、先ほどの何枚かをその上へ4本の棒を使って移します。

何枚を先に移すかで手数が変わるので、一番少なくなる枚数を選びます。この方法が最短だと証明されたのは、2014年のことです。