2017年3月29日

河內塔,從三棍到四棍

作者/游森棚,任教於臺灣師範大學數學系及空軍官校。
圖一:河內塔。(作者提供)
幾個月前我隨意翻著期刊,赫然發現「4根棍子河內塔最佳解」這個高懸已久的問題居然已經解決了。知識增加得太快,真是窮盡一生之力也難以追逐。河內塔是國內許多師生都熟悉的題材,因此在此介紹這個新的進展給讀者。

河內塔(Tower of Hanoi)是法國數學家盧卡斯(Édou-ard 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期】



沒有留言: