ハノイの塔には、こんな伝説が添えられています。インドのある寺院に、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枚なのも、そのためです。