河內塔有 n 個圓盤時,把塔移到另一根柱子的最少步數是 2ⁿ−1 次。也就是把 2 連乘圓盤個數那麼多次,再減 1 的數。

圓盤個數最少步數
1 個1 次
2 個3 次
3 個7 次
4 個15 次
5 個31 次
6 個63 次
7 個127 次
8 個255 次
9 個511 次

圓盤每多 1 個,步數大約就變成 2 倍。我們依序來看看為什麼會這樣。

注意最大的圓盤

來想想把 n 個圓盤的塔從左邊移到右邊。最大的圓盤在其他圓盤的下面,所以直接是動不了的。要把最大的圓盤搬到右側,在那一瞬間必須是下面的狀態。

  • 最大圓盤的上面,什麼都沒有放。
  • 右側的柱子是空的(因為比最大圓盤小的圓盤,不能放在它下面)。

也就是說,剩下的 n−1 個圓盤,必須全部疊在中間的柱子上。

把步數分成 3 個部分

這樣一來,移動 n 個圓盤的步驟,可以分成下面 3 個部分。

  1. 把上面的 n−1 個圓盤,從左邊移到中間。
  2. 把最大的圓盤,從左邊一次移到右邊。
  3. 把中間的 n−1 個圓盤,移到大圓盤的上面。

1 和 3 都正好是「移動 n−1 個圓盤的塔」的問題。把 n 個圓盤的最少步數寫成 T(n),就會得到

T(n) = T(n−1) + 1 + T(n−1) = 2 × T(n−1) + 1

這樣的關係。1 個圓盤時是 1 次,所以 T(1) = 1。由此依序可以求出 3、7、15、31……。

算式變成 2ⁿ−1 的原因

在這個關係的兩邊都加上 1,就會變成

T(n) + 1 = 2 × (T(n−1) + 1)

也就是說,「步數加 1 的數」,每多 1 個圓盤就剛好變成 2 倍。1 個圓盤時 T(1) + 1 = 2,所以 n 個圓盤時就是 2 連乘 n 次的 2ⁿ。再減掉 1,就得到 T(n) = 2ⁿ−1。

為什麼不可能更少

用上面的步驟可以用 2ⁿ−1 次移完,這點我們已經知道了。那麼,有沒有用更少步數移動的方法呢?

如同剛才所說,第一次移動最大圓盤的瞬間,剩下的 n−1 個圓盤必須全部疊在另一根柱子上。到那之前,至少需要移動 n−1 個圓盤的塔所需的步數。同樣地,最後把最大的圓盤放到右側之後,要把剩下的 n−1 個圓盤重新疊到它的上面,至少也需要移動 n−1 個圓盤的塔所需的步數。最大的圓盤本身,也至少要移動 1 次。

不論是什麼走法,這 3 個部分的步數一定都會用到。所以,不可能比 2 × T(n−1) + 1 次更少。其實也已經知道,最少步數的走法只有這 1 種。

App 的「經典」模式是 127 步

App「河內塔」的經典模式是 7 個圓盤,所以最少步數是 2⁷−1 = 127 步。步數剛好是 127,就表示是用最少步數解開的。照著玩法文章介紹的「把小圓盤朝同一個方向循環移動」的走法,就能剛好用 127 步完成。