１．ハノイの塔とは？ゲームの基本ルール
「ハノイの塔」は、19世紀にフランスの数学者エドゥアール・リュカによって考案されたパズルゲームです。数学の「漸化式（ぜんかしき）」を学ぶ際の最高の実践教材として、多くの教科書や入試問題で取り上げられています。
まずは基本ルールをおさらいしましょう。
📜 ハノイの塔のルール
- 3本の杭（A, B, C）と、大きさがすべて異なる $n$ 枚の円盤がある。
- 最初はすべての円盤が大きさ順に杭Aに重なっている（下が大きく、上が小さい）。
- 1回の移動で、いずれかの杭の一番上にある円盤を1枚だけ別の杭に移動できる。
- 小さな円盤の上に大きな円盤を乗せてはならない。
- すべての円盤を杭Aから別の杭（例：杭C）へ移動させたら完成！
枚数 $n$ が少ないうちは手作業で解けますが、枚数が増えると一気に難易度が上がります。
では、$n$ 枚の円盤を移動させるための「最小移動回数」は、どのように計算すればよいのでしょうか？
２．枚数を増やして実験！パターンの発見
数学の基本は「小さな数字で実験すること」です。円盤の枚数 $n$ を $1, 2, 3$ と増やしたときの最小移動回数を観察してみましょう。
- $n = 1$ のとき：杭Aから杭Cへ1枚動かすだけ。 $\rightarrow$ 1回
- $n = 2$ のとき：
- 上の小円盤を杭Bへ（1回）
- 下の大円盤を杭Cへ（1回）
- 杭Bの小円盤を杭Cへ（1回） $\rightarrow$ 3回
- $n = 3$ のとき：
- 上の2枚を杭Bへ移動させる（3回）
- 一番下の最大円盤を杭Cへ移動させる（1回）
- 杭Bにある2枚を杭Cへ移動させる（3回） $\rightarrow$ 7回
回数の並びを見ると、$1, 3, 7, 15, 31 \dots$ と増えていきます。
ここで「おや？」と思った方は鋭いです！ すべて $2^n – 1$ という形をしていますね。
では、なぜこの回数になるのか、漸化式を使って論理的に解明していきましょう。
３．ハノイの塔の漸化式を立てる（立式のロジック）
$n$ 枚の円盤を移動させる最小移動回数を $a_n$ と置きます。
$n$ 枚の円盤を杭Aから杭Cへ移動させる手順は、どんなに枚数が増えても次の3つのステップに集約されます。
🔄 移動の3ステップ
- ステップ1： 上の $(n-1)$ 枚の円盤を、杭Aから作業用の杭Bへ移動させる。
- これに必要な回数は $a_{n-1}$ 回
- ステップ2： 杭Aに残った「一番大きな1枚」を、目的の杭Cへ移動させる。
- これに必要な回数は 1回
- ステップ3： 杭Bに避難させていた $(n-1)$ 枚の円盤を、目的の杭Cへ移動させる。
- これに必要な回数は $a_{n-1}$ 回
これらをすべて足し合わせると、 $a_n$ と $a_{n-1}$ の関係式（漸化式）が完成します！
$$\displaystyle a_n = a_{n-1} + 1 + a_{n-1}$$
整理すると、以下の有名な漸化式が得られます。
$$\displaystyle a_n = 2 a_{n-1} + 1 \quad (a_1 = 1)$$
「$n$ 枚動かすには、$(n-1)$ 枚動かす工程が2回と、一番大きい1枚を動かす1回が必要」という構造が見事に式に現れていますね！
４．漸化式を解く（一般項の導出）
立てた漸化式 $a_n = 2 a_{n-1} + 1$ を解いて、一般項 $a_n$ を求めましょう。
これは「$a_{n+1} = p a_n + q$ 型」の基本形漸化式です。特性方程式を用いて変形します。
💡 特性方程式による変形
特性方程式 $\alpha = 2 \alpha + 1$ を解くと、 $\alpha = -1$ となります。
両辺に $1$ を加えると、次のように変形できます。
$$\displaystyle a_n + 1 = 2 (a_{n-1} + 1)$$
ここで、$b_n = a_n + 1$ と置くと、
- 初項： $b_1 = a_1 + 1 = 1 + 1 = 2$
- 公比： $2$
となり、数列 $\{b_n\}$ は初項 2、公比 2 の等比数列であることが分かります。
数列 $\{b_n\}$ の一般項は、
$$\displaystyle b_n = 2 \times 2^{n-1} = 2^n$$
$b_n = a_n + 1$ であったから、元に戻すと、
$$\displaystyle a_n + 1 = 2^n \implies a_n = 2^n – 1$$
見事、実験で予想した通り最小移動回数の公式 $a_n = 2^n – 1$ が導出できました！
５．【コラム】64枚の円盤を移動させると世界が滅ぶ！？
ハノイの塔には、こんな有名な伝説（インドの神話風フレーバー）が添えられています。
「インドのシュリーランガムにある寺院に、64枚の黄金の円盤と3本のダイヤモンドの針がある。僧侶たちが夜も昼も休みなく、ルールに従って円盤を移し替えている。64枚すべての移し替えが終わったとき、世界は終焉を迎える……」
果たして、世界滅亡までどれくらいの時間がかかるのでしょうか？
公式 $a_n = 2^n – 1$ に $n = 64$ を代入して計算してみましょう。
移動回数は $a_{64} = 2^{64} – 1$ 回です。
⏳ 1秒に1枚動かしたときの時間計算
僧侶たちが不眠不休で「1秒間に1枚」のペースで動き続けると仮定します。
- 1年間の秒数： $60\text{秒} \times 60\text{分} \times 24\text{時間} \times 365\text{日} \approx 3.15 \times 10^7 \text{秒}$
総移動回数（$1.6 \times 10^{19}$ 秒）を1年の秒数で割ると、
$$\displaystyle \frac{1.6 \times 10^{19}}{3.15 \times 10^7} \approx 5.08 \times 10^{11} \text{年}$$
なんと、約 5000 億年 かかります！
※正確な $2^{64}-1 = 18,446,744,073,709,551,615$ 回で厳密に計算しても約 5845 億年となります。
宇宙の現在の年齢が約 138 億年と言われていますから、宇宙の寿命よりも遥かに長い時間です。これなら当分、世界が滅びる心配はなさそうですね。
６．まとめ
今回のポイントを整理しましょう。
- 基本ルール： 小さい円盤の上に大きな円盤は乗せられない。
- 漸化式の立式： $n$ 枚の移動は「$(n-1)$ 枚を避難 $\rightarrow$ 1枚移動 $\rightarrow$ $(n-1)$ 枚を重ねる」の3ステップで $a_n = 2 a_{n-1} + 1$ と表せる。
- 一般項： 特性方程式を用いて解くと $a_n = 2^n – 1$ となる。
- 指数の凄まじさ： $n=64$ になると、移動には数千億年という天文学的数字になる。
一見複雑に見えるパズルも、「手前の状態（$n-1$）を利用して次の状態（$n$）を表す」という漸化式の考え方を使えば、とてもスマートに解き明かすことができます。
高校数学の漸化式で迷ったときは、ぜひこの「ハノイの塔」の3ステップを思い出してみてくださいね！
コメント