[其他] 河內塔, 從三棍到四棍
幾個月前我隨意翻著期刊, 赫然發現 "四根棍子河內塔最佳解" 這個高懸已久的問題居
然已經解決了. 知識增加得太快, 真是窮盡一生之力也難以追逐. 河內塔是國內許多師生
都熟悉的題材, 也是科展的熱門問題, 因此在此介紹這個 (已經沒有滾燙新) 的進展.
---------------------------------------------
河內塔 (Tower of Hanoi) 是法國數學家 Lucas 於 1883 年設計的謎題. 共有三根棍子
, 第一根棍子有若干個由小到大的圓盤套著. 每一步移動一個圓盤到另一個棍子, 但是規
則是大圓盤都不可以在較小圓盤的上面.
市面上可以買到各式各樣的河內塔玩具. 讀者沒有玩過的話可以試試看三個圓盤的情形,
一共需要七步可以完成.
這個謎題帶有一個浪漫的神話故事: 傳說中印度的某個廟宇中有個 64 盤的河內塔, 只
要僧侶完成了此河內塔, 世界就會毀滅.
---------------------------------------------
每一本離散數學或是程式設計的課本都一定有介紹河內塔, 因為這是遞迴解題的經典範
例. 如果有 n 個圓盤, 完成河內塔的移動最少需要幾步呢?
假設移動完 n 個圓盤最少需要 a(n) 步. 一開始所有的圓盤都在第一棍, 目標是全移到
第三棍.
思考一下, 把最大的圓盤從第一棍移到第三棍的當兒, 其他的圓盤都要先讓位清空到第
二棍才有可能. 因此完成河內之塔必須要以下的三大階段 (而且也只能這樣解決):
[A]. 把第 1 棍的前 n-1 個圓盤放到第 2 棍
[B]. 把第 1 棍的最底下的圓盤放到第 3 棍.
[C]. 把第 2 棍上的 n-1 個圓盤放到第 3 棍.
第一個階段不過就是少一個圓盤的河內塔問題, 所以最少需要 a(n-1) 步. 第二個階段一
步即可, 第三個階段一樣最少需要 a(n-1) 步. 因此完成 n 個圓盤河內塔最少一共需要
a(n)=2a(n-1)+1
步. 加上顯然的 a(1)=1, 可解出這個遞迴方程的解為
a(n) = 2^n-1.
n=3 的時候的確答案為 7 步. 至於世界會不會毀滅, 我們就可以放心了. 即使那些
印度的僧侶知道解法且一秒能移動一個圓盤, 完成 64 個圓盤的河內塔也要 2^64-1 秒
, 約 58 萬億年.
----------------------------------------------
四根棍子的河內塔問題首先出現在謎題大師 Dudeney 在 1908 年出版的坎特伯利謎題
集 (The Canterbury Puzzles) 上, 也叫做 Reve 問題. 1939 年美國數學月刊 (American
Mathematical Monthly) 把求 p 根棍子 n 個圓盤當作一個徵答問題, 問在這個狀況下完
成河內塔的最佳解 (最少步驟) 為何. 幾個月後, 出題的 Stewart 和投稿的 Frame 分別
提供了解答.
Frame 與 Stewart 提出的演算法基本上相同, 模仿三根棍子的解答:
[A']. 把第 1 棍的前 L 個圓盤放到第 2 棍
[B']. 把第 1 棍最底下的 n-L 個圓盤放到第 p 棍.
[C']. 把第 2 棍上的 L 個圓盤放到第 p 棍.
對於每個介於 1 到 n-1 的每個 L, 按照這個方式可以分別得到移動的步數 (共有 n-1
個值). 則這 n-1 個值中的最小值就是最少移動步數. 用數學式子寫, 令 a(p,n) 表示完
成 p 根棍子 n 個圓盤河內塔所需的最少步數, 就有
a(p,n) = min (2a(p,L) +a(p-1,n-L)).
L= 1...(n-1)
因為三根棍子河內塔的鼓勵, 模仿三根棍子河內塔的解決方式是正常的思考. 上述的演
算法相當自然, 我們的直覺也告訴我們這應該是對的.
--------------------------------------------------------
但問題沒有這麼簡單. 期刊的編輯看出了這個解答非常微妙的漏洞: 它已經預設了這樣
的移動模式會得到最佳解. 但是不是這樣移動 *真的* 可以得到最佳解? 卻沒有證明.
直覺最佳不一定是真的最佳. 一個簡單的例子是所謂的背包問題, 假設你有一個可以裝
十公斤的包包, 要撿石頭總重愈重愈好. 正常的直覺是貪心演算法: 先撿最大的, 在裝得
下的情況下再檢最大的 ...以此類推. 但這是錯誤的直覺:
如果有四個石頭重量是 5,3,3,3, 則貪心演算法只能得到總重 5+3=8, 但是事實上可以
裝到 3+3+3=9.
Frame 與 Stewart 的演算法的微妙漏洞在哪裡? 棍子多了, 圓盤的移動就有非常多的選
擇, 你怎麼知道最少的步數 *一定* 是經由這樣的方法產生呢? 第一階段 "把第 1 棍的前
L 個圓盤放到第 2 棍" 就有大問題, 誰告訴你要得到最佳解一定要先將前 L 個圓盤聚在
第 2 棍呢? 既然棍子多了, 圓盤的移動選擇就多了, 沒有什麼道理一定要聚在同一根棍子
吧. (注意原始三根棍子的狀況不會有這樣的迷惑).
--------------------------------------------------------
但是, 如果你用電腦模擬, 把所有移動方式暴力搜尋過, 會發現神奇的是按
Frame-Stewart 演算法還真的都得到最少移動步數.
這就是著名(或是惡名昭彰) 的河內塔大難題:
Frame-Stewart 猜想: 用 Frame-Stewart 演算法所求出的步數
真的是完成河內塔的最少步數.
這個問題到現在已經七十幾年了, 其中有許多的論文研究, 但基本上都是只能改良最佳
步數的上下界. 直到 2014 年終於有個突破出現, 數學家 Bousch 終於 *前進了一步*.
他證明在 *四根棍子* 的時候, Frame-Stewart 演算法的確得到了最佳解.
Bosch 的論文奇怪的是沒有引起太大的騷動, 一個原因可能是發表在一個不太起眼的期
刊 "比利時數學學會學報", 而且是法文寫的. 數學界或資訊界或許更期待的是有沒有
"一勞永逸" 的解, 一次證明或反證 Frame-Stewart 猜想.
但無論如何這是一個大突破. 如果你從四棍問題最早出現的 1908 年算起, 從三根棍子
到四根棍子, 整整花了一百年.
--------------------------------------------------------
最後講一點題外話: 歷來台灣國內科展有多組作品前仆後繼, 想要解決類似多根棍子河
內塔的有名初等問題, 我擔任評審多年, 看學生花了大量的時間做白工, 常常於心不忍.
貌似初等的問題能殘留數十年甚或數百年到現在, 想必都是非常困難. 學生有企圖心想要
解決大問題是好事, 但是教師更要適時提供問題背景, 深度與現況, 以免無功而返. 肯靜
下心來作探索的學生愈來愈少, 更要好好珍惜.
2017, 森棚教官
--
*********************************
* 雄壯 威武 嚴肅 剛直 安靜 堅強 *
* 確實 速捷 沉著 忍耐 機警 勇敢 *
* 我是教官 教官是我 *
* 每個人都記嘉獎一支 *
*********************************
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.122.140.77
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1488468843.A.205.html
推
03/03 00:00, , 1F
03/03 00:00, 1F
推
03/03 00:04, , 2F
03/03 00:04, 2F
推
03/03 01:33, , 3F
03/03 01:33, 3F
推
03/03 01:43, , 4F
03/03 01:43, 4F
推
03/03 02:52, , 5F
03/03 02:52, 5F
推
03/03 04:21, , 6F
03/03 04:21, 6F
推
03/03 05:58, , 7F
03/03 05:58, 7F
推
03/03 09:15, , 8F
03/03 09:15, 8F
推
03/03 10:07, , 9F
03/03 10:07, 9F
推
03/04 14:23, , 10F
03/04 14:23, 10F
推
03/04 20:50, , 11F
03/04 20:50, 11F
推
03/05 14:03, , 12F
03/05 14:03, 12F
推
03/06 01:14, , 13F
03/06 01:14, 13F
推
03/08 19:02, , 14F
03/08 19:02, 14F
→
03/09 22:47, , 15F
03/09 22:47, 15F
推
03/16 08:15, , 16F
03/16 08:15, 16F
→
03/22 09:39, , 17F
03/22 09:39, 17F