圖1
羅浩源 顯理中學
蕭文強 香港大學數學系
『廟前的空地豎立了三支柱，位向正東方的一支疊放著六十四塊金片，在
斜陽的照耀下閃閃生輝。大大小小的金片，排列有序，由上至下，金片一層
一層增大。此際，但見方丈運起內力，金片在三支柱間穿梭飛舞。大師對眾
徒說：每發一掌，須把一塊金片移到其餘兩支柱上，任擇其一。但須謹記，
大金片不可壓在小金片上，以免走火入魔。等到六十四塊金片全部移到位於
正西方的柱上，你的內力已臻登峰造極，可以下山了。』
每逢講解「數學歸納法」這個課題，上述的傳奇式故事總有機會流傳開
來。從學生的眼神中看得出他們還是喜歡這個經典數學遊戲 ── 「河內塔」
(TOWER OF HANOI)」── 經渲染了的「武俠小說版本」。「河內塔」這個
玩意，最先大扺是在1883年的巴黎流傳。當時市面上銷售的版本上面署名發
明人是 N. CLAUS (DE SIAM)，看來是 LUCAS D'AMIENS 的化名，因此有人
認為那其實是法國數學家 EDOUARD LUCAS (1849-1891) 想出來的玩意。當
時適值法國開始覬覦安南(今之越南),進軍當地，河內這些地名不時出現在法
國報章上，可能這個玩意便以此命名吧。
這個遊戲珍貴之處，在於讓學生在過程中尋找規律，也可以從過程中體會
到「數學歸納法」的精神。不少學生只掌握了「數學歸納法」較機械化的一
面，那其實是純粹演繹 (DEDUCTION) 而非歸納 (INDUCTION)。他們以為只
要把已知的公式對 和 的兩種情況寫下來，由前者推算出後者(再
加上驗算 的情況)，就算是學懂了「數學歸納法」。很少學生想到如何基
於「數學歸納法」的精神去發現答案，就是運用倒推的手法，把問題一步一
步化簡。（因此，那亦不是純粹歸納而已，雖然有時歸納可以導致合理的猜
測。）
以下是一次師生對話的節錄：
教師：尋找規律，可從一些簡單情況入手。
甲生：明顯地，1塊金片只需1步。【拿了二塊移動。】用3步可以把2塊金片
移往另一支柱上。
【片刻間，該生已發現用7步可以完成3塊金片的移動。大家花了不少時間才
能確定分別以15步和31步可以完成4塊和5塊金片的移動。】
教師：相信大家已開始感受到移動大量金片所需的耐力吧！你們還有沒有興
趣繼續移動6塊金片呢？
乙生：還是留待晚上睡不著才做吧！從這些獲得的結果。是否足以找到移動
金片的規律呢？
教師：讓我們把這些結果寫下來看一看。【隨即在黑板上畫了以下的表：
| 金片數目 | 移動次數(m) | m + 1 |
| 1 | 1 | |
| 2 | 3 | |
| 3 | 7 | |
| 4 | 15 | |
| 5 | 31 |
【學生在教師的引導下完成下表：
N = 3 的移動情況
| 東柱 | 西柱 | 北柱 | 1,2,3 |
| 2,3 | 1 | (金片1移往西柱) | |
| 3 | 1 | 2 | (金片2移往北柱) |
| 3 | 1,2 | (金片1移往北柱) | |
| 3 | 1,2 | (金片3移往西柱) | |
| 1 | 3 | 2 | (金片1移往東柱) |
| 1 | 2,3 | (金片2移往西柱) | |
| 1,2,3 | (金片1移往西柱)】 |
丙生：啊!原來移動7步中，金片1、2、3的移動次數分別是4、2、1。【該生馬
上試完成 N = 4 的移動過程。】 果然不出所料，移動4塊金片，金片
1、2、3、4 的移動次數分別是 8、4、2、1。我們只須移動最大的金片1
次，但卻要把最小的金片移動8次。把最大的金片移動那一次後，問題不 就
是化為移動3塊金片的情況嗎？
教師：非常有意思！你們現在可以解釋移動 塊金片的公式嗎？能否先把問
題從 N 片化成 N - 1 片的情況去處理呢？
【眾學生繼續興高彩烈地討論,還得到更細緻描述移動金片的辦法，大家還估
計了移動六十四塊金片所需的時間，此處不贅。】
現在讓我們看看如何證明需要移動 (至少)2 - 1 次把 N 塊金片從東柱移
到西柱。通常書本上作以下的解釋：
設 是移動(至少)次數，不難明白f(1) = 1 。接著嘗試把 f(N) 和
f(N-1) 的關係找出來。先把上面N - 1 塊金片從東柱移到北柱，用了 f(N)
步，再用一步把第N 塊金片從東柱移到西柱，然後把那 N - 1塊金片從北柱移回到西柱第
N塊金片上面，又用了f(N - 1)步。合起來共用了 2f(N - 1) +1步，於是 2f(N - 1) +1
由此不難算出
| f(N) = | 2f(N-1) + 1 = 2² f(N - 1) + 2 + 1 |
| = | 2 ³ f(N-3) +2 ² + 2 + 1 = :( |
| = | 2 f(1) + 2 + :( + 2² + 2 + 1 |
| = | 2 + 2 + :( + 2² + 2 + 1 = 2 - 1 |
【也可以用「數學歸納法」直接證明，那是假定已知公式為 f(N) = 2 - 1 。】
仔細審視上述的解釋，你便察覺它只證明了不等式 f(N)< 2f(N - 1) + 1 , 也
就是只證明了f(N) <2 - 1吧。我們還欠一步，即是證明
。幸好這一步容易看出來，只用注意一點：要把最底第f(N)> 2f(N - 1) + 1
塊金片從東柱移到西柱之前，必須把較小的N - 1塊金片全部移到北柱去。要
這樣辦，至少已經用了f(N - 1)步。把那N - 1塊金片從北柱移到西柱，又至
少用了f (N-1)步，所以f(N)> 2f(N - 1) + 1 。
後面補充的一段話，通常給忽略掉，也許因為只有三支柱，這回事像明顯
不過。假如有四支柱，不等式便不明顯了，而且那其實是錯的！假如有四支
柱，仍然設 是移動(至少)次數。固然，我們仍然有f(N)=1 和f(N)< 2f(N - 1) + 1
，因此仍然有f(N)< 2 - 1 。但這次真正的f(N)和2 - 1
相差可能不少。舉一個簡單情況為例，有3塊金片和東、南、西、北四支柱，
已經知道f(3)< 2³ - 1 = 7 ，但其實移動5次已足夠，而且 真的是5，不是
7(見下面的表）。
| 東柱 | 南柱 | 西柱 | 北柱 |
| 1,2,3 | |||
| 2,3 | 1 | ||
| 3 | 1 | 2 | |
| 1 | 3 | 2 | |
| 1 | 2,3 | ||
| 1,2,3 |
讀者不妨試計算 f(4) 和 f(5) 。一般而言，N塊金片和K支柱的「河內塔」
需要移動(至少)多少次，似乎仍然是一個懸疑未決的問題呢。
梵塔的傳說包含著多姿多采的數學內容，在教師的適當引導下，學生在遊 戲過程中自當體驗到尋覓數學規律的樂趣。
