河內塔在日本的高中數學(數學 B)的遞迴式,和數學歸納法的題材中,常出現在課本和入學考試的題目裡。這篇文章一邊解例題,一邊練習想法。圓盤依由小到大編為 1、2、3……號,把移動 n 個圓盤的塔的最少步數寫成 aₙ。

例題 1 列出遞迴式

題目:有 3 根柱子 A、B、C,A 上從大到小疊著 n 個大小不同的圓盤。每次移動 1 個圓盤,不把大圓盤放在小圓盤上,把所有圓盤移到 C。把最少步數記為 aₙ,請用 aₙ 表示 aₙ₊₁。

解法:注意最大的圓盤(第 n+1 號)。要把這個圓盤移到 C,在那一瞬間,上面的 n 個圓盤必須全部疊在 B 上。

  1. 把上面的 n 個圓盤從 A 移到 B……最少 aₙ 步
  2. 把第 n+1 號圓盤從 A 移到 C……1 步
  3. 把 B 的 n 個圓盤移到 C……最少 aₙ 步

用這個步驟能移動 n+1 個圓盤,所以 aₙ₊₁ ≤ 2aₙ + 1。反過來,不論什麼步驟,1~3 的步數一定都會用到,所以 aₙ₊₁ ≥ 2aₙ + 1。因此,

aₙ₊₁ = 2aₙ + 1(a₁ = 1)

入學考試有時會要求同時證明「≤」和「≥」,把等號確定下來。詳細說明在最少步數公式裡。

例題 2 求一般項

題目:請求出由 a₁ = 1、aₙ₊₁ = 2aₙ + 1 所定義的數列的一般項。

解法:aₙ₊₁ = paₙ + q 這種形式的遞迴式,要用滿足 α = 2α + 1 的 α 來變形。α = −1,所以兩邊加 1,

aₙ₊₁ + 1 = 2(aₙ + 1)

數列 aₙ + 1,是首項 a₁ + 1 = 2、公比 2 的等比數列。所以 aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ,

aₙ = 2ⁿ − 1

作為驗算,確認一下 a₁ = 1、a₂ = 3、a₃ = 7 和遞迴式吻合吧。

例題 3 用數學歸納法證明

題目:請用數學歸納法證明,移動 n 個圓盤的最少步數是 2ⁿ − 1。

解法:

  1. n = 1 時,1 個圓盤用 1 步就能移動,不可能更少,所以最少步數是 1 = 2¹ − 1,成立。
  2. 假設 n = k 時,最少步數是 2ᵏ − 1。n = k+1 時,由例題 1 的想法,最少步數是 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1,所以 n = k+1 時也成立。
  3. 由 1、2,對所有自然數 n 都成立。

重點是,例題 1 的「≤ 和 ≥ 兩者」,是用在歸納法的第 2 步。

例題 4 只能移到相鄰柱子的情況

題目:假設柱子 A、B、C 排成一列,圓盤只能在 A 和 B、B 和 C 之間移動(不能從 A 直接移到 C)。請求出把 n 個圓盤從 A 移到 C 的最少步數 bₙ。

解法:最大的圓盤 n,必須移動 A → B → C 共 2 次。

  1. 把上面的 n−1 個圓盤從 A 移到 C……bₙ₋₁ 步(要把 n 移到 B,必須先把 B 空出來)
  2. 把圓盤 n 從 A 移到 B……1 步
  3. 把 n−1 個圓盤從 C 移到 A……bₙ₋₁ 步(要把 n 移到 C,必須先把 C 空出來)
  4. 把圓盤 n 從 B 移到 C……1 步
  5. 把 n−1 個圓盤從 A 移到 C……bₙ₋₁ 步

所以 bₙ = 3bₙ₋₁ + 2(b₁ = 2)。由 α = 3α + 2 得 α = −1,所以 bₙ + 1 = 3(bₙ₋₁ + 1)。數列 bₙ + 1 是首項 3、公比 3 的等比數列,所以

bₙ = 3ⁿ − 1

對 1~6 個圓盤,用調查所有擺法的計算,也確認了這個步數是最少的。有趣的是,在 3ⁿ − 1 步之間,會把全部 3ⁿ 種擺法各經過 1 次(擺法的數量在規律的文章)。

例題 5 練習題

最後,請自己解解看。答案在下面。

  1. 請求出圓盤有 10 個時的最少步數。
  2. 最少步數超過 1000 步,是圓盤有幾個以上的時候?
  3. 用最少步驟移動 n 個圓盤時,最小的圓盤會動幾次?

答案:1. 2¹⁰ − 1 = 1023 步。2. 由 2ⁿ − 1 > 1000 得 2ⁿ > 1001,2⁹ = 512,2¹⁰ = 1024,所以是 10 個以上。3. 2ⁿ⁻¹ 次(原因在規律的文章的「各圓盤的移動次數」)。