漢諾塔雜談（六）——變體之「循環移動」

來自專欄 Liu言雜記4 人贊了文章

（抱歉更新速度很慢，因為學生的畢業季有很多事情要處理。）

所謂「循環移動」 就是在原始的漢諾塔問題（參看「漢諾塔雜談（一）」）上增加一個要求：

設A柱、B柱、C柱（及A柱）構成一個順時針方向的三角形，

所有的移動必須是順時針方向，即只能：或從A柱到B柱；或從B柱到C柱；或從C柱到A柱（如下圖所示）。

目標是將原來都處於A柱的 個盤子都移到C柱。

只有1個盤子時，那麼需要兩步：1號盤A→B、1號盤B→C。

有2個盤子時，那麼需要將2號盤從A「移到」（不止一步）C，就必須先後經歷將2號盤從A移到B、將2號盤從B移到C。

而要將2號盤從A移到B，就得先把1號盤從A移到C；要將2號盤從B移到C，就得先把1號盤再從C移到A；最後再把1號盤從A移到C。

但是這時要注意的是："把1號盤從A移到C"和「把1號盤再從C移到A」是不同的問題！！！通俗地講，前者是要「跨過」B柱的、是不「相鄰」的移動，而後者則不然。

所以，有2個盤子時，可以採用下表方式分析（寫的有點粗略，應該能看懂吧= =），黃色部分可以看作類似原問題的子問題，而粉色部分和黃色部分是不同的。

更一般性地講，有 個盤子時，要採用如下的移動步驟：

1. 先將A柱上的 號盤子移到C柱上（這是一個類似於自己的子問題）;
2. 接著將最大的盤子（ 號）從A柱移到B柱；
3. 之後再將C柱上的 號盤子移到A柱上（注意，這不是一個類似於自己的子問題！！！）；
4. 接著將最大的盤子（ 號）從B柱移到C柱；
5. 最後再將A柱上的 號盤子移到C柱上（這還是一個類似於自己的子問題）。

因此我們需要定義一個「附屬問題」：設所有的移動必須是順時針方向，即只能：或從A柱到B柱；或從B柱到C柱；或從C柱到A柱。目標是將原來都處於A柱的 個盤子都移到B柱。

可以分析這時的解法是：

1. 先將A柱上的 號盤子移到C柱上;
2. 接著將最大的盤子（ 號）從A柱移到B柱；
3. 之後再將C柱上的 號盤子移到B柱上。

如果用表格表示的話就是：

下面來計算移動步數：

假設最初的「循環移動」問題的解法的步數為 ，而「循環移動」問題的「附屬問題」解法的步數為 。

則由解法描述有：

， ， 。

我將採用兩種方法來求解。

（一） 基於「2階常係數線性齊次遞推關係」的解法。

將 代入 ，得到：

。

之後類似於「漢諾塔雜談（一）」和「漢諾塔雜談（五）——變體之「臨近移動」」的方法，處理一下常數「3」：令 ，則得到 。

——這就是一個「2階常係數線性齊次遞推關係」：

假設序列 滿足遞推關係 ，其中 為已知常數，又 均已知（或者 均已知，可由遞推關係逆推出 ）。

稱 為該遞推關係的特徵方程，假設它的兩個根為 （允許 情況，即為二重根）。

可以很容易驗證 ，及 。

遞推可以得到：

。

由此再使用倒推法得到：

。

於是

• 當 時， ，即 ；
• 當 時， ，即 。

回到遞推關係 。

特徵方程為 ，兩個特徵根為 ， ， ，可逆推得到 。解得

，即得 。

（二） 基於「矩陣遞推關係」的解法。

假設 ， ， 。則得到矩陣遞推關係：

。

可以進一步遞推得到

，

其中 是單位矩陣。

下面介紹一般性解法：

（首先我們假設 可以對角化，否則可以使用Jordan分解，過程類似，但是複雜點兒）

• 假設 可以對角化為 ，那麼 ；
• 注意到 ，於是如果 可逆的話，則 ；
• 綜合這兩者，得到 。

回到具體問題， ，其中 ， ， ， ，由 可以逆推得到 。

代入 ，整理得到

。

最後看一下「漢諾塔圖」，此時變成了有向圖，紅色有向邊形成了解：