河內塔

河內塔（通常也稱為“漢諾塔”），是由 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) 將河內塔分析為一個多計算過程，包括透過使用分支圖。