震撼人心
Union_of_Britain
·
2024-02-23 23:28:38
·
题解
注：本文基本上是对参考文献 1 的翻译。这份论文是法语的，并且我没找到英语版本或中文介绍（
大家应该很熟悉汉诺塔了把，，，这里就不解释三柱汉诺塔了。
Frame-Stewart 算法
对于有 N 个圆盘 p 和 p(p\ge 3) 个柱子的汉诺塔，该算法寻找 1\le l<N ，使得以下步骤得到操作次数最小：
设其答案为 \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=\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 是依下表的值：
设
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 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\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.