用最少步数解汉诺塔时,那个步骤里有着令人惊讶的漂亮规律。这里就 n 个圆盘的塔从左侧移到右侧的最少步骤(2ⁿ−1 步),依次介绍能发现的规则。圆盘按从小到大的顺序编号为 1、2、3……

每个圆盘的移动次数是 2 的幂

在最少步骤里,每个圆盘移动的次数是固定的。有 n 个圆盘时,第 k 号圆盘会移动 2ⁿ⁻ᵏ 次。

圆盘(4 个圆盘时)移动次数
18 次
24 次
32 次
41 次
合计15 次

最大的圆盘 1 次,下一个 2 次,再下一个 4 次……每小一号就翻一倍。合计起来是 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1,和最少步数正好一致。

原因用和最少步数公式同样的思路就能明白。移动 n 个圆盘,要把 n−1 个圆盘的塔移动 2 次。所以,比 n 号小的圆盘,动的次数是移动 n−1 个圆盘时的 2 倍。

第几步动哪个圆盘

4 个圆盘的最少步骤里,把从第 1 步开始依次移动的圆盘编号排出来,就是下面这样。

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

1 每隔一步出现,在它们之间每隔一个有 2,再在它们之间有 3……这和尺子刻度长度的排列(短、中、短、长……)是同样的形状。

这个排列,只要把步数写成二进制,就能马上求出。

第几步二进制末尾 0 的个数动的圆盘
110 个1
2101 个2
3110 个1
41002 个3
51010 个1
61101 个2
71110 个1
810003 个4

第 m 步动的,是把 m 写成二进制后“末尾连续 0 的个数 + 1”号圆盘。奇数步的二进制末尾是 1,所以总是动 1。这就是解法的文章里“奇数步动 1”的原因。

此外,起点和终点的柱子,也只靠二进制的计算就能求出(算法的文章)。

与格雷码的联系

把二进制从 0 开始依次数的时候,每加 1 变化的位数各不相同(0111 到 1000 有 4 位变化)。于是,把数排成每前进一步只有 1 位变化的表示方法,叫作“格雷码”。

序号格雷码变化的位(从右数)
0000―
10011
20112
30101
41103
51111
61012
71001

变化的位的排列“1 2 1 3 1 2 1”,和汉诺塔里移动的圆盘的排列完全相同。把 1 个圆盘看作二进制的 1 位,认为“那一位变化 = 那个圆盘移动”,那么汉诺塔的最少步骤,就和依次走过格雷码是一回事。

圆盘绕行的方向

解法的文章里介绍过,1 总是朝同一个方向绕行。其实其他圆盘也有同样的规则。

  • 奇数号圆盘(1、3、5……),全都和 1 朝同一个方向绕行。
  • 偶数号圆盘(2、4、6……),全都和 1 朝相反的方向绕行。

把左侧的塔移到右侧时,奇数个圆盘的话,1 的方向是“左 → 右 → 中间”,偶数个圆盘的话是“左 → 中间 → 右”。每个圆盘,到最后都一次也不改变方向。

还有一条在10 层的解法里介绍过的规则。在最少步骤里,绝不会把奇数号圆盘直接放在奇数号圆盘上,也不会把偶数号圆盘直接放在偶数号圆盘上。

摆放一共有 3ⁿ 种

遵守规则的圆盘摆放,一共有多少种呢?每个圆盘都可以放在 3 根柱子中的任何一根,而放在同一根柱子上的圆盘的顺序,由从大到小就定死了,所以摆放有 3ⁿ 种。

圆盘个数摆放数
3 个27 种
5 个243 种
7 个2,187 种
9 个19,683 种

而且,从任何一种摆放到任何一种摆放,遵守规则都一定能移过去。把所有摆放用点表示,再把一步就能互相移动的点用线连起来,得到的图形,也已知和大三角形里套着小三角形的“谢尔宾斯基三角形”很相似。

“汉诺塔”应用的“题目”模式,就是从这所有的摆放里,做出要摆成样本形状的题目。即使是 9 个圆盘的★5,也是把 19,683 种摆放全都查过最少步数之后才出题的。