ハノイの塔で円盤が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つに分けられます。

  1. 上のn−1枚を、左から中央へ移す。
  2. いちばん大きい円盤を、左から右へ1回で動かす。
  3. 中央の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手で完成します。