河內塔有一個這樣的傳說:在印度的某座寺院裡,有一座疊著 64 個金圓盤的塔,僧侶們正照著規則不斷移動圓盤。當所有圓盤都移完的時候,世界就會終結……

那麼,要移完 64 個圓盤,到底需要多久呢?

最少也要 2⁶⁴−1 步

圓盤有 n 個時,最少步數是 2ⁿ−1 步(原因請看最少步數的文章)。64 個圓盤的話,

2⁶⁴−1 = 18,446,744,073,709,551,615 步

約為 1.8 × 10¹⁹ 步,也就是 1 兆的 1845 萬倍。

如果每秒移動一步

假設僧侶不休息,每秒移動一步,而且一次都不出錯。把 1 年當作約 3155 萬秒(365.25 天)來除,

18,446,744,073,709,551,615 秒 ÷ 31,557,600 秒 ≒ 5845 億年

需要這麼久。

拿來比較的對象年數
以每秒一步的速度移完 64 個圓盤約 5845 億年
從宇宙誕生到現在約 138 億年
從地球誕生到現在約 46 億年

大約是宇宙年齡的 42 倍。就算傳說是真的,似乎也不必擔心世界末日。

如果交給電腦呢

假設不靠人手,而是用每秒能計算 10 億步的電腦來走完整個步驟。即使這樣,

18,446,744,073,709,551,615 ÷ 1,000,000,000 ≒ 184 億秒 ≒ 約 585 年

還是要花這麼久。每一步的走法明明非常簡單,但圓盤一增加,步數就會成倍成倍地增加。這就是「以指數成長」的一個很好懂的例子。

用手玩的話最多到幾個?

以每秒一步來走,就算是最少步數,也需要下面這些時間。

圓盤個數最少步數每秒一步所需時間
7 個127 步約 2 分鐘
10 個1,023 步約 17 分鐘
15 個32,767 步約 9 小時
20 個1,048,575 步約 12 天

利用空檔玩的話,7 個左右剛好是適合的長度。App「河內塔」的「經典」模式用 7 個圓盤,也是這個原因。