[具体数学]第一章·递归问题

第一章·递归问题分 3 节，主要包括 \(\textbf{Hanoi}\) 塔问题、平面上直线分割问题、约瑟夫问题。其中，个人认为约瑟夫问题的讨论相当具有启发性。

Hanoi 塔问题

Notes

这是个超级经典的递归问题了，不多做解释。设 \(T_n\) 是 \(n\) 个圆盘的移动次数，那么有递归式： \[ \begin{cases}T_0=0\\T_n=2T_{n-1}+1\end{cases} \] 两边同时加一转化成等比数列，或者用数学归纳法，最后解得： \[ T_n=2^n-1 \]

习题

书上的习题有一些 \(\textbf{Hanoi}\) 塔问题的变式，在此挑一些记录一下：

• 不允许在最左边的 \(A\) 柱和最右边的 \(B\) 柱之间直接移动： \[ T_n=T_{n-1}+1+T_{n-1}+1+T_{n-1}=3T_{n-1}+2\implies T_n=3^n-1 \] 证明：这种移动规则下，\(3\) 根柱子上都会出现 \(n\) 个圆盘的每一种正确叠放。

  证：宏观来看，一共就 \(3^n\) 种可能，而 \(T_n=3^n-1\)，一定遍历了所有可能的叠放方式。\(\square\)

  批注：这问题问得很玄学，转换角度思考就变简单了。

• 是否存在某种初始情形和结束情形，使得需要多于 \(2^n-1\) 的移动？

  不存在，归纳：如果最大盘不动，最多 \(2^{n-1}-1\) 次；否则，最多 \((2^{n-1}-1)+1+(2^{n-1}-1)=2^n-1\) 次。\(\square\)

  批注：不知道咋整就归纳，哈哈

• 要求移动必须是顺时针方向（只能 \(A\to B,B\to C,C\to A\)），设 \(Q_n\) 是 \(A\to B\) 的最少移动次数，\(R_n\) 是 \(B\to A\) 的最少移动次数，求证： \[ Q_n=\begin{cases}0&,n=0\\2R_{n-1}+1&,n>0\end{cases}\quad\quad R_n=\begin{cases}0&,n=0\\Q_n+Q_{n-1}+1&,n>0\end{cases} \] 证：意思就是 \(Q_n\) 是跨一步，\(R_n\) 是跨两步。

  跨一步这样完成：\(n-1\) 个盘 \(A\to C\)，\(1\) 个盘 \(A\to B\)，\(n-1\) 个盘 \(C\to B\)，故 \(Q_n=R_{n-1}+1+R_{n-1}=2R_{n-1}+1\)；

  跨两步这样完成：\(n-1\) 个盘 \(A\to C\)，\(1\) 个盘 \(A\to B\)，\(n-1\) 个盘 \(C\to A\)，\(1\) 个盘 \(B\to C\)，\(n-1\) 个盘 \(A\to C\)，故 \(R_n=R_{n-1}+1+Q_{n-1}+1+R_{n-1}=(2R_{n-1}+1)+Q_{n-1}+1=Q_n+Q_{n-1}+1\). \(\square\)

  注：遗留问题：为什么跨两步不能这样：\(n-1\) 个盘 \(A\to C\)，\(1\) 个盘 \(A\to B\)，\(n-1\) 个盘 \(C\to B\)，\(n\) 个盘 \(B\to C\)。这样是 \(R_n=R_{n-1}+1+R_{n-1}+Q_n=2Q_n\). 可以验证答案更差，但是怎样才能避免这样想？

• \(n\) 种尺寸，第 \(k\) 种有 \(m_k\) 个圆盘，求最少移动次数 \(A(m_1,\cdots,m_k)\). \[ A(m_1,\cdots,m_n)=2A(m_1,\cdots,m_{n-1})+m_n=4A(m_1,\cdots,m_{n-2})+2m_{n-1}+m_n=\cdots=\sum\limits_{i=0}^{n-1}2^im_{n-i} \]

平面上的直线

Notes

也是一个经典问题了，一条新的直线和原来的 \(n-1\) 条直线最多有 \(n-1\) 个交点，就最多增加 \(n\) 个面。

