用最少步數解開河內塔時,它的步驟有著驚人漂亮的規律。這裡針對有 n 個圓盤的塔從左邊移到右邊的最少步驟(2ⁿ−1 步),依序介紹能發現的規則。圓盤依由小到大編為 1、2、3……號。
各圓盤的移動次數是 2 的次方
在最少步驟中,每個圓盤移動的次數是固定的。n 個圓盤時,第 k 號圓盤會移動 2ⁿ⁻ᵏ 次。
| 圓盤(4 個時) | 移動次數 |
|---|---|
| 1 | 8 次 |
| 2 | 4 次 |
| 3 | 2 次 |
| 4 | 1 次 |
| 合計 | 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 的個數 | 移動的圓盤 |
|---|---|---|---|
| 1 | 1 | 0 個 | 1 |
| 2 | 10 | 1 個 | 2 |
| 3 | 11 | 0 個 | 1 |
| 4 | 100 | 2 個 | 3 |
| 5 | 101 | 0 個 | 1 |
| 6 | 110 | 1 個 | 2 |
| 7 | 111 | 0 個 | 1 |
| 8 | 1000 | 3 個 | 4 |
第 m 步移動的,是 m 寫成二進位時「結尾連續 0 的個數 + 1」號的圓盤。奇數步的二進位結尾是 1,所以一定是 1 在動。這就是解法文章裡「奇數步移動 1」的原因。
此外,移動的來源柱和目標柱,也只要用二進位的計算就能求出(演算法的文章)。
與格雷碼的關聯
把二進位從 0 開始依序數的時候,每加 1,改變的位數各不相同(從 0111 到 1000 會有 4 位數改變)。於是,把數排成每前進 1 次只有 1 個位數改變的表示法,叫做「格雷碼」。
| 順序 | 格雷碼 | 改變的位數(從右邊數) |
|---|---|---|
| 0 | 000 | ― |
| 1 | 001 | 1 |
| 2 | 011 | 2 |
| 3 | 010 | 1 |
| 4 | 110 | 3 |
| 5 | 111 | 1 |
| 6 | 101 | 2 |
| 7 | 100 | 1 |
改變位數的排列「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 種擺法的最短步數之後才出題的。
