張貼日期：Dec 05, 2017 4:30:51 AM
作者：郭君逸 副教授（國立臺灣師範大學數學系）
河內塔 (或稱漢諾依塔) 相信大家都不陌生，它是由艾德華．盧卡斯 (Édouard Lucas) 在 1883 年提出的一個數學遊戲，至今已經超過一百年歷史。由於中文名字叫「河內塔」，所以很容易被誤會以為和古老的某條河中或河旁邊的塔有關；另外也有一充滿神秘色彩的傳說，在古印度的某個廟宇中有個 64 盤的河內塔，只要僧侶順利完成了河內塔移動，世界就會毀滅。不知道是怎樣的廟，才會擁有毀滅世界的塔，會不會跟漫威世界裡的至尊魔法師古一有關就不得而知了.....。不過，即使這個傳說是真的，懂一點數學你就知道不用太煩惱 (最後揭曉)。
Domina 木製玩具公司發行的 3 杆 10 圓盤河內塔 (source: http://www.kokaspeles.lv/en)
以 3 杆 3 圓盤河內塔為例，首先全都串在其中一根杆子上，由下到上，依照大到小順序放置，移動的規則如下：
(1) 每次只能移動一個圓盤
(2) 任何時候，大的圓盤不能疊在小的上面
而遊戲目的是要所有的圓盤，依照此規則，移到另一根杆子上。
3 杆 3 圓盤河內塔不會太困難，很適合初學者動手玩一玩。下圖展示了從第 1 根杆子移到第 3 根杆子最少移動次數的方法。
photo author: Tamara Smyth
7 步就可以移動完了。這裡要提醒讀者的是，河內塔的移動方式並非一定要如此，如果不積極前進甚至往反方向走，走一步退兩步，當然有可能退步一百年！
除了畫出移動的示意圖之外，數學家想到了一種合適的語言能夠描述河內塔各種狀態及移動的關係。先把三根杆子編號為 a、b、c，圓盤由小到大編號為 1、2、3，若 3 個圓盤都放在 a 杆的話，就把這種情況記為「aaa」，若 1 號圓盤在 c 杆，2、3號圓盤都在 b 杆，就記為「cbb」。而 n 個圓盤 3 根杆子的河內塔的所有情況有 3n 種情況，藉助圖論為語言，把每一種情況當作一個點，若移動一個盤就能兩者互通的話，就把兩點連一條邊，如此則形成所有狀態及其關聯的圖。以 3 個圓盤 3 根杆子為例，27 個點的圖如下：
Source: wikimedia commons, photo author: Nonenmac
有了這張圖就等於在諾大的迷宮裡撿到了地圖，「若想 3 個圓盤從 a 杆移到 c 杆」就是由「aaa」點，走到「ccc」點，目視知道直接一路朝右下走就是最短路徑 7 步解。
3 杆 n 盤河內塔最佳解證明
有了 3 杆 3 圓盤的結果當基礎，很容易就能推進到 3 杆 n 盤的情況，提出一般解的猜測。不過，這個運用數學歸納法的證明看似簡單，其實暗藏了一些陷阱，一不小心就容易掉進去。關鍵之處我畫紅底標示出來。
定理1：三根杆子 n 圓盤的河內塔，最少步數為 2n-1 步。
證明想法：假設目標是將圓盤從 a 杆移到 c 杆。接下來對圓盤數 n 做數學歸納法。很明顯，一個圓盤時只需要一步，正確。
假設 n=k 個圓盤時，最少步的移法是 2k-1 步。
當 n=k+1 時，我們關注第 k+1 號盤，假設第 k+1 號盤在整個過程中移動了 s 次。
第 k+1 號盤每次移動前，第 1 號到第 k 號盤，必定要全移到 b 杆(最少花 2k-1 步)；
然後移動第 k+1 號盤後，再把第 1 號到第 k 號盤移到第 k+1 號盤上(最少花 2k-1步)，
加起來恰 s(2k-1)+s+(2k-1) = (s+1) 2k-1 步。
而 (s+1) 2k-1 是一個隨 s 遞增的函數，所以 s=1 時達最小值，即為 2k+1-1 步。
從上面的證明，可以知道，最大的圓盤，只會移動一次。就是大家熟知的那種移法。然而不少人論證時就直接當作最大圓盤只會移動一次，卻沒有說明原因，嚴格說來邏輯是錯的，卻因為「2n-1」這個數字是正確的，所以不容易發現問題所在，這也是「數學歸納法」常常被誤用而沒發覺的原因。但若同一命題若把 2n-1 換成別的數字，就會發現剛才寫錯的人依然能完成證明，這時就露餡了。
河內塔研究再下一城
數學家對河內塔的研究熱情持續了一百年，近幾年還不斷地有新的論文發表。史塔克梅爾 (Stockmeyer) 整理了在 1883 年到 2005 年間所有關於河內塔的論文，高達 369 篇。在這些年之間也多了不少變型，比較常被討論的有：
1. 循環模型 (Cyclic)：杆子排成環狀，圓盤在移動時，只能順時針相鄰移動。
2. 磁鐵模型 (Magnetic)：圓盤有南北兩極，每次移動要翻面，同極相斥的話就不能移。
3. 雙色模型 (Bicolor)：每號圓盤都有黑白兩個，除了小的在大的上面外，若同大小，還要黑的在白的上面。
4. 多杆模型 (m-pegs)：m 根杆子的模型，近幾年來論文主要討論這種模型。
最早提出多杆模型的是亨利．恩尼斯特．道得尼 (Henry Ernest Dudeney) ，在 1908 年首先提出 4 根杆子的模型，當時稱為「Reve's Puzzle」。後來 1939 年史都華 (B. M. Stewart) 在美國數學月刊 (American Mathematical Monthly) 中介紹了 m 杆 n 盤河內塔問題，不久，史都華自己提出了解答，同一時間福潤 (J. S. Frame) 也提出了 m 杆 n 盤的解答，兩個人用類似的方法：假設 m 杆 n 盤的最少步為函數 f(m,n) 表示，
l 先將前 t 盤利用 m 杆移到第 2 杆，花 f(m,t) 步；
l 再將後 n-t 盤利用 m-1 杆移到最末杆(因為此時第2杆無法用)，花 f(m-1,n-t) 步；
l 再將前 t 盤利用 m-1 杆從第2杆移到最末杆，花 f(m,t) 步，即完成。
加起來總共是 2f(m,t) + f(m-1,n-t) 步。但是 t 多少才使這算式最少不知道，所以要把所有情況都試過，取最小值，因此答案為：
這個函數太有名，後來被稱為福潤-史都華數 (Frame-Stewart numbers)，學界的人也普遍認為福潤-史都華數就是最佳解。不過就在這兩位學者以為證明了 m 杆 n 盤的最少步數解法時，在他們的證明中很快就被發現有一嚴重缺陷，即是都沒有說明為何這樣是最少。
我們回過頭來檢驗一下，第一階段「先將前 t 盤利用 m 杆移到第 2 杆」就很可疑，誰說這樣就是最好的呢? ３杆的情況下這樣做的確是必要的，因為總得留一根空杆子讓最大的圓盤移動，因此就必須把前面較小的盤全部都移到某一杆。但是在多杆情況下，杆子變多了，那麼圓盤暫放的選擇就多了許多，把前 t 盤移到同一個杆子看起來沒什麼特別的好處。後來有人用電腦窮舉驗證，發現 30 個圓盤內，f(4,n) 都是對的。
現在的 3D 印表機非常流行，有興趣的讀者可以印一個 4 杆的河內塔出來玩，上圖是筆者在 2017 年的 Taiwan Puzzle Community 年會設計的 4 杆河內塔紀念品，附 8 個圓盤。在此考考各位，4 杆 8 盤的河內塔，要從一根杆子移到另一根，最少是幾步呢？好了，不賣關子，答案是 33 步。當天幾位益智玩具高手試玩了一下，大多都五十幾步，最佳紀錄是 42 步，離 33 還差了不少，由此可見其難度。
有興趣的讀者可以動手算一下 f(4,8) 是不是等於33？計算過程恰可以看出移動方法喔！
福潤-史都華猜想：福潤-史都華數就是河內塔的最佳解。
自 1940 年代往後數十年，「證明福潤-史都華數就是最佳解」成為河內塔界最高大的巨塔，等著被眾人扳倒。不過，征服這座巨塔並非塔尖上功德，這麼多年來進展不多，比較有意思的結果是 2002 年 Klavžar 等三人首先把文件中常提出的 m 杆 n 盤移動方法歸納出 7 類，然後證明這些移法雖看起來不同，但實際移動方式本質上是相同的。真正的突破性進展發生在 2014 年，法國數學家布希 (Thierry Bousch) 用一個嶄新的方法，證明福潤-史都華猜想在 4 杆的正確性，不過，他的論文並沒有在第一時間引起學界注意，可能是因為論文刊登在一個非主流的地區型期刊上，而且用的語言是法文，提高了閱讀門檻。雖然布希的結果僅限於 4 杆，卻是河內塔研究七十年來最大的突破。
布希的論文摘要，內文是用法文寫的。
布希的論文主要就是用新的方法提供了四杆河內塔最少移動數一個更好的下界，剛好符合福潤-史都華數，之後不久，德國數學家 Codrut Grosu 藉助布希的想法又進一步推升五杆以上河內塔的最少移動數下界，只是這個下界在五杆以上並沒有觸碰到福潤-史都華數，換句話說，上下界之間還有一些差距。
最多步數的移法
有最少步的走法，很自然就會有人研究最多步的走法。這裡講的「最多步」指的是「不重複的最多步走法」，也就是狀態不能重複。這有一個很天然的天然上界，既然不能重複，那所有的狀態數少一 3n -1 就是極限了 (討論 3 杆 n 盤的情況)。這個數量能不能達到呢？答案是可以的。下面就是 3 圓盤從 aaa 移到 bbb 的最多步走法：
Source: wikimedia commons, photo author: Nonenmac
眼尖的讀者應該發現這是圖論的著名問題，在圖中找一條通過所有頂點的漢米爾頓路徑 (Hamiltonian Path)。
定理2：三根杆子 n 圓盤的河內塔，最多不重複步數為 3n -1 步。
這個證明一樣是對 n 做數學歸納法，把其對應的圖形切成三個小一號的子圖，各自找出路徑後接起來即可，在此省略其細節。
河內塔與九連環有關
益智玩具九連環 (source: wikimedia commons)
值得一提的是，3 杆河內塔的最少步數移法，其實跟九連環解法是相同的，我們可以把九連環中各種與格雷碼有關的定理拿來用。將九連環由外而內編號為 1 號環，到 9 號環，而九連環從全部的環都拿出來的情況下，一一放回去所動到的環依序是
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,…
很巧的是 3 杆的河內塔，不管幾個圓盤，最少步移動的圓盤編號，剛好也是這個數列，兩者之間存在一一對應的關係。因此，我們可以計算第幾步是動第幾號盤(環)，舉例來說第 20 步該動幾號盤，可藉由 40 = 23 x 5，因為 2 的指數是 3，所以是動 3+1 = 4 號盤(環)。
除此之外，還可以利用格雷碼計算出下面 3 杆 n 盤河內塔的答案：
l 任給一個的狀態，都可以計算出幾步可以解出、該動第幾號盤。
l 隨便給個步數 k，可以擺出所有 k 步可移好的狀態。
l 任給兩個狀態，可計算最少幾步可移至另一狀態，該動第幾號盤。
有興趣的讀者，可以參考數學傳播 38 卷 3 期「九連環與格雷碼」一文，裡面的結果都可以對應到 3 杆河內塔的結果。
世界毀滅的傳說不要怕
前面我們已經知道，3 杆 n 盤的河內塔最佳解是 2n- 1 次移動，64 個盤就是 264 - 1 步，這個數字是 18446744073709551615，假設僧侶像奇異博士擁有強大魔法每一秒可以完成 3000 次圓盤移動，而且想要加班毀滅世界即使一天上工 24 小時每週七天也沒有過勞問題的話，要完成 64 盤的河內塔也要耗費大約 150 億年，依據目前最潮的理論估計，宇宙年齡也不過 137 億年左右，我想應該沒什麼好擔心的。
最後，筆者給大家兩個結語：第一、數學歸納法使用要小心，因為常會犯錯而不自知。第二、河內塔真的不簡單啊！前陣子有不少科展作品研究河內塔，其中不乏證明 4 杆模型的最佳解，甚至是 m 杆的最佳解，最後都徒勞無功。這個問題看起來雖然很容易，但是歷經一百年來多少數學家寫了許多論文仍未能解決，可想而知相當困難。一直到 2014 年才被布希用了新方法把 4 杆的情況解決。在此建議對此有興趣的老師或同學，除非有創新的、聰明的方法，否則別再想對「最少步」問題動腦筋了，不然可能做到畢業也沒有結果，做了白工不打緊，怕是傷害了學生的研究信心可就不好。如真有興趣，或許可考慮從「性質」上著手，例如任意給個狀態，幾步可解出、動哪個盤之類的。當然，光是這之前三百多篇的文獻探討，就夠累的了。
延伸閱讀