一般的河內塔有 3 根柱子。那麼,如果多加 1 根變成 4 根,會怎麼樣呢?規則一樣,一次移 1 個圓盤,不把大圓盤放在小圓盤上,把塔移到另一根柱子。

只多 1 根,步數就大幅減少

能用的放置處多了 1 個,搬開圓盤就輕鬆多了。比較最少步數,圓盤越多,差距就越大。

圓盤個數3 根柱子4 根柱子
3 個7 步5 步
4 個15 步9 步
5 個31 步13 步
6 個63 步17 步
7 個127 步25 步
8 個255 步33 步
10 個1,023 步49 步
64 個約 1.8 × 10¹⁹ 步18,433 步

用 3 根柱子移 64 個圓盤,就算每秒一步也要約 5845 億年(64 個圓盤要花幾年才能移完?)。但如果是 4 根柱子,只要 18,433 步,每秒一步的話約 5 小時。如果傳說中的僧侶多加了 1 根柱子,世界當天就會終結了。

杜德尼的「起司謎題」

廣泛介紹 4 根柱子河內塔的,是英國的益智作家亨利·杜德尼(Henry Dudeney)。他在 1907 年的書《坎特伯里謎題》(The Canterbury Puzzles)中,以「雷夫難題」(Reeve’s Puzzle)的名字出了這道題。Reeve(雷夫)是指莊園的管理人。

在杜德尼的題目裡,不是圓盤,而是在 4 張凳子之間移動 8 塊大小不同的起司。不可以把大起司放在小起司上面。答案是 33 步,和上表中 8 個圓盤的步數一樣。

Frame–Stewart 演算法的解法

用 4 根柱子以少步數移動的方法,是 1941 年由 J. S. Frame 和 B. M. Stewart 分別發表了相同的想法。要移動 n 個圓盤的塔時:

  1. 把上面的 k 個圓盤,用全部 4 根柱子,移到想移去的柱子以外的柱子。
  2. 把剩下的 n−k 個圓盤,不用 k 個圓盤所在的那根柱子,只用 3 根柱子移到想移去的柱子(2ⁿ⁻ᵏ−1 步)。
  3. 把在 1 搬開的 k 個圓盤,用全部 4 根柱子,移到想移去的柱子。

分成這三件事。1 和 3 都是同一個問題的小版本,所以可以用遞迴的想法(演算法的文章)。剩下的,就只是選上面要留幾個(k 個)時步數最少。8 個圓盤的話,先搬開上面的 4 個或 5 個步數最少,是 33 步。

近 100 年都沒被證明的「最少」

用 Frame–Stewart 的方法能用少步數移動,這件事已經知道了。但是,有沒有比這更少的方法,很長一段時間沒有人能證明。

3 根柱子的話,只要靠「移動最大圓盤的瞬間,其他圓盤必須全部集中在 1 根柱子上」這一個事實,就能馬上證明最少步數(最少步數公式)。到了 4 根柱子,移動大圓盤的瞬間,其他圓盤要怎麼分在剩下的 2 根柱子上都可以,所以可以想到的走法一下子就變多了。

用電腦調查所有的擺法,確認了到 30 個左右的圓盤,這個方法都是最少的。然後在杜德尼出題的大約 100 年後,2014 年,法國數學家蒂埃里·布施(Thierry Bousch)證明了不論有幾個圓盤,Frame–Stewart 的方法都是最少的。至於 5 根以上柱子的情況,據說到現在都還沒有被證明。

自己也能試試

4 根柱子的河內塔,用製作方法的文章裡的厚紙做法,把放置處的圓圈改成 4 個就能做出來。試試看能不能用 5 步移動 3 個圓盤,用 9 步移動 4 個圓盤。可以用身體感受到和 3 根柱子時的差別。