普通的汉诺塔有 3 根柱子。那么,如果多加 1 根,变成 4 根,会怎样呢?规则不变,一次移动 1 个圆盘,不把大圆盘放在小圆盘上,把塔移到另一根柱子。

只多 1 根,步数就大幅减少

能用的放置位置多了一个,移开圆盘就轻松多了。比较最少步数,圆盘越多,差距越大。

圆盘个数3 根柱子4 根柱子
3 个7 步5 步
4 个15 步9 步
5 个31 步13 步
6 个63 步17 步
7 个127 步25 步
8 个255 步33 步
10 个1,023 步49 步
64 个约 1845 亿亿步18,433 步

用 3 根柱子移 64 个圆盘,就算每秒 1 步也要约 5845 亿年(64 个圆盘要花多少年?)。但如果是 4 根柱子,只要 18,433 步,每秒 1 步的话约 5 小时。如果传说里的僧侣多加了一根柱子,世界当天就终结了。

杜德尼的“奶酪谜题”

把 4 根柱子的汉诺塔广泛介绍出去的,是英国的益智作家亨利·杜德尼。他在 1907 年出版的书《坎特伯雷谜题》里,把它作为“雷夫难题”出了题。雷夫(Reeve)是指庄园的管理人。

在杜德尼的题目里,用的不是圆盘,而是 8 块大小不同的奶酪,要在 4 个凳子之间移动。不能把大奶酪放在小奶酪上。答案是 33 步,和上表中 8 个圆盘的步数一样。

Frame–Stewart 的解法

用 4 根柱子以较少步数移动的方法,1941 年 J·S·Frame 和 B·M·Stewart 分别发表了同样的思路。移动 n 个圆盘的塔时,

  1. 把上面的 k 个圆盘,用全部 4 根柱子,移到目标柱子以外的一根柱子上。
  2. 把剩下的 n−k 个圆盘,不使用放着上面 k 个圆盘的那根柱子,只用 3 根柱子移到目标柱子上(2ⁿ⁻ᵏ−1 步)。
  3. 把第 1 步移开的 k 个圆盘,用全部 4 根柱子,移到目标柱子上。

分成这 3 个部分。第 1 步和第 3 步是同一个问题的缩小版,所以可以用递归的思路(算法的文章)。剩下的,就是选出上面留下多少个(k 个)时步数最少。8 个圆盘的话,先移开上面的 4 个或 5 个最少,是 33 步。

将近 100 年没能证明的“最少”

人们知道,用 Frame–Stewart 的方法能以较少步数移动。可是,有没有比这更少的方法,长期以来谁也证明不了。

3 根柱子的话,从“移动最大圆盘的瞬间,其他圆盘必须全部集中在 1 根柱子上”这一个事实,马上就能证明最少步数(最少步数公式)。到了 4 根,移动大圆盘的瞬间,其他圆盘在剩下的 2 根柱子上怎样分布都可以,所以可能的步骤一下子就增加了。

用计算机查遍所有摆放,已经确认到 30 个左右的圆盘时这个方法是最少的。然后在杜德尼出题大约 100 年后的 2014 年,法国数学家蒂埃里·布什(Thierry Bousch)证明了,不管有多少个圆盘,Frame–Stewart 的方法都是最少的。柱子有 5 根以上的情况,据说至今还没有证明。

自己也能试

4 根柱子的汉诺塔,用制作方法的文章里的厚纸做法,把放置位置的圆圈画成 4 个就能做出来。试试看能不能用 5 步移 3 个圆盘、9 步移 4 个圆盘。可以亲身感受到和 3 根柱子时的不同。