为什么？注意这条直线被划分成了 \(n\) 段，每一段两侧是两个现在不同、但是之前相同的面，所以净增加了 \(n\) 个面。

由此，我们有递归式： \[ \begin{cases}L_0=1\\L_n=L_{n-1}+n\end{cases} \] 累和，或者数学归纳法，解得： \[ L_n=\frac{n(n+1)}{2}+1 \]

变式

• 把直线改成折线：

  

  注意到，一条折线相当于两条直线相交后抹掉一半，抹掉一半后平面数减 \(2\)，所以 \(Z_n=L_{2n}-2n\).

  可能还是不好理解（至少我理解了很久），这么考虑：新加一条折线进来，从它的顶点向被抹掉的那个方向看去，抹掉的直线本应该把这个区域分成 \(3\) 部分，但现在它是 \(1\) 部分，所以少了 \(2\)。

  基于此我们也可以得到递归式：加入新折线的一条边，有 \(2n-2\) 个新交点，增加 \(2n-1\) 个面，再加入另一条边，有 \(2n-1\) 个新交点（包括新折线的顶点），增加 \(2n\) 个面，但是顶点那个交点不争气要减 \(2\)，所以总共新增 \(4n-3\) 个面，即 \(Z_n=Z_{n-1}+4n-3\).

• \(\text{Z}\) 字型（两平行半直线加一条直线段）划分平面：沿用上面的思路可得递归式：\(Z_n=Z_{n-1}+(3n-3+1)+(3n-3+1)+(3n-1+1)-2-2=Z_{n-1}+9n-8\)，解得：\(Z_n=\frac{9}{2}n^2-\frac{7}{2}n+1\).

• 厚奶酪上划直切痕，得到的三维区域最大个数：新增一个面，前 \(n-1\) 个面在这个新平面上最多得到 \(L_{n-1}\) 个区域，考虑每个区域两侧可以知道新增了 \(L_{n-1}\) 个块，所以 \(P_n=P_{n-1}+L_{n-1}\).

  这波降维打击实在有趣！

约瑟夫问题

重点来了！

基础问题

\(n\) 个人围圈，隔一个死一个，问最后剩下的人的编号 \(J(n)\).

• 偶数情况：\(2n\) 个人，死了一圈之后，剩下 \(n\) 个人编号是：\(1,3,5,\cdots,2n-1\)，这就是个把原编号 \(k\) 改成 \(2k-1\) 之后的 \(n\) 人约瑟夫问题，所以 \(J(2n)=2J(n)-1\)；
• 奇数情况：\(2n+1\) 个人，死了一圈之后，剩下 \(n\) 个人编号是：\(3,5,7,\cdots,2n+1\)，这就是个把原编号 \(k\) 改成 \(2k+1\) 之后的 \(n\) 人约瑟夫问题，所以 \(J(2n+1)=2J(n)+1\).

综上，再加上初始条件，有递归式： \[ \begin{cases}J(1)=1\\J(2n)=2J(n)-1\\J(2n+1)=2J(n)+1\end{cases} \] 至于怎么解这个递归式……我们可以打表（OIer & ACMer 狂喜）：

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
J(n)​	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

观察得到： \[ J(n)=2\left(n-2^{\lfloor\lg n\rfloor}\right)+1 \] 或者按书上的写法，是 \(J(2^m+l)=2l+1,\quad m\geqslant0,\quad 0\leqslant l<2^m\). 证明数学归纳法即可。

二进制视角

这一部分是我觉得最 Amazing 的地方了。

把上表写成二进制：

n​	1	10	11	100	101	110	111	1000	1001	1010	1011	1100	1101	1110	1111	10000
J(n)​	1	1	11	001	011	101	111	0001	0011	0101	0111	1001	1011	1101	1111	00001

发现一个神奇的现象：把 \(n\) 的二进制向左循环滚动一位，就得到了 \(J(n)\)！

其实看看通项公式，\(n-2^{\lfloor\lg n\rfloor}\) 就是删掉最高位的剩下的部分，乘 \(2\) 就是左移一位，加一就是把最高位加到最低位去——所以一通操作下来，就是向左循环一位。

