ハノイの塔の手数は、なぜ2倍ずつ増えるのか

問いを正確にする：2倍ずつ増えるのは何か

まずルールを確認します。棒はA、B、Cの3本で、最初はAに円盤がすべて、大きい順に下から積まれています。目標は、全部をCへ移すことです。守るルールは次の2つです。

• 1回に動かせる円盤は1枚だけです。動かすのは、棒の一番上にある円盤です。
• 小さい円盤の上に、大きい円盤を置くことはできません。

この記事では、円盤1枚を1本の棒から別の棒へ動かすことを「1手」と数えます。数え方を先に決めておくのは大切なことです。「戻す」操作を手数に含めるかどうかなど、定義が違えば数字も変わります。

円盤n枚の最少手数を T(n) と書きます。ここでの問いは「T(n) は T(n−1) の何倍か」ですが、ぴったり2倍にはなりません。正しくは次の関係です。

T(n) = 2 × T(n−1) + 1

「+1」を移項すると、見通しがよくなります。両辺に1を足すと次の形になります。

T(n) + 1 = 2 × ( T(n−1) + 1 )

つまり、手数に1を足した値は、枚数が1枚増えるたびにぴったり2倍になります。題名の「2倍ずつ」は、手数そのものではなく、この「手数＋1」について正確に言えることです。

1枚・2枚・3枚の手順を図で追う

小さい場合から順に手順を追います。円盤は、小さい方から1、2、3と呼びます。

1枚の場合です。1をAからCへ動かして終わりです。

手1: 円盤1  A→C

2枚の場合です。1をいったんBに逃がし、2をCへ動かし、1をCへ戻します。

手1: 円盤1  A→B
手2: 円盤2  A→C
手3: 円盤1  B→C

3枚の場合です。各手のあとの棒の状態を、下から上の順に書きます。

開始      A: 3 2 1    B: -       C: -
手1: 1 A→C  A: 3 2      B: -       C: 1
手2: 2 A→B  A: 3        B: 2       C: 1
手3: 1 C→B  A: 3        B: 2 1     C: -
手4: 3 A→C  A: -        B: 2 1     C: 3
手5: 1 B→A  A: 1        B: 2       C: 3
手6: 2 B→C  A: 1        B: -       C: 3 2
手7: 1 A→C  A: -        B: -       C: 3 2 1

ここで手4に注目します。いちばん大きい円盤3が動くのは、この1回だけです。手4の直前には、小さな2枚（2と1）がBに積まれていて、AとCがそれぞれ「3だけ」「空」になっています。大きい円盤を動かすには、この状態が必要です。

手1〜3は、「2枚の塔をAからBへ動かす」手順になっています。2枚の手順で、行き先をCからBに読み替えたものです。手5〜7は、「2枚の塔をBからCへ動かす」手順です。3枚の手順は、2枚の手順2回と、大きい円盤の1手でできています。

再帰の構造：同じ形が一回り小さく入っている

3枚で見えた形は、枚数を問わず成り立ちます。n枚の塔を、出発の棒から目的の棒へ動かす手順は、次の3段階です。

1. 上の(n−1)枚を、出発の棒から「残りの1本」へ動かします。
2. いちばん大きい円盤を、出発の棒から目的の棒へ動かします。
3. 先ほど動かした(n−1)枚を、残りの棒から目的の棒へ動かします。

この1と3は、「n枚」の問題を「(n−1)枚」にした同じ形の問題です。自分自身の手順を、一回り小さい規模で呼び出しています。これが再帰です。(n−1)枚の動かし方は、さらに(n−2)枚の動かし方を2回使います。これを繰り返すと、最後は1枚の動かし方、つまり1手に行き着きます。

手数を数えると、1と3でそれぞれ T(n−1) 手、2で1手なので、合計は 2×T(n−1)+1 手です。これが先ほどの関係の正体です。

この手順が最少である理由も、図から読み取れます。いちばん大きい円盤を動かす瞬間、上に円盤が乗っていてはいけません。また、行き先の棒にも円盤があってはいけません。大きい円盤の上にも、行き先の棒にも、小さい円盤は置けない、というルールのためです。したがって、残りの(n−1)枚は第三の棒に積まれている必要があります。大きい円盤が動く前に、(n−1)枚を第三の棒へ移す手が必ず要ります。動かしたあとも、(n−1)枚を大きい円盤の上に乗せ直す手が要ります。この2回分は省けません。

自分で数える：記録表と読み方

円盤は硬貨や紙片でも代用できます。大きさの違うものを重ね、ここでは「紙を3枚の円盤、紙コップを棒」のような見立てで十分です。1枚から4枚まで、次の手順で記録します。

