A Variation of Hanoi Problem

Saturday, January 12, 2019

这道题目来自《具体数学:计算机科学基础(第二版)》第一章习题中“热身题”部分的第二题:把有 N 个圆盘的塔从左边的桩柱 A 移动到右边的桩柱 B,不允许在 A 和 B 之间直接移动,求最短的移动序列(每一次移动都必须是移动到中间的桩柱或者从中间的桩柱移出。较大的圆盘永远不能放在较小的圆盘的上面)。

注意,这道题目与“汉诺塔问题”唯一不同之处在于:不允许在 A 和 B 之间直接移动,必须通过中间的桩柱

首先,从最简单的几种情况开始观察规律(注:以下移动顺序的起点桩柱 $A$ 用“$(\bullet)$”表示)。

  • 当只有一个圆盘时,我们需要至少移动 $2$ 次; 移动顺序:$(\bullet)$ -> $M$ -> $B$。
  • 当有两个圆盘时,我们需要至少移动 $8$ 次;假定圆盘按从小到大的尺寸分别编号为 #1#2:对于圆盘 #1 的移动顺序,有 $(\bullet)$ -> $M$ -> $B$ -> $M$ -> $A$ -> $M$ -> $B$,对于圆盘 #2 的移动顺序,有 $(\bullet)$ -> $M$ -> $B$
  • 当有三个圆盘时,我们需要至少移动 $26$ 次;假定圆盘按从小到大的尺寸分别编号为 #1#2#3:对于圆盘 #1 的移动顺序,有 $(\bullet)$ -> $M$ -> $B$ -> $M$ -> $A$ -> $M$ -> $B$ -> $M$ -> $A$ -> $M$ -> $B$ -> $M$ -> $A$ -> $M$ -> $B$ -> $M$ -> $A$ -> $M$ -> $B$,对于圆盘 #2 的移动顺序,有 $(\bullet)$ -> $M$ -> $B$ -> $M$ -> $A$ -> $M$ -> $B$,对于圆盘 #3 的移动顺序,有 $(\bullet)$ -> $M$ -> $B$
圆盘个数 移动次数
1 2
2 8
3 26

到目前为止,可以看到移动次数 $X_{n}$ 与圆盘的个数 $N$ 存在着指数的关系。另外,还可以观察到,最大的那块圆盘总是移动 $2$ 次,即 $(\bullet)$ -> $M$ -> $B$。猜测可能存在这样的关系 $X_{n} = \alpha q^{m} + 2$,其中 $\alpha > 0,m \geqslant 0$。看上去这是一个等比数列,但是目前没有足够的信息进一步推断 $\alpha q^{m}$。

接下来观察两个圆盘的移动顺序:

  1. 圆盘 #1先移动到 $B$,也就是 $A$ -> $M$ -> $B$,这里我们把移动次数记作 $X_{1}$
  2. 圆盘 #2 移动到 $M$,此时移动了 $1$ 次
  3. 圆盘 #1 通过再次返回到 $A$,也就是 $B$ -> $M$ -> $A$,这个顺序刚好与第一次圆盘 #1 移动的顺序相反,由于移动次数与移动顺序无关,我们可以把移动次数同样记作 $X_{1}$
  4. 圆盘 #2 移动到 $B$,此时移动了 $1$ 次
  5. 圆盘 #1 需要从 $A$ 移动到 $B$,这种情况如同移动只有一个圆盘的问题,则其移动次数可记作 $X_{1}$

通过上面的分析,我们可以把有两个圆盘总共移动的次数写成如下式子:

$$ X_{2} = X_{1} + 1 + X_{1} + 1 + X_{1} = 3X_{1} + 2 $$

进一步,我们可以猜测,对于任意多的圆盘 $N$ 且 $N \geqslant 1$,存在:

$$ \begin{equation} X_{n}=\left\{ \begin{array}{lcl} 0 & & ({n = 0}) \\ 3X_{n-1} + 2 & & ({n \geqslant 1})\\ \end{array} \right. \end{equation} $$
把 $N - 1$ 个圆盘整体看做较小的圆盘

事实上,我们可以这样考虑这个问题:当 $N > 1$ 时,把 $N$ 个圆盘从 $A$ 移动到 $B$,必然需要先把 $N - 1$ 个圆盘从 $A$ 移动到 $B$,这样第 $N$ 个圆盘才能移动到 $M$,接下来 $N - 1$ 个圆盘再从 $B$ 移动到 $A$,这样第 $N$ 个圆盘才能移动到 $B$,此时第 $N$ 个圆盘已抵达终点,而剩余的 $N - 1$ 个圆盘处在 $A$,那么我们最后把它们从 $A$ 经过 $M$ 移动到 $B$ 即可。

简言之,当 $N = 1$ 时,圆盘从 $A$ 经过 $M$ 到达 $B$ 总共移动了 $2$ 次;当 $N > 1$ 时,圆盘的移动过程中存在 $3$ 次 $N - 1$ 个圆盘从 $A$ 到 $B$ 的往返移动以及 $2$ 次第 $N$ 个圆盘从 $A$ 到 $B$ 的移动。对于 $N - 1 $ 个圆盘,把它们当做 $N’$ 个圆盘的问题来处理,重复上述操作即可。最终验证了 $X_{n} = 3X_{n-1} + 2$。

最后我们对递归式 $(1)$ 进行求解:

$$ \begin{array}{llll} \because & X_{n} & = 3X_{n-1} + 2 & \\ & X_{n} + 1 & = 3X_{n-1} + 1 + 2 & = 3(X_{n-1} + 1)\\ \therefore & X_{n} & = 3^{n} - 1 \\ \end{array} $$