河內塔－藍色情懷

河內塔 (Tower of Hanoi)

九章出版社　提供

一、河內塔的起源

　　1883年，一位法國的數學家 Edouard Lucas 教授在歐洲的一份雜誌上介紹了一

個相當吸引人的難題──迷人的智力遊戲。這個遊戲名為河內塔(Tower of Hanoi)，它源自古印度神廟中的一段故事(也有一說是 Lucas 教授為增加此遊戲之神秘色彩而捏造的)。傳說在古老的印度，有一座神廟，據說它是宇宙的中心。在廟宇中放置了一塊上面插有三根長木釘的木板，在其中的一根木釘上，從上至下被放置了64片直徑由小至大的圓環形金屬片。古印度教的天神指示祂的僧侶們將64片的金屬片移至三根木釘中的其中一根上。規定在每次的移動中，只能搬移一片金屬片，並且在過程中必須保持金屬片由上至下是直徑由小至大的次序，也就是說不論在那一根木釘上，圓環形的金屬片都是直徑較小的被放在上層。直到有一天，僧侶們能將64片的金屬片依規則從指定的木釘上全部移動至另一根木釘上，那麼，世界末日即隨之來到，世間的一切終將被毀滅，萬物都將至極樂世界。

　　倘若這個故事的敘述為真，那麼，我們只需加速移動金屬片，是不是就能愈早到達極樂世界呢？果真要移動這64片金屬片，那麼，至少要花幾次的搬動才能完成呢？有沒有規律可循呢？

　　1929年，紐約的Knapp Electric 公司據此構想出品了一個新遊戲──金字塔(Pyramid)，故事背景變成在埃及，三根木釘排成三角形，木釘上放置8片圓環形塑膠片，盒內附有每一操作步驟的詳細解答。

二、河內塔的數學
　　就像其他的益智遊戲，對於河內塔遊戲也可以經由數學上的方法得到一些漂亮的結果：若一開始就考慮64片金屬片似乎太難了，我們不妨把金屬片的數量降低至2片，看看會有什麼結果？

　　如果只有1片，顯然只須移動一次即可。當2片直徑不一的金屬片放在同一木釘上，必須將最上的那一片先移至非指定的木釘上，然後將第二片金屬片移至指定的木釘上，再接著將第一片金屬片移至第二片之上，所以，至少要花3次搬移來完成。若是3片金屬片，依相同的討論方法，可得知須至少移動金屬片7 次。

　　當n很大時(金屬片數 = n )，至少要花幾次呢？

　　假設至少須 T(n) 次的移動來完成，那麼，我們再加一片金屬片，即此時共有 n+1 片金屬片；我們知道前 n 片花了 T(n) 次來移動至另一根木釘上，第 n+1 片金屬片只須花一次就可移至指定的木釘上，所以，只須再花 T(n) 次的移動將 n 片金屬片移至這一片金屬片之上，這就完成了任務──有 n+1 片金屬片移到另一根木釘上。它們都是在規範內被完成移動，所以

也就是說64片金屬片至少要經 =18,446,744,073,709,551,615次的搬移才能完成。假如一位熟練的僧侶每秒中搬移一次金屬片，日以繼夜不眠不休的工作，也需要約 584,942,417,355年，這是非常非常遙遠的事，科學家估計地球約已存在2,000,000,000年，也沒有一種生物能活這麼久，所以我們大可放心的睡覺。