河內塔在日本的高中數學(數學 B)的遞迴式,和數學歸納法的題材中,常出現在課本和入學考試的題目裡。這篇文章一邊解例題,一邊練習想法。圓盤依由小到大編為 1、2、3……號,把移動 n 個圓盤的塔的最少步數寫成 aₙ。
例題 1 列出遞迴式
題目:有 3 根柱子 A、B、C,A 上從大到小疊著 n 個大小不同的圓盤。每次移動 1 個圓盤,不把大圓盤放在小圓盤上,把所有圓盤移到 C。把最少步數記為 aₙ,請用 aₙ 表示 aₙ₊₁。
解法:注意最大的圓盤(第 n+1 號)。要把這個圓盤移到 C,在那一瞬間,上面的 n 個圓盤必須全部疊在 B 上。
- 把上面的 n 個圓盤從 A 移到 B……最少 aₙ 步
- 把第 n+1 號圓盤從 A 移到 C……1 步
- 把 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。
解法:
- n = 1 時,1 個圓盤用 1 步就能移動,不可能更少,所以最少步數是 1 = 2¹ − 1,成立。
- 假設 n = k 時,最少步數是 2ᵏ − 1。n = k+1 時,由例題 1 的想法,最少步數是 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1,所以 n = k+1 時也成立。
- 由 1、2,對所有自然數 n 都成立。
重點是,例題 1 的「≤ 和 ≥ 兩者」,是用在歸納法的第 2 步。
例題 4 只能移到相鄰柱子的情況
題目:假設柱子 A、B、C 排成一列,圓盤只能在 A 和 B、B 和 C 之間移動(不能從 A 直接移到 C)。請求出把 n 個圓盤從 A 移到 C 的最少步數 bₙ。
解法:最大的圓盤 n,必須移動 A → B → C 共 2 次。
- 把上面的 n−1 個圓盤從 A 移到 C……bₙ₋₁ 步(要把 n 移到 B,必須先把 B 空出來)
- 把圓盤 n 從 A 移到 B……1 步
- 把 n−1 個圓盤從 C 移到 A……bₙ₋₁ 步(要把 n 移到 C,必須先把 C 空出來)
- 把圓盤 n 從 B 移到 C……1 步
- 把 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 練習題
最後,請自己解解看。答案在下面。
- 請求出圓盤有 10 個時的最少步數。
- 最少步數超過 1000 步,是圓盤有幾個以上的時候?
- 用最少步驟移動 n 個圓盤時,最小的圓盤會動幾次?
答案:1. 2¹⁰ − 1 = 1023 步。2. 由 2ⁿ − 1 > 1000 得 2ⁿ > 1001,2⁹ = 512,2¹⁰ = 1024,所以是 10 個以上。3. 2ⁿ⁻¹ 次(原因在規律的文章的「各圓盤的移動次數」)。
