汉诺塔的传说：64 片金盘与世界末日

背景

1883 年，巴黎市场上出现一种玩具：三根柱子，一根柱子上套着从小到大叠放的圆盘，要求把整叠盘子搬到另一根柱子上，每次只搬一片，且任何时候大盘不能压在小盘上。玩具说明书讲了一个动人的故事：印度梵天庙里，僧侣们日夜搬运一座 64 片金盘的塔，搬完之日，世界将随之终结。

这个故事把无数孩子拦在「数得清、搬不完」的门口，也把「递归」这个深刻的数学思想装进了玩具盒。

史料辨析

传说 「梵天庙 64 金盘」的故事没有任何印度文献佐证，它是卢卡斯为玩具营销而编的文学包装——他甚至用了「N. Claus」这个把自己姓氏重新排列的笔名（Claus 是 Lucas 的变位词）。

史实 玩具本身及其数学分析是卢卡斯的真实贡献，收录于他的《数学游戏》。最少步数公式 $2^n-1$ 及「此数不可再少」的证明，在玩具问世次年即见于数学杂志。

数学内核

设搬 $n$ 片盘最少需要 $a_n$ 步。关键观察：最大的一片盘从起点柱搬到目标柱的那一步之前，上面 $n-1$ 片必须先全部搬到中转柱（$a_{n-1}$ 步）；大片落位后，再把 $n-1$ 片从中转柱搬回目标柱（又是 $a_{n-1}$ 步）：

$a_n=2a_{n-1}+1,a_1=1$

逐项算：$1,3,7,15,31,\dots$，规律一目了然：

$a_n=2^n-1$

为什么不能再少：最大盘必须移动至少一次，而它移动的前提是其余 $n-1$ 片已摞成一整塔放在另一柱上——这本身至少需要 $a_{n-1}$ 步。所以任何方案都不少于 $2a_{n-1}+1$ 步，递归方案恰好达到下限。

64 片的代价：$2^{64}-1=18446744073709551615$ 步。即使僧侣不眠不休每秒搬一片，也需要约 5849 亿年——是宇宙年龄的四十多倍。传说的「末日」因此格外「安全」。

递归的魅力在于：你不需要记住几千亿步中的任何一步，只需坚信一句话——「要搬 n 片，就先搬好 n−1 片」，然后把这个信念交给下一层。这种「把问题交给更小的自己」的思维方式，是小学递推、中学数学归纳法与计算机递归程序的共同源头。

说法与史实