自动搬运

查看原文

来自洛谷，原作者为

	Union_of_Britain 神于天

搬运于2025-08-24 21:26:37，当前版本为作者最后更新于2024-02-23 23:28:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

注：本文基本上是对参考文献 $1$ 的翻译。这份论文是法语的，并且我没找到英语版本或中文介绍（

大家应该很熟悉汉诺塔了把，，，这里就不解释三柱汉诺塔了。

Frame-Stewart 算法

对于有 $N$ 个圆盘 $p$ 和 $p(p\ge 3)$ 个柱子的汉诺塔，该算法寻找 $1\le l<N$，使得以下步骤得到操作次数最小：

• 把前 $l$ 个通过 $p$ 个柱子移到一个非目标柱子上。

• 把剩下的圆盘通过 $p-1$ 个柱子移到目标柱子上去。

• 把前 $l$ 个通过 $p$ 个柱子移到目标柱子上。

设其答案为 $\Phi(p,N)$，有：

$$\Phi(p,N)=\min_{1\le l<N}(2\Phi(p,l)+\Phi(p-1,N-l)) $$

边界条件：$\Phi(3,N)=2^N-1,\Phi(p,1)=1$。

如何证明其正确性呢？这是一个困难的问题，见下文所述。

如何解决本题

这个算法真的有人在意他的正确性吗？

好吧还真有。

// Problem: P1573 栈的操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1573
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// UOB Koala'
// 
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e6+7;
int qp(int a,int b){
	if(b==0)return 1;
	int T=qp(a,b>>1);T=T*T%mod;
	if(b&1)return T*a%mod;
	return T;
}
int calc(int n){
	int t=(0.5+sqrt(2.0*n));
	int res=(1-qp(2,t-2)*(t*t-3*t-2*n+4)%mod+mod)%mod;
	return res;
}
signed main(){
    int n;cin>>n;
    cout<<calc(n)<,endl;
	return 0;
}

按照下面讲的通项公式实现即可。

有关 $\Psi$ 和 $\Phi$ 的代数性质

有必要引入几个重要函数及其性质来辅助证明定理 $9$ 和定理 $10$。

设

$$[n]=\{0,1,\dots,n-1\}$$ $$\Delta (n)=n(n+1)/2,\nabla(n)=\max\{k\ge 0\mid \Delta(k)\le n\} $$$$\Phi(n)=\sum _{i=0}^{n-1}2^{\nabla(i)}$$

此时有 $\Delta u=u+\Delta(u-1)$。

参考文献 2 指出，

$$\Phi(n)=\min_{0\le m<n}2\Phi(m)+2^{n-m}-1$$

可以发现其的确和 $\Phi(4,N)$ 的递推式吻合，所以说 $\Phi(n)$ 即为所找 $\Phi(4,N)$。根据这一点不难得出其通项公式

$$\Phi(n)=1-2^{t-2}(t^2-3t+4-2n)$$

其中 $t=\lceil \sqrt{2n}\rceil$。

推论：

$$\forall a,b\in \mathbb{N},\Phi(a+b)\le 2\Phi(a)+2^b-1 $$

引理 1：对于 $n,p\in \mathbb{N},p\le n+1$，

$$\Phi(\Delta n+p)=1+(n+p-1)2^n$$

证明：显然其在 $p=0$ 时成立，$p$ 逐渐增加到 $n+1$ 时都不会改变 $\Delta n+p-1$ 的 $\nabla$ 值，得证。

定义函数

$$\Psi_L(E)=(1-L)2^L-1+\sum_{u\in E}2^{\min(\nabla u,L)} $$$$\Psi(E)=\sup _{L\in \mathbb{N}}\Psi_L(E)$$

不难发现其是良定义的。

引理 2：$\forall n\in\mathbb{N}$，

$$\Psi[n]=\frac{\Phi(n+1)-1}2$$

证明：

$n=0$ 时命题成立。因此假设 $n\ge 1$。

类似于带余除法地，设 $n=\Delta m+p$，其中 $m=\nabla n$，此时 $0\le p\le m$。

