[其他] 河內塔, 從三棍到四棍

[Giawgwan (教官)]

  幾個月前我隨意翻著期刊, 赫然發現 "四根棍子河內塔最佳解" 這個高懸已久的問題居
然已經解決了. 知識增加得太快, 真是窮盡一生之力也難以追逐. 河內塔是國內許多師生
都熟悉的題材, 也是科展的熱門問題, 因此在此介紹這個 (已經沒有滾燙新) 的進展.

---------------------------------------------

  河內塔 (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
推 worcdlo     : 推
推 cutekid     : 大推(Y)
推 RaventheCrow: 推游教官
推 LeonYo      : 睡前看到~ 可以睡個好覺了
推 forget0309  : 推
推 sunev       : 推
推 HeterCompute: 推教官
推 Desperato   : 推推
推 coolbetter33: GOOD
推 c14871083   : 推教官
推 TassTW      :  教官要不要寫本 "科展不要做的五十個問題" ?
推 Desperato   : 推樓上XD
推 THEJOY      : 推教官
推 dorminia    : 驚居然被解了！
→ Giawgwan    : 的確吃驚. 該證明有 Knuth 加持, 應該是對的.
推 snaredrum   : 請問教官 Knuth的加持寫在哪裡?
→ Giawgwan    : MAA Math Mag Dec'16, p.387, 編輯提及 Knuth 評註