AI丛刊

Thierry Bousch在2014年发表的论文《La quatrième tour de Hanoï》（四柱汉诺塔），它证明了四柱汉诺塔问题（Reve's Puzzle）中Frame-Stewart猜想的最优性。以下是对证明核心内容的解读：

核心问题：四柱汉诺塔的最优解

目标：证明将 (N) 个盘子从一根柱子移动到另一根所需的最少步数确为 (\Phi(N) = \sum_{k=0}^{N-1} 2^{\nabla k})，其中 (\nabla k) 是 (k) 的三角根（满足 (\Delta p = p(p+1)/2 \leq k) 的最大整数 (p)）。
背景：Dudeney（1908）和Frame-Stewart（1941）提出该公式并猜想其最优性，但此前缺乏严格证明。

证明的核心工具：函数 (\Psi)

作者构造了一个关键函数 (\Psi)，其定义基于集合的三角根性质： [ \Psi(E) = \max_{L \in \mathbb{N}} \left( (1-L)2^L - 1 + \sum_{k \in E} 2^{\min(\nabla k, L)} \right) ] 其中 (E \subseteq \mathbb{N}) 是有限自然数子集。(\Psi) 的性质是证明的核心：

关联 (\Phi)（引理 2.2）： [ \Psi[n] = \frac{\Phi(n+1)-1}{2} = \frac{1}{2} \sum_{k=1}^{n} 2^{\nabla k} ]
不等式控制（引理 2.4–2.8）：
- 上下界：(n \leq \Psi(E) \leq 2^n - 1)（(n = |E|)）
- 集合操作下的行为（如 (\Psi(A \cup B) \leq \Psi(A) + \Psi(B))）。

核心定理：距离下界（定理 2.9）

设 (C = {0, 1, 2, 3}) 为四根柱子。对任意初始配置 (u: [N] \to C) 和目标配置 (v)（满足 (v) 仅使用柱子 ({2, 3})），有： [ d(u, v) \geq \Psi({k \in [N] : u(k) = 0}) ] 解释：

(d(u,v)) 是从 (u) 到 (v) 的最少移动步数。
右边仅依赖初始时在柱子 (0) 的盘子集合 (E)。
意义：为后续证明 (\Phi(N)) 的最优性奠定基础。

证明框架（归纳法 + 分情况讨论）

归纳基础：对盘子数 (N) 进行归纳，假设结论对 (< N) 成立。
关键步骤：
- Case 1：最大盘 (N-1) 初始不在柱子 (0)（平凡情况）。
- Case 2：最大盘在柱子 (0)，且最终移至柱子 (2)（不失一般性）。
  - 定义关键时间点 (t_0, t_1, t_2, t_3) 对应最大盘和关键盘 (T) 的移动事件。
  - 分情况讨论磁盘 (T) 的行为（是否经过柱子 (3)）。
核心情形：
- 子情形 1：(\Delta K > T)（(K) 是大于 (T) 的盘子数）
  利用 (\Psi) 的递归不等式和移动步数下界拼接（第10页）。
- 子情形 2：(\Delta K \leq T)
  进一步按时间顺序 (t_1) 与 (t_3) 的关系分三种情况（第11–13页），结合引理 2.6–2.8 控制 (\Psi) 的变化。

最优性推论（推论 4.1）

应用定理 2.9 到特例：

(u)：所有盘在柱子 (0)。
(v)：所有盘在柱子 (2)。
通过路径 (u \to z_0 \to z_2 \to v) 和 (\Psi) 的性质导出： [ d(u, v) \geq 1 + 2\Psi[N-1] = \Phi(N) ] 结论：(\Phi(N)) 是最小步数。

(\Psi) 的动机（第14–17页）

类比三柱汉诺塔：在三柱问题中，距离下界为 (\sum 2^k)（经典解）。
四柱推广：自然猜想下界为 (\sum 2^{\nabla k})，但直接归纳失败（因下界不单调）。
单调化修正：通过考虑子集嵌入，定义 (\Gamma(N, E) = \frac{\Phi(N+1)-1}{2} - \sum_{k \notin E} 2^{\nabla k})，并证明其单调化版本恰为 (\Psi(E))（引理 5.1）。

证明的意义

解决百年猜想：严格证明了Frame-Stewart公式对四柱汉诺塔的最优性。
方法创新：
- 引入函数 (\Psi) 将组合优化问题转化为集合函数极值。
- 通过三角根 (\nabla k) 捕捉四柱情况下的分层递归结构。
扩展性：方法可能推广到更多柱子（尽管本文仅处理四柱）。

注：证明技术性强，需熟悉组合数学、递归函数和图论（配置图为超立方体的子图）。建议从 (N=3) 的示例验证关键步骤。