汉诺塔作为高中数学里递推式和数学归纳法的题材,常出现在课本和入学考试题里。这篇文章一边解例题,一边练习思考方法。圆盘按从小到大的顺序编号为 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,必须移动 2 次:A → B → C。

  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ⁿ⁻¹ 次(原因见规律性的文章的“每个圆盘移动的次数”)。