如果我们进行套娃式迭代——不停地向左循环，但是注意前导 \(0\) 会消失掉，所以足够多次迭代下去后得到的数就是由所有 \(1\) 组成的二进制数，即 \(J(J(J(\cdots J(n))))=2^{\nu(n)}-1\)，其中 \(\nu(n)\) 是 \(n\) 在二进制下 \(1\) 的个数。

成套方法求解递归式 Repertoire Method

我们把 \(J(n)\) 的递归式给推广一下： \[ \begin{cases}f(1)=\alpha\\f(2n)=2f(n)+\beta\\f(2n+1)=2f(n)+\gamma\end{cases} \] （\(J(n)\) 是 \(\alpha=1,\beta=-1,\gamma=1\) 的特殊情况）。我们仍然可以打表找规律，但是可以用成套方法（这名字好奇怪）解它。

注意到决定上式结果的是 \(3\) 个参数 \(\alpha,\beta,\gamma\)，所以我们可以设 \(f(n)=\alpha A(n)+\beta B(n)+\gamma C(n)\) 是它的解（充分利用已知条件嘛）。下面我们找 \(3\) 个特解：

• 令 \(f(n)=1\)，解得：\(\alpha=1,\beta=-1,\gamma=-1\)，得到：\(A(n)-B(n)-C(n)=1\)；
• 令 \(f(n)=n\)，解得：\(\alpha=1,\beta=0,\gamma=1\)，得到：\(A(n)+C(n)=n\)；
• 令 \(\alpha=1,\beta=0,\gamma=0\)，有 \(f(n)=A(n)\)，得到：\(\begin{cases}A(1)=1\\A(2n)=2A(n)\\A(2n+1)=2A(n)\end{cases}\)，解得：\(A(n)=2^{\lfloor\lg n\rfloor}\).

联立上述 \(3\) 式，解得：\(C(n)=n-2^{\lfloor\lg n\rfloor},\;B(n)=2^{\lfloor\lg n\rfloor+1}-n-1\). 所以我们得到了递归式的解： \[ f(n)=2^{\lfloor\lg n\rfloor}\alpha+\left(2^{\lfloor\lg n\rfloor+1}-n-1\right)\beta+\left(n-2^{\lfloor\lg n\rfloor}\right)\gamma \] 或者用书上的写法（ \(n=2^m+l\) ），就是：\(f(n)=2^m\alpha+\left(2^m-1-l\right)\beta+l\gamma\).

有木有感觉很玄学！这三个特解咋冒出来的～特别是第三个特解，好生奇怪！

如果我们把函数 \(f(n)\) 看作一个向量，那它就是 \(A(n),B(n),C(n)\) 的线性组合，我们找到了三个特解，得到线性方程组： \[ \begin{bmatrix}1&-1&-1\\1&0&1\\1&0&0\end{bmatrix}\begin{bmatrix}A(n)\\B(n)\\C(n)\end{bmatrix}=\begin{bmatrix}1\\n\\2^m\end{bmatrix} \] 理论上，给定三个线性无关的向量 \([\alpha,\beta,\gamma]\) 和分别对应的的 \(f(n)\)，那么就可以解出 \([A(n),B(n),C(n)]\)。但是问题的关键就在于，任给一个 \([\alpha,\beta,\gamma]\)，解 \(f(n)\) 不一定简单。反过来，给定 \(f(n)\) 解 \([\alpha,\beta,\gamma]\) 倒是简单，但是给定的 \(f(n)\) 可能不合法，即根本就不是原递归式的解。所以我感觉这个“成套方法”有很多凑的成分……

推广递归式的进制视角

