A Variation of Hanoi Problem

Saturday, January 12, 2019

• 当只有一个圆盘时，我们需要至少移动 $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

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$$

$$$$X_{n}=\left\{ \begin{array}{lcl} 0 & & ({n = 0}) \\ 3X_{n-1} + 2 & & ({n \geqslant 1})\\ \end{array} \right.$$$$

$$\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}$$