这道题目来自《 具体数学：计算机科学基础（第二版） 》第一章习题中“热身题”部分的第二题：把有 N 个圆盘的塔从左边的桩柱 A 移动到右边的桩柱 B， 不允许在 A 和 B 之间直接移动 ，求最短的移动序列（每一次移动都必须是移动到中间的桩柱或者从中间的桩柱移出。较大的圆盘永远不能放在较小的圆盘的上面）。
这道题目与“ 汉诺塔问题 ”唯一不同之处在于：不允许在 A 和 B 之间直接移动，必须通过中间的桩柱
首先，从最简单的几种情况开始观察规律（注：以下移动顺序的起点桩柱 A 用“(∙)”表示）。
当只有一个圆盘时，我们需要至少移动 2 次； 移动顺序：(∙) -> M -> B。
当有两个圆盘时，我们需要至少移动 8 次；假定圆盘按从小到大的尺寸分别编号为 #1 和 #2：对于圆盘 #1 的移动顺序，有 (∙) -> M -> B -> M -> A -> M -> B，对于圆盘 #2 的移动顺序，有 (∙) -> M -> B
当有三个圆盘时，我们需要至少移动 26 次；假定圆盘按从小到大的尺寸分别编号为 #1、#2 和 #3：对于圆盘 #1 的移动顺序，有 (∙) -> M -> B -> M -> A -> M -> B -> M -> A -> M -> B -> M -> A -> M -> B -> M -> A -> M -> B，对于圆盘 #2 的移动顺序，有 (∙) -> M -> B -> M -> A -> M -> B，对于圆盘 #3 的移动顺序，有 (∙) -> M -> B
圆盘个数
移动次数
1
2
2
8
3
26
到目前为止，可以看到移动次数 Xn 与圆盘的个数 N 存在着指数的关系。另外，还可以观察到，最大的那块圆盘总是移动 2 次，即 (∙) -> M -> B。猜测可能存在这样的关系 Xn=αqm+2，其中 α>0，m⩾0。看上去这是一个等比数列，但是目前没有足够的信息进一步推断 αqm。
接下来观察两个圆盘的移动顺序：
圆盘 #1先移动到 B，也就是 A -> M -> B，这里我们把移动次数记作 X1
圆盘 #2 移动到 M，此时移动了 1 次
圆盘 #1 通过再次返回到 A，也就是 B -> M -> A，这个顺序刚好与第一次圆盘 #1 移动的顺序相反，由于移动次数与移动顺序无关，我们可以把移动次数同样记作 X1
圆盘 #2 移动到 B，此时移动了 1 次
圆盘 #1 需要从 A 移动到 B，这种情况如同移动只有一个圆盘的问题，则其移动次数可记作 X1
通过上面的分析，我们可以把有两个圆盘总共移动的次数写成如下式子：
X2=X1+1+X1+1+X1=3X1+2
进一步，我们可以猜测，对于任意多的圆盘 N 且 N⩾1，存在：
Xn={03Xn−1+2(n=0)(n⩾1)把 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′ 个圆盘的问题来处理，重复上述操作即可。最终验证了 Xn=3Xn−1+2。
