ハノイの塔で円盤がn枚のとき、塔を別の棒へ移すいちばん少ない手数は 2ⁿ−1回 です。2を円盤の枚数だけ掛けて、1を引いた数になります。
| 円盤の枚数 | 最少手数 |
|---|---|
| 1枚 | 1回 |
| 2枚 | 3回 |
| 3枚 | 7回 |
| 4枚 | 15回 |
| 5枚 | 31回 |
| 6枚 | 63回 |
| 7枚 | 127回 |
| 8枚 | 255回 |
| 9枚 | 511回 |
円盤が1枚増えるたびに、手数はおよそ2倍になります。なぜそうなるのかを、順に見ていきましょう。
いちばん大きい円盤に注目する
n枚の塔を左から右へ移すことを考えます。いちばん大きい円盤は、ほかの円盤の下にあるので、そのままでは動かせません。大きい円盤を右へ運ぶには、その瞬間に次の状態になっている必要があります。
- 大きい円盤の上に、何も載っていない。
- 右の棒が空いている(大きい円盤より小さい円盤は、その下に置けないため)。
つまり、残りのn−1枚は、すべて中央の棒に積まれていなければなりません。
手数を3つに分ける
ここから、n枚を移す手順は次の3つに分けられます。
- 上のn−1枚を、左から中央へ移す。
- いちばん大きい円盤を、左から右へ1回で動かす。
- 中央のn−1枚を、大きい円盤の上へ移す。
1と3は、どちらも「n−1枚の塔を移す」問題そのものです。n枚の最少手数をT(n)と書くと、
T(n) = T(n−1) + 1 + T(n−1) = 2 × T(n−1) + 1
という関係になります。1枚のときは1回なので、T(1) = 1。ここから順に、3、7、15、31…と求められます。
式が 2ⁿ−1 になる理由
この関係の両辺に1を足すと、
T(n) + 1 = 2 × (T(n−1) + 1)
となります。「手数に1を足した数」は、円盤が1枚増えるたびにちょうど2倍になるということです。1枚のときは T(1) + 1 = 2 なので、n枚では2をn回掛けた 2ⁿ。そこから1を引いて、T(n) = 2ⁿ−1 になります。
これより少なくできない理由
上の手順で2ⁿ−1回で移せることは分かりました。では、もっと少ない手数で移す方法はないのでしょうか。
先ほどのとおり、大きい円盤を初めて動かす瞬間には、残りのn−1枚がすべて別の1本に積まれていなければなりません。そこまでに、少なくともn−1枚の塔を移す手数がかかります。同じように、大きい円盤を最後に右へ置いたあと、残りのn−1枚をその上へ積み直すにも、少なくともn−1枚の塔を移す手数がかかります。大きい円盤そのものも、少なくとも1回は動かします。
どんな手順でも、この3つの手数は必ずかかります。だから、2 × T(n−1) + 1回より少なくはできません。いちばん少ない手順は、実はこの1通りしかないことも知られています。
アプリの「定番」は127手
アプリ「ハノイの塔」の定番は7枚なので、最少手数は 2⁷−1 = 127手です。手数が127になったら、いちばん少ない手順で解けたということです。遊び方の記事で紹介した「小さい円盤を同じ向きに回す」動かし方をすると、ちょうど127手で完成します。
