河内塔

河内塔（通常也称为“汉诺塔”），是由 E. 卢卡斯于 1883 年发明的谜题。它也被称为梵天塔谜题，并在电影《猩球崛起》（2011 年）中以“卢卡斯塔”的名义作为猿类的智力测试出现。

给定一叠个圆盘，从下到上按大小排列在一个杆上，以及两个空杆，河内塔谜题要求将这叠圆盘从一个杆移动到另一个杆所需的最少步数，其中只有当将较小的圆盘放在较大的圆盘之上时才允许移动。具有个柱子和个圆盘的谜题有时被称为 Reve 谜题。

该问题与在-超立方体上找到哈密顿路径同构（Gardner 1957, 1959）。

给定三个杆和个圆盘，序列给出在第步要移动的圆盘的编号（到），由非常简单的递归程序给出，该程序从单圆盘的列表开始，并递归计算

对于的前几个值，这给出了下表所示的序列。上图说明了三杆四圆盘问题的解法。

随着圆盘数量的增加（同样对于三杆），获得一个无限序列，上表说明了该序列的前几项 (OEIS A001511)。令人惊讶的是，这正是二进制进位序列加一。更令人惊讶的是，在第步之后移动的圆盘数量与需要在个被加数的Ryser 公式中添加或删除的元素相同（Gardner 1988，Vardi 1991）。一种简单的手工解法使用涂有交替颜色的圆盘。任何两个相同颜色的圆盘都不会叠放在一起，并且任何圆盘都不会连续移动两次（P. Tokarczuk，私人通信，2004 年 6 月 23 日）。

由于上述过程，求解三个杆上的个圆盘的谜题所需的移动次数由递推关系给出

其中。求解得到

即，梅森数。

对于三个杆，可以使用卢卡斯对应证明上述解法是最小的，卢卡斯对应将帕斯卡三角形与河内图联系起来。虽然已知在四个杆上转移圆盘的算法，但没有一个被证明是最小的。

可以构造一个河内图，其图顶点对应于个塔的合法配置，其中图顶点在相应的配置可以通过合法移动获得时相邻。谜题本身可以使用二进制格雷码来解决。

Poole (1994) 和 Rangel-Mondragón 给出了用于解决河内塔问题的 Wolfram 语言 例程。Poole 的算法适用于任意圆盘配置，并以最少的步数提供解决方案。

在四个杆上排序, 2, ... 个圆盘所需的最少移动次数由 1, 3, 5, 9, 13, 17, 25, 33, ... 给出 (OEIS A007664)。据推测，该序列由以下递归式给出

其中，是以下方程的正底整数解

即，

这将给出显式公式

Wolfram (2022) 将河内塔分析为一个多计算过程，包括通过使用分支图。