ハノイの塔には、こんな伝説が添えられています。インドのある寺院に、64枚の金の円盤を積んだ塔があり、僧たちがルールどおりに円盤を移し続けている。すべてを移し終えたとき、世界は終わる――。
では、64枚を移すには、本当にどれくらいかかるのでしょうか。
最少でも 2⁶⁴−1 回
円盤がn枚のときの最少手数は 2ⁿ−1回です(理由は最少手数の記事で説明しています)。64枚なら、
2⁶⁴−1 = 18,446,744,073,709,551,615回
です。日本語の単位で言うと、約1845京(けい)回。1兆の1845万倍です。
1秒に1手で動かすと
僧が休まず、1秒に1手ずつ、一度も間違えずに動かしたとします。1年をおよそ3155万秒(365.25日)として割ると、
18,446,744,073,709,551,615秒 ÷ 31,557,600秒 ≒ 5845億年
かかります。
| くらべるもの | 年数 |
|---|---|
| 64枚を1秒に1手で移す | 約5845億年 |
| 宇宙が生まれてから今まで | 約138億年 |
| 地球が生まれてから今まで | 約46億年 |
宇宙の年齢のおよそ42倍です。伝説が本当でも、世界の終わりを心配する必要はなさそうです。
コンピューターならどうか
人の手ではなく、1秒に10億手を計算できるコンピューターで手順をたどったとします。それでも、
18,446,744,073,709,551,615 ÷ 1,000,000,000 ≒ 184億秒 ≒ 約585年
かかります。1手ごとの手順はとても単純なのに、枚数が増えると手数は倍々に増えていきます。これが「指数関数的に増える」ということの、分かりやすい例です。
手で遊べるのは何枚まで?
1秒に1手で動かすと、最少手数のままでも次の時間がかかります。
| 円盤の枚数 | 最少手数 | 1秒に1手で |
|---|---|---|
| 7枚 | 127回 | 約2分 |
| 10枚 | 1,023回 | 約17分 |
| 15枚 | 32,767回 | 約9時間 |
| 20枚 | 1,048,575回 | 約12日 |
ひと休みの間に遊ぶなら、7枚前後がちょうどよい長さです。アプリ「ハノイの塔」の定番が7枚なのも、そのためです。