根据引理 $1$，有：

$$\Phi(\Delta m)=1+(m-1)2^m$$ $$\Phi(n+1)=1+(m+p)2^m$$

因此 $\forall L\in \mathbb{N}$，有：

$$\Psi_{L+1}[n]-\Psi_L[n]=-(L+1)2^L+\sum _{u\in [n]}2^{\min(\nabla u,L+1)}-2^{\min(L,\nabla u)} $$$$=-(L+1)2^L+2^L(\#\{u\in [n]\mid u\ge \Delta(L+1)\}) $$$$=2^L(\max(0,n-\Delta(L+1))-(L+1))$$

此式 $>0$ 当且仅当：

$$n\ge \Delta(L+1)+L+2=\Delta(L+2)$$

即 $\nabla n\ge L+2$，等价于 $L<m-1$。因此只需计算 $\Psi_{m-1}[n]$。

$$\Psi_{m-1}(n)=(2-m)2^{m-1}-1+\sum _{0\le i<\Delta m}2^{\nabla i}+\sum_{\Delta m\le k<n}2^{m-1} $$$$=(2-m)2^{m-1}-1+\Phi(\Delta m)+(n-\Delta m)2^{m-1} $$$$=m2^{m-1}+p2^{m-1}$$ $$=\frac{\Phi(n+1)-1}2$$

证毕。

推论：

$$\forall a,b\in \mathbb{N},\Psi[a+b]\le 2\Psi[a]+2^{b-1} $$

根据引理 $2$ 化为 $\Phi$ 即可。

引理 $3$：$\forall n\in \mathbb{N}$，

$$\Psi[n+2]\ge 2^{(\nabla n)+1}$$

设 $s=\nabla n$。根据 $\Psi[\cdot]$ 递增，仅需考虑 $\Psi[\Delta s+2]\ge 2^{s+1}$。

容易验证 $s<2$ 时成立，对于 $s\ge 2$，根据引理 $2$，

$$\Psi[\Delta s+2]=(s+2)2^{s-1}\ge 2^{s+1}$$

证毕。

引理 $4$：$\forall E\subset N,\#E=n$，

$$n\le \Psi[n]\le \Psi (E)\le 2^n-1$$

$n\le \Psi[n]$ 是显然的。

$\Psi[n]\le \Psi (E)$：设 $E$ 排序后为 $e_0<e_1<\dots<e_{n-1}$。此时有 $e_i\ge i$。所以

$$\Psi_L(E)=(1-L)2^L-1+\sum_{i}2^{\min(\nabla e_i,L)}\ge (1-L)2^L-1+\sum_{i}2^{\min(\nabla i,L)}=\Psi_L[n] $$

$\Psi(E)\le 2^n-1$：放缩，

$$\Psi_L(E)=(1-L)2^L-1+\sum_{i\in E}2^{\min(\nabla u,L)} $$$$\le (1-L)2^L-1+\sum_{i\in E}2^{L}=(1+n-L)2^L-1\le 2^{n}-1 $$

证毕。

引理 $5$：设 $A,B\subset \mathbb{N}$，

$$\Psi(A)-\Psi(B)\le \sum_{u\in A-B}2^{\nabla u}$$

设 $\Psi(A)=\Psi_L(A)$。放缩：

$$\Psi(A)-\Psi(B)\le \Psi_L(A)-\Psi_L(B)\le \Psi_L(A)-\Psi_L(A\cap B) $$$$=\sum _{u\in A-B}2^{\min (\nabla u,L)}\le \sum _{u\in A-B}2^{\nabla u} $$

引理 $6$：设 $A\subset \mathbb{N}$，$s\in \mathbb{N}$，使得 $\#(A-[\Delta s])\le s$，那么：

$$\Psi(A)-\Psi(A-\{a\})\le 2^{s-1},\forall a\in A$$

可以假设 $A\neq \varnothing$，那么 $s\ge 1$。$\forall L\ge s-1$，根据前面的结果，

$$\Psi_{L+1}(A)-\Psi_L(A)=2^L(\#\{n\in A\mid n\ge \Delta(L+1)\}-L-1)\le 2^L(\#\{n\in A\mid n\ge \Delta s\}-s)\le 0 $$

那么 $\exists L\le s-1,\Psi(A)=\Psi_L(A)$，所以：

$$\Psi(A)-\Psi(A-\{a\})\le \Psi_L(A)-\Psi_L(A-\{a\})=2^{\min(\nabla a,L)}\le 2^L\le 2^{s-1} $$

证毕。

引理 $7$：

设 $n,s\in \mathbb{N},s\ge 1,n\ge \Delta(s-1),A\in [n],b_{1:s}\in \mathbb{N}^s$。有：

$$\Psi(A\cup \{b_{1:s}\})-\Psi(A)\le \Psi[n+s]-\Psi[n] $$

设 $A_t=A\cup \{b_{1:t}\},0\le t\le s$。原命题等价于

$$\Psi(A_t)-\Psi(A_{t-1})\le \Psi[n+t]-\Psi[n+t-1]$$

只需考虑 $t>0,b$ 互不相同。

根据引理 $2$，右式可以写作 $2^{\sigma -1}$，其中 $\sigma=\nabla (n+t)$。根据引理 $6$，只需证明 $\#(A_t-[\Delta\sigma])\le \sigma$。

注意到 $\Delta(\sigma+1)>n+t$，即 $\sigma+\Delta\sigma\ge n+t$，所以

$$\#(A_t-[\Delta\sigma])\le t+\#([n]-[\Delta\sigma])=t+\max(0,n-\Delta\sigma)\le \max(t,\sigma) $$

下面证明 $\sigma\ge t$：

$$\Delta t-t=\Delta(t-1)\le \Delta(s-1)\le n$$

所以

$$\Delta t\le n+t$$

而 $\sigma=\nabla(n+t)\ge t$。证毕。

引理 $8$：

设 $A,B\subset \mathbb{N},n=\#(A\cup B)$，则

$$\Psi(A)+\Psi(B)\ge \frac{\Phi(n+3)-5}4=\frac 12\Psi[n+2]-1=\frac 14\left(\sum _{i=3}^{n+2}2^{\nabla i}\right) $$

等号可直接通过定义得到，关注不等号：

设 $E=A\cup B,L\in \mathbb{N}$。根据引理 $4$，总有 $\Psi_L(E)\ge \Psi_L[n]$。所以：

$$\Psi(A)+\Psi(B)\ge \Psi_L(A)+\Psi_L(B)=\Psi_L(A\cap B)+\Psi(A\cup B)\ge \Psi _L(\varnothing)+\Psi_L(E) $$$$\ge \Psi_L[0]+\Psi_L[n]$$

和上面类似地，设 $n+3=\Delta m+p$，其中 $m=\nabla (n+3)$。

根据引理 $1$，有：

$$\Phi(n+3)=1+(m+p-1)2^m\\ \Phi(\Delta(m-2))=1+(m-3)2^{m-2} $$

取 $L=m-2$。这样

$$\Psi_L[0]+\Psi_L[n]=(1-L)2^{L+1}-2+\sum_{i=0}^{n-1}2^{\min(\nabla i,L)} $$$$=(3-m)2^{m-1}-2+\sum _{i=0}^{\Delta(m-2)-1}2^{\nabla i}+\sum_{i=\Delta(m-2)}^{n-1}2^{m-2} $$$$=(3-m)2^{m-1}-2+\Phi(\Delta(m-2))+(n-\Delta(m-2))2^{m-2} $$$$=(m+p-1)2^{m-2}-1=\frac{\Phi(n+3)-5}{4}$$

这些引理会在后面的证明被反复应用。

定理 $9$ 及其证明

汉诺塔游戏和定理 $9$

接下来回到原问题汉诺塔问题。

从小到大对圆盘用 $[N]$ 标号。记 $C$ 是柱子集合，比方说 $\{0,1,2,3\}$。

一个汉诺塔游戏的状态可以使用一个函数 $u:[N]\to C$ 表示。$u(a)$ 表示 $a$ 盘子所在柱子。所有状态的集合显然就是 $C^{[N]}$。

定义距离函数 $d(u,v):(C^{[N]})^2\to \mathbb{N}\cup \{\infty\}$，是两个状态通过合法操作互化的最小操作次数。

定理 $9$：

设 $C=\{0,1,2,3\},N\in \mathbb{N}$，$u,v$ 是两个 $N$ 圆盘 $4$ 柱汉诺塔的状态。如果 $\forall i,v(i)\in \{2,3\}$，那么：

$$d(u,v)\ge \Psi(k\in [N]\mid u(k)=0)$$

这个定理意味着，$N$ 圆盘 $4$ 柱汉诺塔的答案 $\ge \Psi[N]$。

下面大部分的篇幅将会证明这个定理。

定理 $9$ 的证明

定义和基础性质

我们采取对 $N$ 归纳的方法。边界条件是显然的。

设 $E=\{k\in [N]\mid u(k)=0\}$。可以假设 $E\neq \varnothing$，否则命题显然。

设 $u',v':[N-1]\to C$，是 $u,v$ 移除掉最大的圆盘的状态。

有：

$$d(u,v)\ge d(u',v')\ge \Psi(E-\{N-1\})$$

若 $N-1\not\in E$，显然；因此，假设 $N-1\in E$。不妨设 $v(N-1)=2$。

接下来定义路径。设 $d(u,v)=D$。路径是函数 $\gamma:[D+1]\to C^{[N]}$，且满足 $\gamma(0)=u,\gamma(D)=v$，$d(\gamma(i),\gamma(j))=|i-j|,\forall i,j\in [D+1]$。下面，也用 $\gamma _i$ 指代 $\gamma(i)$（应用柯里化技巧）。

事实上，把所有的状态可以一步互化的连上无向边，得到的图上 $u$ 到 $v$ 的任意一条最短路径就是上面的 $\gamma$。

设 $E'=\{k\in E\mid \exists t\in [D+1],\gamma_t(k)=3\}$，即初始在第 $0$ 柱，但经过第 $3$ 柱的圆盘集合。

考虑 $E'=\varnothing$ 的情况。这就是三柱问题，而根据引理 $4$ 知道 $\Psi (E)\le 2^{\# E}-1$，而 $D\ge 2^{\# E}-1\ge \Psi(E)$。

设 $T=\max E'$，$E''=E-[T+1]$，$K=|E''|$（可能是 $0$）。设 $E''=\{b_{1:K}\},b_i<b_{i+1}$。

显然有 $T+K+1\le N$。

设 $t_0$ 是最小的整数使得 $\gamma_{t_0}(T)\neq 0$，即 $T$ 已经离开 $0$ 柱子的时间。设状态 $x_0=\gamma(t_0-1)$。在这一状态中，第 $0$ 柱的顶部是 $T$，移动到的那一柱的顶部 $>T$。设 $t_1$ 是最小的整数使得 $\gamma_{t_1}(T)=3$。类似地，设 $x_3=\gamma(t_1)$。在这一状态中，第 $3$ 柱的顶部是 $T$，来的那一柱顶部 $>T$。显然 $1\le t_0\le t_1\le D$。

设 $t_2$ 是最小的整数使得 $\gamma_{t_2}(N-1)\neq 0$，并设 $z_0=\gamma(t_2-1)$。在这一状态中，第 $0$ 柱的顶部是 $N-1$，移动到的那一柱是空的。设 $t_3$ 是最大的整数使得 $\gamma_{t_3}(N-1)\neq 2$，并设 $z_2=\gamma (t_3+1)$。在这一状态中，第 $2$ 柱的顶部是 $N-1$，来的那一柱是空的。此时有 $t_2\le t_3+1$。

类似地定义 $x'_a,z'_b$ 是忽略 $N-1$ 圆盘的 $x_a,z_b$，$x_a'',z_b''$ 是忽略 $\ge T$ 的圆盘的 $x_a,z_b$。 $u,v$ 同理。

观察到 $z_0'$ 的两列都是空的。所以可以类似地应用归纳假设：

$$d(u,z_0)\ge d(u',z_0')\ge \Psi\{k\in [N-1]\mid u(k)=0\}=\Psi(E-\{N-1\}) $$

类似地：

$$d(u,x_0)\ge d(u'',x_0'')\ge \Psi(E\cap [T])$$

$\Delta K>T$

首先考虑 $\Delta K>T$ 的情形。

此时有 $K\ge 1,T<b_k=N-1$，也就是说 $N-1$ 没有经过第 $3$ 柱。

此外，注意到 $(E-[\Delta K])\subset E''$，$\#(E-[\Delta K])\le \Delta K$，那么可以应用引理 $6$：

$$\Psi (E)-\Psi(E-\{N-1\})\le 2^{K-1}$$

与上面的式子结合，得到

$$d(u,z_0)\ge \Psi(E)-2^{K-1}$$

由于 $t_2\le t_3+1$，$u$ 到 $v$ 的路径 $\gamma$ 一定形如：

$$u\to z_0\to z_2\to v$$

考虑 $z_2$ 的 $2$ 柱和 $c=\gamma_{t_3}(N-1)$（$c\in\{0,1\}$）柱上不能有 $<N-1$ 的圆盘，所以 $b_{1:K-1}$ 一定都在 $1-c$ 柱上。这些盘最后（$v$）一定都在 $2$ 柱上，而这些圆盘不被允许通过第 $3$ 柱。根据三柱汉诺塔，有：

$$d(z_2,v)\ge 2^{K-1}-1$$

而 $d(z_0,z_2)\ge 1$，所以：

$$D=d(u,z_0)+d(z_0,z_2)+d(z_2,v)$$ $$\ge (\Psi(E)-2^{K-1})+1+(2^{K-1}-1)=\Psi(E)$$

证毕。

$\Delta K\le T$

其次考虑 $\Delta K\le T$ 的情况。

取 $s=\nabla(T+K+1)$。由于 $E=[T+1]\cup E''$，$\#(E-[\Delta s])\le \max(T+1-\Delta s,0)+K$。

显然 $s\ge \nabla T\ge K$。并且 $T+K+1<\Delta(s+1)=\Delta s+s+1$，那么 $T+K+1-\Delta s\le s$。根据以上两条，有：

$$\#(E-[\Delta s])\le s$$

所以应用引理 $6$ 有：

$$\Psi(E)-\Psi(E-\{N-1\})\le 2^{s-1}$$

这次作用于上面的式子得到的结果是

$$d(u,z_0)\ge d(u',z_0')\ge \Psi(E)-2^{\nabla(T+K+1)-1} $$

$K=0$

先考虑 $K=0$。

这意味着 $T=N-1$ 经过了 $3$ 柱，最后留在 $2$ 柱。

因为 $t_1\le t_3$，所以 $u$ 到 $v$ 的路径 $\gamma$ 一定形如：

$$u\to z_0=x_0\to x_3\to z_2\to v$$

设 $c=\gamma_{t_3}(N-1)\neq 2$。所以在状态 $z_2'$ 中，所有圆盘都在除了 $2,c$ 的那两个柱子上。设：

$$\{0,1,2,3\}-\{2,c\}=\{a,b\}$$

不妨设 $a,b$ 是依下表的值：

$c$	$0$	$1$	$3$
$a$	$3$		$0$
$b$	$1$	$0$	$1$

设

$$A=\{k\in [N-1]\mid z_2(k)=a\}$$ $$B=\{k\in [N-1]\mid z_2(k)=b\}$$

因为 $A\cup B=[N-1]$，根据引理 $8$，有：

$$\Psi(A)+\Psi(B)\ge \frac 12\Psi[N+1]-1$$ $$=\frac 14(2^{\nabla (N+1)}+2^{\nabla N})+\frac 12 \Psi[N-1]-1 $$$$\ge 2^{\nabla(T+K+1)-1}+\frac 12 \Psi[N-1]-1$$

在 $x'_a$ 中， $a$ 柱和另一柱为空，因此可以应用归纳假设：

$$d(z_2',x_a')\ge \Psi(A)$$

而在 $v'$ 中，$0$ 和 $1$ 柱为空，有：

$$d(z_2,v)\ge d(z_2',v')\ge \Psi(B)$$

而在 $z_0$ 到 $z_2$ 的路径上，$[N-1]$ 的圆盘至少做了 $d(x_a',z_2')$ 次操作（因为路径结构），而 $N-1$ 至少需要 $0\to 3\to 2$，所以

$$d(z_0,z_2)\ge \Psi(A)+2$$

那么

$$D=d(u,v)=d(u,z_0)+d(z_0,z_2)+d(z_2,v)$$ $$\ge \Psi(E)-2^{\nabla(T+K+1)-1}+\Psi(A)+2+\Psi(B)$$ $$\ge \Psi(E)+1+\frac 12 \Psi[N-1]\ge \Psi(E)$$

$K\ge 1$

接下来解决最后一种情况：$K\ge 1$，所以 $T<b_k=N-1$。

此时我们无从比较 $t_1$ 和 $t_3+1$，难以像之前一样直接每段放缩，只能分类讨论。

$t_1>t_3+1$

假设 $t_1>t_3+1$。

那么 $u\to v$ 的路径一定形如：

$$u\to z_0\to z_2\to x_3\to v$$

在状态 $x_3$ 中，$3$ 和 $d=\gamma_{t_1-1}(T)$ 不包含小于 $T$ 的圆盘。他们在剩下的两列里。所以，设 $c=\gamma_{t_3}(N-1)\in \{0,1\}$。

那么设：

$$\{0,1,2,3\}-\{3,d\}=\{a,b\}$$

其中 $a,b$ 值依下表。

$d$	$0$ 或 $1$	$2$
$a$	$2$	$c$
$b$	$1-d$	$1-c$

设

$$A=\{k\in [T]\mid x_3(k)=a\}$$ $$B=\{k\in [T]\mid x_3(k)=b\}$$

在状态 $z_2''$ 中， $a$ 和另一列是空的。因此应用归纳假设：

$$d(x_3,z_2)\ge d(x_3'',z_2'')\ge \Psi(A)$$

而在 $v''$ 中， $0,1$ 列为空。所以应用归纳假设：

$$d(x_3,v)\ge d(x_3'',v'')\ge \Psi(B)$$

而 $d(z_0,z_2)\ge 1$，所以：

$$D=d(u,v)=d(u,z_0)+d(z_0,z_2)+d(z_2,z_3)+d(x_3,v)$$ $$\ge \Psi(E)-2^{\nabla (T+K+1)-1}+1+\Psi(A)+\Psi(B) $$$$\ge \Psi(E)-2^{\nabla(T+K+1)-1}+\frac 12 \Psi[T+2] $$

设 $s=\nabla(T+K+1)$。因为 $T\ge \Delta K$，$T+K+1\ge \Delta(K+1)$，即 $s\ge K+1$。但是

$$T=(T+K+1)-(K+1)\ge \Delta s-s=\Delta(s-1)$$

即 $\nabla T\ge s-1$。根据引理 $3$，$\Psi[T+2]\ge 2^s$。所以，$D\ge \Psi (E)$。

$t_1<t_3+1$

设 $t_1<t_3+1$。

$u\to v$ 的路径一定形如：

$$u\to x_0\to x_3/z_0\to z_2\to v$$

中间不能确定 $x_3$ 和 $z_0$ 的顺序。

在状态 $z_2'$ 中，$2$ 柱和 $c=\gamma_{t_3}(N-1)\in \{0,1\}$ 柱为空。因此所有圆盘都在 $3$ 柱和 $b=1-c$ 柱上。$b_{1:K-1}$ 一定在 $b$ 柱上。

设

$$A=\{k\in [T]\mid z_2(k)=3\}$$ $$B=\{k\in [N-1]\mid z_2(k)=b\}$$

在状态 $x_3''$ 中，$3$ 柱和另一柱为空。因此可以应用归纳假设，$d(z_2'',x_3'')\ge \Psi(A)$。

而在状态 $v'$ 中，$0,1$ 柱为空，所以 $d(z_2,v)\ge d(z_2',v')\ge \Psi(B)$。

$$([T]\cup \{b_{1:K-1}\})\subset (A\cup B)$$

所以

$$\Psi(A)+\Psi(B)\ge \frac 12 \Psi[T+K+1]-1$$

由于 $d(z_2'',x_3'')\ge \Psi(A)$，在 $x_3$ 到 $z_2$，$<T$ 的圆盘至少操作 $\Psi(A)$ 次。从 $u$ 到 $x_0$，$<T$ 的圆盘至少操作 $\Psi(E\cap [T])$ 次（依靠归纳假设）。此外，在 $u$ 状态下，$b_{1:K-1}$ 圆盘都在 $0$ 柱，在 $z_0$ 却都不在 $0$ 柱上，且不能经过 $3$ 柱。因此，根据三柱汉诺塔，他们至少需要 $2^{K-1}-1$ 次操作完成这个。最后，盘 $T$ 在 $x_0$ 到 $x_3$ 至少被操作一次，盘 $N-1$ 在 $z_0$ 到 $z_2$ 至少被操作一次。综上，

$$d(u,z_2)\ge \Psi(E\cap [T])+\Psi(A)+2^{K-1}+1$$

得到结果：

$$D=d(u,v)=d(u,z_2)+d(z_2,v)$$ $$\ge\Psi(E\cap [T])+\Psi(A)+2^{K-1}+1+\Psi(B)$$ $$\ge \Psi(E\cap [T])+\frac 12 \Psi[T+K+1]+2^{K-1}$$

另外，由于 $T\ge \Delta K$，$E=(E\cap[T])\cup\{T,b_{1:K}\}$，根据引理 $7$，有：

$$\Psi(E)-\Psi(E\cap [T])\le \Psi[T+K+1]-\Psi[T]$$

根据上式，有：

$$D-\Psi(E)\ge \Psi(T)+2^{K-1}-\frac 12\Psi[T+K+1]$$

根据引理 $2$ 的推论，右式非负，所以 $D\ge \Psi(E)$。

至此，定理 $9$ 的所有情况证毕。

证明原命题-定理 $10$

定理 $9$ 并没有显然地给出 Frame-Stewart Algorithm 的正确性。

定理 $10$：$N$ 个圆盘的汉诺塔问题可以在 $\Phi(N)$ 步内解决。

不妨设 $N\ge 1$。

设 $u$ 是所有 $N$ 个圆盘都在 $0$ 柱的状态，$v$ 是所有圆盘都在 $2$ 柱的状态。

$u$ 到 $v$ 的路径一定形如：

$$u\to z_0\to z_2\to v$$

由于 $z_0$ 有两列为空，应用定理 $9$：

$$d(u,z_0)\ge d(u',z_0')\ge \Psi\{k\in [N-1]\mid u(k)=0\}=\Psi[N-1] $$

同样，

$$d(v,z_2)\ge \Psi[N-1]$$

而 $d(z_0,z_2)\ge 1$，所以：

$$d(u,v)=d(u,z_0)+d(z_0,z_2)+d(z_2,v)\ge 1+2\Psi[N-1]=\Phi(N) $$

最后一个等号来源于引理 $2$。

证毕。

参考文献

参考文献 1 ：T. Bousch. La quatri`eme tour de Hano¨ı. Bull. Belg. Math. Soc. Simon Stevin, 21:895–912,2014.

参考文献 2： S.Klav˘zar, U. Milutinovi´c, and C. Petr. On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem.Discrete Appl. Math., 120(1–3):141–157, 2002.