汉诺塔(1883) — 数学家以化名推出的六十四片圆盘的传说

引言 — 三根柱子,与大小不同的圆盘

这是 1883 年在法国推出的一种游戏:在三根柱子之间移动木制圆盘。圆盘大小各不相同,起初按从大到小的顺序叠在一根柱子上。目标是把它们整体移到另一根柱子上。

规则只有两条。一次只能移动一片。并且,不得把大圆盘放在小圆盘之上。三片需要七步完成。五片需要三十一步。片数一增加,步数便急剧膨胀。

设计者是法国数学家爱德华·卢卡斯。不过,推出时署的名并不是卢卡斯本人。作者栏上写的是一位虚构人物,“暹罗的 N·克劳斯教授”。

按从大到小叠放的五片圆盘的示意(示意图・AI 生成)

时代背景 — 化名的教授,与梵天之塔的传说

卢卡斯的化名“N. Claus (de Siam)”,据说是“Lucas d'Amiens(亚眠的卢卡斯)”的字母重排而成。日文版 Wikipedia 也说明,这是其任职学校的名称与本人姓名的变位词。

游戏附带有说明书形式的传说。印度贝拿勒斯的寺院里,有六十四片纯金圆盘。僧侣们按同样的规则,日夜不停地搬移着塔。据说,当全部移完之时,世界就将终结。

盒子上的名字是“汉诺塔”,说明书中的塔则是“梵天之塔”。河内是越南北部的城市。并列使用这些暗示东方神秘的名字,为数学游戏披上了故事的外衣。

卢卡斯的讲解后来也收入了遗作《数学游戏(Récréations mathématiques)》。小册子的出版是在 1889 年。数学家隐去自己的名字,把它作为游戏出售。这是十九世纪数学热潮中颇具特色的做法。

令人联想到传说中“塔”的夜景示意(示意图・AI 生成)

机制 — 分解成小问题,步数就成了公式

解法的核心在于把问题变小。要移动 n 片,首先把上面的 n−1 片避让到空着的柱子上。接着把最大的圆盘放到目标柱子上。最后把避让开的 n−1 片移回它的上面。

反复如此,最少步数为 2 的 n 次方减 1。三片为 7,五片为 31。这一公式在英文版 Wikipedia 中也有载,属于基本事项。每增加一片,步数便大致翻倍。

六十四片的话,就是 2 的 64 次方减 1 步,也就是 18,446,744,073,709,551,615 步。即使每秒移动一步,也需要约 5850 亿年。传说中的“世界终结”,也就远在宇宙当前年龄之后。

通过这一计算,游戏从动手的游戏,变成了计数方法的练习。无论动得多快都不够。因此产生了“只要找到规则,不必思考就能全部知道”的体验。

三片圆盘用七步移完的八个局面(图解・示意图・AI 生成)

通向现代的谱系 — 柱子变成四根,成了一百多年的课题

把柱子增加到四根的情形,也已被充分研究。据英文版 Wikipedia,四根及以上柱子的步骤,以 1941 年的 Frame–Stewart 方法而闻名。至于是否最短的证明,则长期遗留未解。

2014 年 6 月,蒂埃里·布什公开了一篇论文(预印本),证明在四根柱子的情形下,这一步数确实是最小的。正如布什本人所写,这一猜想曾用计算机验证到 N=30,但没有证明。

这种游戏的形式也传到了心理学。1982 年心理学家蒂姆·沙利斯设计的“伦敦塔任务”,是以与汉诺塔相关的检测而闻名,被用来考察制订计划的能力。

本站的其他文章中也出现过汉诺塔。就同为“读步骤”的游戏这一点而言,[九连环(1872)](/en/articles/baguenaudier-1872)是较近的亲戚。关于测量 AI 推理能力的话题,可以在[Pereira 等人的论文介绍](/en/articles/paper-pereira-hanoi-world-model)中读到。

小问题构成大问题的嵌套结构示意(示意图・AI 生成)

参考文献

本文参考的信息来源:

・Wikipedia(英文版): Tower of Hanoi

・Wikipedia(日文版): ハノイの塔

・Thierry Bousch: The Fourth Tower of Hanoi(2014 年 6 月 15 日预印本)

・Wikipedia(英文版): Tower of London test

※“暹罗的 N·克劳斯教授”的化名与 64 片的传说,依据上述 Wikipedia 的记述。1889 年出版小册子一事亦同。未确认一手的说明书。

结语 — 数学家用故事推销游戏的那一年

1883 年的汉诺塔所表明的是:即使是只需两条规则的游戏,也能隐藏深层的结构。每移动一次圆盘,我们都在描摹递归的形态。

传说是编造的。但正因为有这个编造的故事,“六十四片”这个数字才留在了人们的记忆里。把数学与故事一起出售的手法,在一百四十年后的今天也并不过时。

你手边有三根柱子吗?如果没有,用三枚硬币和纸上画的三条线也足够。请先用三片,确认那七步。

只剩三根柱子和一片圆盘的安静情景示意(示意图・AI 生成)