ハノイの塔の解き方（最短手数と公式）

一番小さい円盤を1回おきに同じ向きへ回すと、何段でも最短の2ⁿ−1手でそろいます。

小さい円盤を1回おきに同じ向きへ回す

• 回す向きは奇数段なら 左→右→真ん中、偶数段なら 左→真ん中→右
• 2・4・6…手目は小さい円盤以外を動かす（動かせるのは1通りだけ）

3段は7手・4段は15手でそろう

円盤の番号は小さい順。左・真ん中・右は棒です。

3段の答え（7手）

1. 1左→右
2. 2左→真ん中
3. 1右→真ん中
4. 3左→右
5. 1真ん中→左
6. 2真ん中→右
7. 1左→右

4段の答え（15手）

1. 1左→真ん中
2. 2左→右
3. 1真ん中→右
4. 3左→真ん中
5. 1右→左
6. 2右→真ん中
7. 1左→真ん中
8. 4左→右
9. 1真ん中→右
10. 2真ん中→左
11. 1右→左
12. 3真ん中→右
13. 1左→真ん中
14. 2左→右
15. 1真ん中→右

最短手数は2ⁿ−1（4段なら15手）

円盤が n 枚（n段）なら、2を n 回かけて1を引いた数が最短手数です。

n段の手数は「1つ少ない段×2＋1」

一番大きい円盤を動かすには、上の円盤を全部よけておく必要があります。

だから1段増えるごとに「2倍＋1」。手数に1を足すと倍々になり、n段の最短は 2ⁿ−1 手です。

数列の漸化式なら a_n＝2a_n−1＋1 を a_n＋1＝2(a_n−1＋1) と変形して解きます。

よくある質問

最初の1手はどこへ？

奇数段は右の棒、偶数段は真ん中の棒へ一番小さい円盤を動かす

どうしてこれより短くできない？

一番大きい円盤を動かす前とあとに、ほかの円盤を全部1本に集める必要があるから

それぞれの円盤は何回動く？

一番小さい円盤が全体の約半分（2ⁿ⁻¹回）。1つ大きくなるごとに半分になり、一番大きい円盤は1回

覚え方はほかにある？

最短の手順では、奇数番の円盤どうし・偶数番の円盤どうしを重ねない

途中の形から最短で解くには？

一番大きい円盤から考える。右の棒にあればそのままにし、無ければそれより小さい円盤を全部残りの1本へ寄せてから動かす

真ん中の棒へ移すときは？

回す向きが逆になる。奇数段なら 左→真ん中→右 の向き

棒が4本なら？

1〜8枚の最短は 1・3・5・9・13・17・25・33手。1枚ごとの増え方は、2が2回・4が3回・8が4回…と続く

プログラムではどう書く？

「n−1段を真ん中へ・n番を右へ・n−1段を右へ」を同じ関数の中で呼ぶ（再帰）

ゲームで練習できる？

3段〜10段と今日の問題（ばらばらの5枚）。「ヒント」で最短の次の一手が光る