要移動 n 個盤,必須先把上面 n − 1 個挪開,再把最大的那一個走一步,然後把那 n − 1 個整個疊回它上面。於是 M(n) = 2M(n − 1) + 1 且 M(1) = 1,解出來就是 2ⁿ − 1:八個盤 255 步,三個盤 7 步,即前兩個連結。255 這個數字對讀記憶體容量的人並不陌生——無符號位元組的最大值正是它,理由也完全一樣。
盧卡斯那一版附帶六十四金盤和一個預言:等塔移完,世界就到盡頭。每秒一步,這是 2⁶⁴ − 1 = 1.844674407371⋅10+19 步(第三個連結),約五千八百五十億年,比宇宙年齡的四十倍還多——而擺在你面前的八個盤一分半鐘就能移完。讓小題變得無聊、大題變得地質年代的,是同一條翻倍規則:255 與 1.844674407371⋅10+19 之間沒有第二種演算法,只隔六十次。
答案
255
口徑說明
工作台上的 2⁸ − 1。第二個連結是三個盤,第三個是會讓世界終結的六十四個盤。
出處
Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1
在計算機裡做這道題
下面的連結直接開啟對應的計算機,並把這道題的數字填進屏幕——答案就是上面那一行,可以自己核對。