对于推广的递归式，改写为： \[ \begin{cases}f(1)=\alpha\\f(2n+j)=2f(n)+\beta_j&j=0,1,\;n\geqslant1\end{cases} \] 我们用二进制展开： \[ \begin{align} f\Big({(b_mb_{m-1}\cdots b_1b_0)}_2\Big)&=2f\Big({(b_mb_{m-1}\cdots b_1)}_2\Big)+\beta_{b_0} \\&=4f\Big({(b_mb_{m-1}\cdots b_2)}_2\Big)+2\beta_{b_1}+\beta_{b_0}\\&=\cdots \\&=2^m\cdot1+2^{m-1}\beta_{b_{m-1}}+\cdots+2\beta_{b_1}+\beta_{b_0} \\&={(\alpha\beta_{b_{m-1}}\cdots\beta_{b_1}\beta_{b_0})}_2 \end{align} \] 当然，这里不要求二进制的每一位必须是 \(0,1\)，而是任意数字都行。

怎么理解？把 \(n\) 写作二进制，其中 \(0\) 改成 \(\beta_0\)，\(1\) 改成 \(\beta_1\)，最高位改成 \(\alpha\)，就得到了 \(f(n)\).

我们还可以推广，如果递归式长这样： \[ \begin{cases}f(j)=\alpha_j&1\leqslant j<d\\f(dn+j)=cf(n)+\beta_j&0\leqslant j<d,\;n\geqslant1\end{cases} \] 那么用 \(d\) 进制展开： \[ \begin{align} f\Big({(b_mb_{m-1}\cdots b_1b_0)}_d\Big)&=cf\Big({(b_mb_{m-1}\cdots b_1)}_d\Big)+\beta_{b_0}\\ &=c^2f\Big({(b_mb_{m-1}\cdots b_2)}_d\Big)+c\beta_{b_1}+\beta_{b_0}\\&=\cdots\\ &=c^m\cdot\alpha_{b_m}+c^{m-1}\beta_{b_{m-1}}+\cdots+c\beta_{b_1}+\beta_{b_0}\\ &={(\alpha_{b_m}\beta_{b_{m-1}}\cdots\beta_{b_1}\beta_{b_0})}_c \end{align} \] 发现得到一个 \(c\) 进制结果！实在是妙呀！

习题

• 用成套方法解四参数递归式： \[ \begin{cases}g(1)=\alpha\\g(2n+j)=3g(n)+\gamma n+\beta_j&j=0,1,\; n\geqslant 1\end{cases} \] 解：设 \(g(n)=\alpha A(n)+\gamma B(n)+\beta_0C(n)+\beta_1D(n)\) 是它的解。这是四参数递归式，我们需要找到四个特解。

  • 令 \(\gamma=0\)，问题转化成了之前解决的问题，有解：\(g\Big({(b_mb_{m-1}\cdots b_1b_0)}_2\Big)={(\alpha\beta_{b_{m-1}}\cdots\beta_{b_1}\beta_{b_0})}_3\). 随便取 \(3\) 个线性无关的 \([\alpha,\beta_0,\beta_1]\)，就能确定下 \(A(n),C(n),D(n)\)；
  • 令 \(g(n)=n\)，解得：\((\alpha,\gamma,\beta_0,\beta_1)=(1,-1,0,1)\)，得到：\(A(n)-B(n)+D(n)=n\).

  于是我们解决了这个问题（虽然没有写出显式的表达式）。

• 用成套方法解五参数递归式： \[ \begin{cases}h(1)=\alpha\\h(2n+j)=4h(n)+\gamma_j n+\beta_j&j=0,1,\; n\geqslant 1\end{cases} \] 解：设 \(h(n)=\alpha A(n)+\gamma_0 B(n)+\gamma_1C(n)+\beta_0D(n)+\beta_1E(n)\) 是它的解。这是五参数递归式，我们需要找到五个特解。

  • 令 \(\gamma_0=\gamma_1=0\)，问题转化成了之前解决的问题，可以确定 \(A(n),D(n),E(n)\)；
  • 令 \(h(n)=n\)，解得：\((\alpha,\gamma_0,\gamma_1,\beta_0,\beta_1)=(1,-2,-2,0,1)\)，得到：\(A(n)-2B(n)-2C(n)+E(n)=n\)；
  • 令 \(h(n)=n^2\)（注意观察，平方项正好抵消，所以这么设又解），解得：\((\alpha,\gamma_0,\gamma_1,\beta_0,\beta_1)=(1,0,4,0,1)\)，得到：\(A(n)+4C(n)+E(n)=n^2\).

  联立，问题解决。