九章出版社 提供
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年，也沒有一種生物能活這麼久，所以我們大可放心的睡覺。
準備一張卡片，剪成8個大小不一樣的正方形紙片，將它們由上至下由小而大的堆起來。
接著在紙片上(另一張紙板上)點上三個點，並將8張紙片所組成的紙堆放在其中的一點。現在就可以開始動動手試試看了，至少須要幾次的移動才能將紙堆移到另一個點上呢？
答案是 
次。
若像金字塔遊戲一樣將三根木釘排成一個三角形(即木釘在三角形的頂點)。假設，移動金屬片的方式被分為順時針方向及逆時針方向，每做一次順時針方向移動，我們在紙上劃上＼，做一次逆時針方向則劃上／，若令出發點為 A 柱，終點為 C 柱。逐步記錄結果：
當我們對更多片金屬片操作時可以發現： n片金屬片所構成的移動圖形，恰好是 n-1 片金屬片所構成的圖在鏡子內所呈現的圖形做複製及平移，中間再加上一段「\」符號。
歸納這個現象，也可以證明出遞迴關係式 T(n+1)= 2T(n) + 1，所計錄的每一筆畫恰巧是移動一次的記錄。對於這些結果，您能不能找出更多有趣的現象？
下列網站有河內塔的電腦遊戲及相關資料：
http://www.pangea.ca/kolar/javascript/Hanoi/HTonWebE.html
http://www.math.toronto.edu/mathnet/games/towers.html