- 專欄
文章專區
2017-04-01河內塔，從三棍到四棍
568 期
Author 作者
游森棚／任教於臺灣師範大學數學系及空軍官校。
圖一：河內塔。（作者提供）
幾個月前我隨意翻著期刊，赫然發現「4根棍子河內塔最佳解」這個高懸已久的問題居然已經解決了。知識增加得太快，真是窮盡一生之力也難以追逐。河內塔是國內許多師生都熟悉的題材，因此在此介紹這個新的進展給讀者。
河內塔（Tower of Hanoi）是法國數學家盧卡斯（Édouard Lucas）於1883 年設計的謎題。共有3根棍子， 第一根棍子有若干個由小到大的圓盤套著。每一步移動一個圓盤到另一個棍子，但是規則是大圓盤都不可以在較小圓盤的上面。市面上可以買到各式各樣的河內塔玩具。讀者沒有玩過的話可以試試看3個圓盤的情形，一共需要7步可以完成（圖二）。
圖二：典型的河內塔玩法。 （作者提供）
這個謎題帶有一個浪漫的神話故事：傳說中印度的某個廟宇中有個64盤的河內塔，只要僧侶完成了此河內塔，世界就會毀滅。
數學中的經典範例
每一本離散數學或是程式設計的課本都一定有介紹河內塔， 因為這是遞迴解題的經典範例。如果有n個圓盤，完成河內塔的移動最少需要幾步呢？
假設移動完n個圓盤最少需要an步。一開始所有的圓盤都在第一棍，目標是全移到第三棍。思考一下，把最大的圓盤從第一棍移到第三棍的當兒，其他的圓盤都要先讓位清空到第二棍才有可能。因此完成河內之塔必須要以下的三大階段（而且也只能這樣解決）：
第一階段：把第1棍的前n-1個圓盤放到第2棍。
第二階段：把第1棍的最底下的圓盤放到第3棍。
第三階段：把第2棍上的n-1個圓盤放到第3棍。
第一個階段不過就是少一個圓盤的河內塔問題，所以最少需要an-1步。第二個階段一步即可，第三個階段一樣最少需要an-1步。因此完成n個圓盤河內塔最少一共需要 an=2an-1+1步。加上顯然的a1=1，可解出這個遞迴方程的解為：
an=2n-1
n=3 的時候的確答案為7步。至於世界會不會毀滅，我們就可以放心了。即使那些印度的僧侶知道解法且一秒能移動一個圓盤，完成64個圓盤的河內塔也要264-1秒，約58萬億年。……【更多內容請閱讀科學月刊第568期】