用最少步數解開河內塔時,它的步驟有著驚人漂亮的規律。這裡針對有 n 個圓盤的塔從左邊移到右邊的最少步驟(2ⁿ−1 步),依序介紹能發現的規則。圓盤依由小到大編為 1、2、3……號。

各圓盤的移動次數是 2 的次方

在最少步驟中,每個圓盤移動的次數是固定的。n 個圓盤時,第 k 號圓盤會移動 2ⁿ⁻ᵏ 次。

圓盤(4 個時)移動次數
18 次
24 次
32 次
41 次
合計15 次

最大的圓盤 1 次,次大的 2 次,再下一個 4 次……越小就變成 2 倍。加起來 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1,和最少步數剛好一致。

原因用和最少步數公式一樣的想法就能明白。要移動 n 個圓盤,要把 n−1 個圓盤的塔移動 2 次。所以比第 n 號小的圓盤,就會是移動 n−1 個圓盤時的 2 倍次數。

第幾步會動哪個圓盤

4 個圓盤的最少步驟中,從第 1 步開始依序排出移動的圓盤編號,會是下面這樣。

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

1 每隔一步出現,中間每隔一個放進 2,再中間又放進 3……。和尺上刻度長短的排列(短、中、短、長……)是同樣的形狀。

這個排列只要把步數寫成二進位,就能馬上求出來。

第幾步二進位結尾 0 的個數移動的圓盤
110 個1
2101 個2
3110 個1
41002 個3
51010 個1
61101 個2
71110 個1
810003 個4

第 m 步移動的,是 m 寫成二進位時「結尾連續 0 的個數 + 1」號的圓盤。奇數步的二進位結尾是 1,所以一定是 1 在動。這就是解法文章裡「奇數步移動 1」的原因。

此外,移動的來源柱和目標柱,也只要用二進位的計算就能求出(演算法的文章)。

與格雷碼的關聯

把二進位從 0 開始依序數的時候,每加 1,改變的位數各不相同(從 0111 到 1000 會有 4 位數改變)。於是,把數排成每前進 1 次只有 1 個位數改變的表示法,叫做「格雷碼」。

順序格雷碼改變的位數(從右邊數)
0000―
10011
20112
30101
41103
51111
61012
71001

改變位數的排列「1 2 1 3 1 2 1」,和河內塔中移動的圓盤排列完全相同。把 1 個圓盤看作二進位的 1 個位數,想成「那個位數改變=那個圓盤移動」,河內塔的最少步驟,就和依序走過格雷碼是一樣的。

圓盤循環的方向

解法文章介紹過,1 總是朝同一個方向循環。其實,其他圓盤也有同樣的規則。

  • 奇數號的圓盤(1、3、5……)全部都和 1 朝同一個方向循環。
  • 偶數號的圓盤(2、4、6……)全部都和 1 朝相反方向循環。

把左側的塔移到右側時,奇數個圓盤的話,1 的方向是「左 → 右 → 中間」,偶數個圓盤的話是「左 → 中間 → 右」。不論哪個圓盤,到最後一次都不會改變方向。

還有一個規則,是在10 層的解法介紹過的。在最少步驟中,奇數號圓盤上面不會直接放奇數號,偶數號上面也不會直接放偶數號。

擺法總共有 3ⁿ 種

遵守規則的圓盤擺法,總共有幾種呢?每個圓盤都能放在 3 根柱子的任何一根,而疊在同一根柱子上的圓盤順序,會被固定成由大到小,所以擺法是 3ⁿ 種。

圓盤個數擺法
3 個27 種
5 個243 種
7 個2,187 種
9 個19,683 種

而且,不論從哪種擺法到哪種擺法,遵守規則一定都能移過去。也已經知道,如果把所有擺法用點表示,把一步就能移過去的點之間用線連起來,會變成很像大三角形裡巢狀嵌著小三角形的「謝爾賓斯基三角形」的圖形。

App「河內塔」的「題目」模式,是從這全部的擺法當中,做出要擺成樣本形狀的題目。就算是 9 個圓盤的 ★5,也是在調查過全部 19,683 種擺法的最短步數之後才出題的。