円盤3枚なら、何回か挑戦すればすぐに成功できます。ところが5枚、7枚となると急に時間がかかるようになり、10枚にもなると、必要な手数は手で数えきれないほどになります。円盤が1枚増えるだけで、どうしてこんなに急に難しくなるのでしょうか？ その答えは、ハノイの塔が「指数関数的に」増えていく問題だからです。
ルールはかんたんです。棒が3本あり、1本目の棒に大きさ順に積まれた円盤を、すべて3本目の棒に移します。条件は2つだけ。一度に動かせる円盤は1枚だけで、小さい円盤の上に大きい円盤をのせてはいけません。円盤がn枚のとき、必要な最少の手数はちょうど2ⁿ − 1回です。1枚なら1回、2枚なら3回、3枚なら7回、4枚なら15回……円盤が1枚増えるごとに、必要な手数はほぼ2倍になっていきます。
なぜちょうど2ⁿ−1回なのでしょう？ n枚を動かすには、まず上のn−1枚（いちばん下の大きな円盤以外すべて）を予備の棒に移します。これだけで2ⁿ⁻¹−1回かかります。次にいちばん下の円盤を目的の棒に移し（1回）、最後に予備の棒のn−1枚を目的の棒に移します（さらに2ⁿ⁻¹−1回）。式にすると (2ⁿ⁻¹−1) + 1 + (2ⁿ⁻¹−1) = 2ⁿ−1 です。このように「大きな問題を、まったく同じ形の小さな問題に分けて解く」考え方を再帰といいます。ハノイの塔は再帰的な考え方を学ぶいちばん有名な例で、プログラミングを初めて学ぶときの定番の題材にもなっています。
このパズルには、インドの寺院にまつわる有名な伝説があります。僧侶たちがこのルールどおりに64枚の金の円盤を動かしていて、それが終わったときに世界が終わる、というものです。64枚の最少手数は2⁶⁴−1回。1秒に1枚ずつ休まず動かしても約5850億年かかり、宇宙の年齢（約138億年）よりはるかに長くなります。この伝説のおかげで、ハノイの塔は指数関数的に増える量がどれほど恐ろしい速さでふくらむかを示す代表例として、よく取り上げられます。
こうした指数関数的な増え方は、ハノイの塔以外でも大切です。一定時間ごとに数が2倍になる細菌や、何回か折るだけでとんでもない厚さになる紙も、同じしくみで動いています。「小さく見えるルールでも、くり返すと想像をはるかに超えて大きくなる」という感覚を身につけるのに、ハノイの塔ほどぴったりな例はなかなかありません。
お子さんと一緒に試すなら、まず3枚を最少手数（7回）で解いてもらい、次に4枚（15回）、5枚（31回）と進めながら、毎回「何回で解けたか」を記録してみてください。円盤が1枚増えるたびに必要な手数が2倍ちょっとに増えることを自分で確かめると、指数関数的な増加という抽象的な考え方が、ずっと実感をもって伝わります。
アクティビティのページでは、円盤3枚から6枚までの難易度を選んで挑戦でき、自分の手数と理論上の最少手数をリアルタイムで比べられます。ぜひ最少手数ぴったりで解くことに挑戦してみてください。