• 1手動かすたびに、手数を1つ数えます。
• 各枚数で、無駄な手を入れずに動かしきったときの手数を記録します。
• 動かし方に迷ったら、前の章の3段階に従います。

記録表は次のようにします。右側の列は、数えた結果から計算して埋めます。

• 1、数えた手数 T(n)：、T(n)＋1：、T(n)＋1 が前の行の何倍か：（基準）
• 2、数えた手数 T(n)：、T(n)＋1：、T(n)＋1 が前の行の何倍か：
• 3、数えた手数 T(n)：、T(n)＋1：、T(n)＋1 が前の行の何倍か：
• 4、数えた手数 T(n)：、T(n)＋1：、T(n)＋1 が前の行の何倍か：

読み方の基準は次のとおりです。

• 「T(n)＋1」の列が、行ごとにぴったり2倍になっていれば、手順が最少で、構造もそのとおりです。
• 3枚で7手より多くなったら、途中で同じ円盤を意味なく往復させていないか、手順表で確認します。
• 4枚の手数は、表を見る前に「3枚の手数×2＋1」で予想し、実際に数えた値と照らし合わせます。予想と合えば、構造を理解できています。

枚数と手数の関係は、一般に T(n) = 2ⁿ − 1 と書けます。表の「T(n)＋1」の列が2、4、8、…と並ぶのは、このためです。数えた結果が2の累乗に1足りない形になっているかどうかが、確認の目印になります。

コードで同じ手順を列挙する

手で数える代わりに、再帰の定義をそのままコードにして確かめる方法もあります。次のファイルは外部ライブラリを使わず、単独で動きます。ブラウザで開くと、手順と合計手数が表示されます。

<pre id="out"></pre>
<script>
let count = 0;
const lines = [];
function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  count++;
  lines.push(count + ": 円盤" + n + " " + from + "→" + to);
  hanoi(n - 1, via, to, from);
}
const n = 3;
hanoi(n, "A", "C", "B");
lines.push("合計 " + count + " 手");
document.getElementById("out").textContent = lines.join("\n");
</script>

関数 hanoi の中身は、前の章の3段階そのものです。1行目の hanoi(n - 1, from, via, to) が「(n−1)枚を残りの棒へ」、真ん中が「大きい円盤を目的の棒へ」、最後の行が「(n−1)枚を目的の棒へ」にあたります。n = 3 の出力は、図で追った7手と同じ順になります。n の値を4、5と変えて、合計の手数を表に書き込んでください。

起こりやすい誤り

数えたり実装したりするとき、つまずきやすい点を挙げます。

• 手数の定義がぶれる：「1手」を円盤1枚の移動と決めたのに、複数枚を一度に動かす数え方が混ざることがあります。ルールで許されるのは1枚ずつです。
• 「手数が2倍」と思い込む：3手の次は6手ではなく7手です。「＋1」を忘れると、表の比が合いません。「手数＋1」で見ると、ぴったり2倍になります。
• 棒の役割の取り違え：再帰の1段階目では、行き先が「目的の棒」ではなく「残りの棒」です。コードでは hanoi(n - 1, from, via, to) の引数の順番を間違えやすい箇所です。
• 0枚の扱い忘れ：コードの if (n === 0) return; を外すと、再帰が止まらなくなります。止まる条件を最初に決めることが再帰の基本です。
• 「最少」の検証不足：動かしきれたことと最少であることは別です。少なくとも3枚では、7手より少ない手順がないかを、大きい円盤が動く前に必要な状態から考えてみます。

「手数がどう数えられるか」の定義が結果を左右する点は、ほかのパズルでも同じです。たとえば「かたちのあいだ」には、次の一手のヒントが最短とは限らない仕組みと、一手戻しても手数は減らない仕組みがあります。自分の記録を読むときは、どこまでを1手と数えているのかを、ゲーム側の説明で確かめておくと誤解を避けられます。

次の行動

手元の紙片か上のコードを使って、1〜4枚の手数を表に書き込み、「T(n)＋1」の列が2倍ずつになるかを確かめてみてください。4枚を数える前に、3枚の手数から予想を立てておくと、再帰の理解度がはっきり分かります。

さらに進めたい場合は、上のコードに円盤の絵と「クリックで動かす」操作を足し、index.html 1つの作品にして投稿する方法があります。アソバースは単独のHTMLファイルをアップロードして公開できます。手順の列挙だけでも、「枚数を選ぶと手順が表示される」小さな教材として成り立ちます。