04 EXERCISES

1

当$n=2$时，证明是错误的，因为$[1, n-1]$是$[1,1]$，就是第一匹马，$[2, n]$就是$[2,2]$，就是第二匹马，证明中说$[2, n-1]$这个集合如何如何，但是这个集合是空集，所以不能推定第一匹马和第二匹马是一个颜色。

如果补充一个条件，任意两匹马的集合颜色是一样的，那么整个证明就完整了，那么所有马的颜色都一样。

2

令$f(n)$表示移动$n$个盘的最小移动次数。最佳移动过程如下： 1. 从$A$移动$n-1$个盘到$B$；$f(n-1)$次 2. $A$的最大盘移动到中间的柱子上；1次 3. 从$B$把$n-1$个盘到$A$；$f(n-1)$次 4. 把最大盘从中间的柱子移动到$B$；1次 5. 最后把$n-1$个盘从$A$挪回$B$；$f(n-1)$次

所以$f(n)=3f(n-1)+2,n\geq 1$。最极端的情况$f(0)=0$。递归式两边同时加一得到 $$f(n)+1=3(f(n-1)+1)$$ 令$u(n)=f(n)+1,n\geq 1$，那么$u(0)=1$。所以 $$u(n)=3u(n-1)$$ 进而有 $$u(n)=3^n$$ $$f(n)=3^n-1$$

3

每一个圆盘有三种可能性，那么圆盘摆放的方式数量是$3^n$，需要移动$3^n-1$，加上初始状态，共计$3^n$。所以每一种情况都会覆盖到。

4

不存在。如果最大的圆盘不需要移动，那么根据归纳法$2^{n-1}-1$就足够了，如果最大的圆盘需要，那么和正文中归纳法一样，需要$2^{n-1}-1+1+$2^{n-1}-1=2^n-1$就足够了。

5

一个圆分成了两个区域，增加一个圆，和之前的圆有两个交点，增加两个区域，现在是四个区域，增加第三个圆，和之前的圆最多有四个交点，四个线段，那么再增加四个区域到八个区域。现在增加第四个圆，最多六个交点，那么再增加六个区域到十四个区域，小于十六。所以不能用四个重叠的圆来表示。

6

首先平面所有的区域数是$L_n$。有界区域数是多少呢？如果我们能够得到无界区域数，那么也就得到了问题的解。
一条直线的时候，无界区域是2个，两条直线无界区域是4个。如果已经有$n-1$条直线，将第$n$条直线加进去，那么会切过两个无界区域，变成4个无界区域，增加了2个，即每填一条直线是增加两个无界区域，所以$n$条直线的无界区域是$2n$个。
所以有界区域数是$L_n-2n$个。

7

没有给出基础的证明，而这正是错误所在。 $$H(1)=J(2)-J(1)=1-1=0\neq 2$$

8

计算前几项看看有没有规律可循。 $$\begin{aligned} Q_0&=\alpha\\ Q_1&=\beta\\ Q_2&=(1+\beta)/\alpha\\ Q_3&=\frac{1+(1+\beta)/\alpha}{\beta}\\ &=\frac{1+\alpha+\beta}{\alpha\beta}\\ Q_4&=\frac{1+\frac{1+\alpha+\beta}{\alpha\beta}}{(1+\beta)/\alpha}\\ &=\frac{\alpha\beta+1+\alpha+\beta}{\beta(1+\beta)}\\ &=\frac{(1+\alpha)(1+\beta)}{\beta(1+\beta)}\\ &=(1+\alpha)/\beta\\ Q_5&=\frac{1+(1+\alpha)/\beta}{\frac{1+\alpha+\beta}{\alpha\beta}}\\ &=\frac{\beta+1+\alpha}{\frac{1+\alpha+\beta}{\alpha}}\\ &=\alpha\\ Q_6&=\frac{1+\alpha}{(1+\alpha)/\beta}\\ &=\beta \end{aligned}$$ 也就说，整个数列是个循环数组，周期是5，周期内各个数如上所列。

9

$P(n)$成立，所以 $$x_1x_2\cdots x_{n-1}x_n\leq(\frac{x_1+x_2+\cdots+x_{n-1}+x_n}{n})^n$$ 令$x_n=\frac{x_1+x_2+\cdots+x_{n-1}}{n-1}$，代入上式 $$x_1x_2\cdots x_{n-1}x_n\leq(\frac{(n-1)x_n+x_n}{n})^n=x_n^n$$ 所以 $$x_1x_2\cdots x_{n-1}\leq(\frac{(n-1)x_n+x_n}{n})^n=x_n^{n-1}=(\frac{x_1+x_2+\cdots+x_{n-1}}{n-1})^{n-1}$$ 所以$P(n-1)$成立。

令 $$\begin{aligned} x_a&=\frac{x_1+x_2+\cdots+x_n}{n}\\ x_b&=\frac{x_{n+1}+x_{n+2}+\cdots+x_{2n}}{n} \end{aligned}$$ 那么 $$\begin{aligned} x_1x_2\cdots x_{2n}&\leq x_a^nx_b^n\\ &=(x_ax_b)^n\\ &\leq(\frac{x_a+x_b}{2})^{2n}\\ &=(\frac{x_1+\cdots+x_n+x_{n+1}+\cdots+x_{2n}}{2n})^{2n} \end{aligned}$$ 所以$P(2n)$成立。

有了上述这些递推条件，$P(2)$成立，那么$P(4)$成立，那么$P(3)$成立，进而$P(6)$成立，那么$P(5)$成立。
找到最近的没有递归到的偶数项$2n$，之前已经有了$P(n)$成立，所以$P(2n)$成立，进而有$P(2n-1)$成立。

10

假设盘子移动顺序是$A\to B\to C\to A$。
先考虑$Q_n$，我们需要把$n-1$个盘子从$A$移动到$C$，让后把最大的盘子移动到$B$，最后把$C$上的$n-1$个盘子移动回$B$，那么$Q_n=R_{n-1}+1+R_{n-1}=2R_{n-1}+1$。
$R_n$稍微复杂点。首先需要把$n-1$个盘子移动到$C$，然后把最大的盘子移动到$B$，然后把$C$上的移动到$A$，接着才能把最大的移动到$C$，最后把$A$上的$n-1$个移动到$C$，那么$R_n=R_{n-1}+1+Q_{n-1}+1+R_{n-1}=Q_n+Q_{n-1}+1$。

11

如果没有圆盘，那么$A_0=0$。如果$n=1$，也就是两个圆盘，那么直接移动两次将圆盘移动到目标圆柱即可，$A_1=2$。对于$2n$个圆盘，我们移动$A_{n-1}$次将前面$2n-2$个移动到目标圆柱，然后移动两次把最大的两个圆盘移动到目标圆柱，再移动$A_{n-1}$次完成。所以$A_n=2A_{n-1}+2$，$A_n=2^{n+1}-2$。

第二问稍微复杂一点，给三个圆柱命名：$XYZ$。$B_0=0$。$n=1$时，首先把上面的圆盘从$X$移动到$Z$，然后把下面的圆盘从$X$移动到$Y$，最后把上面的圆盘从$Z$移动到$Y$，所以$B_1=3$。$2n$个圆盘时，先把前$2n-2$个移动到$Y$，$B_{n-1}$次，然后把最大的上面的圆盘移动到$Z$，1次，然后把前$2n-2$个移动到$Z$，$B_{n-1}$次，移动最大的下面的圆盘到$Y$，1次，把前$2n-2$个移动到$X$，$B_{n-1}$次，$Z$下面的圆盘移动到$Y$，1次，最后把$X$上的圆盘移动回$Y$，$B_{n-1}$次，那么$B_n=4B_{n-1}+3$，我这个过程明显比答案给出的多指数倍，因为递归系数高一倍。

从课后答案推最优解。首先需要说明的是，第一个问题的移动方式上下两块恰好颠倒了，我们称之为逆序。两次逆序会回归正序。前$2n-2$个移动到$Y$，逆序，$A_{n-1}$次，最大的两块逆序移动到$Z$，2次，$Y$上的逆序回$X$，$A_{n-1}$次，注意两次逆序回到了正序，即初始状态；然后最大的两块逆序回$Y$，2次，最后$X$的上面保持顺序到$Y$，$B_{n-1}$次，所以得到$B_n=2A_{n-1}+B_{n-1}+4=2^{n+2}-5$，注意，这个封闭写法要求$n>0$。

书中最后提示$B_n=A_{n-1}+1+A_{n-1}+1+A_{n-1}+1+A_{n-1}$，告诉我的算法中只需要把$B_{n-1}$替换成$A_{n-1}$即可，也就是移动前面$2n-2$个的时候不保持顺序，准确的说是逆序，而总共逆序了4次，最后顺序是对的。

12

与11第一问类似，移动最下面$m_n$个到另一个圆柱需要$m_n$次，还需要两次移动上面所有圆盘，所以$A(m_1,m_2,\cdots,m_n)=2A(m_1,m_2,\cdots,m_{n-1})+m_n=2^{n-1}m_1+2^{n-2}m_2+\cdots+2m_{n-1}+m_n$

13

每个$Z$和之前的$Z$相交，最多能产生9个交点，那么和前$n-1$个$Z$有$9n-9$个交点，那么是$9n-8$条线段或者射线，那么就会增加$9n-8$个区域，所以$Z_n=Z_{n-1}+9n-8$，题目给出$Z_1=2,Z_2=12$，那么 $$\begin{aligned} Z_n&=&&Z_{n-1}+9n-8\\ &=&&Z_{n-2}+9(n-1)-8+9n-8\\ &&&\vdots\\ &=&&Z_1+9\times 2-8+\cdots+9(n-1)-8+9n-8\\ &=&&2+9(S_n-1)-8(n-1)\\ &=&&9S_n-8n+1\\ &=&&\frac{9}{2}n^2-\frac{7}{2}n+1 \end{aligned}$$

14

这个问题比线分割平面高了一维，对于平面的问题，增加一条直线，和前面的线有若干个交点，那么会多出交点数加一个线段或者射线，也就增加这么多个区域，对于立体问题，增加一个平面，和前面的面有若干个交线，那么会多出一些有界区域或者无界区域，也就是增加这么多个空间数。

零个平面奶酪是一整块，$n=1$时被切成了两块。增加第$n$个平面，和前面$n-1$条线有$n-1$条交线，把新增的平面分割成$L_{n-1}$个区域，那么增加$L_{n-1}$个空间，所以$P_n=P_{n-1}+$L_{n-1}$$。列一个表格计算前几个数： | $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |--|--|--|--|--|--|--|--| | $P$ | 1 | 2 | 4 | 8 | 15 | 26 | 42 | | $L$ | 1 | 2 | 4 | 7 | 11 | 16 | 22|

15

首先研究几个比较小的情况 | $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |--|--|--|--|--|--|--|--| | $I$ | - | 2 | 1 | 3 | 5 | 1 | 3 |

排除前面两个值，后面的和$J(n)$类似。那么可以想到解与$J(n)$也是类似的。与推导$J(n)$类似，考虑$2n, 2n+1$两种情况。由于第一轮删除的人和原始的约瑟夫问题完全一样，所以递推式是一样的，不过$n$其实值不太一样，因为前几个情况不太一样。 $$\begin{aligned} I(2)&=2\\ I(3)&=1\\ I(2n)&=2I(n)-1,n\geq 2\\ I(2n+1)&=2I(n)+1,n\geq 2 \end{aligned}$$ 和原始问题一样，从$3=1+2$开始，长度是$3=1+2$的一个分组，下一组从$6=2(1+2)$开始，长度是$6=2\times 3$，依次类推，每组开始都是$2^m+2^{m-1}$，长度也是$2^m+2^{m-1}$。每组内部从1开始，依次加2，所以如果$n=2^m+2^{m-1}+k,0\leq k< 2^m+2^{m-1}$，那么 $$I(n)=2k+1,n> 2$$

16

令 $$g(n)=a(n)\alpha+b(n)\beta_0+c(n)\beta_1+d(n)\gamma$$ 代入$g(n)=n$，可以得到 $$\begin{aligned} 1&=\alpha\\ 2n&=3n+\gamma n+\beta_0\\ 2n+1&=3n+\gamma n+\beta_1 \end{aligned}$$ 所以$\alpha=1,\beta_0=0,\beta_1=1,\gamma=-1$，进而 $$g(n)=n=a(n)+c(n)-d(n)$$

如果$\gamma=0$，那么就退化成了$(1.17), (1.18)$，那么 $$\begin{aligned}g(n)&=a(n)\alpha+b(n)\beta_0+c(n)\beta_1\\ &=(\alpha\beta_{b_{m-1}}\beta_{b_{m-2}}\cdots\beta_{b_1}\beta_{b_0})_3\\ &=3^m\alpha+\sum_{i=0}^{m-1}\beta_{b_i}3^i \end{aligned}$$ 可以直观看出来$\alpha=3^m$。本质上说，$\beta_0,\beta_1$也包含在了这个式子里面。

TODO 问了个问题，是说如何从上面那个写在一起的求和式子中分离出这两者。但是没有人回答。或者做不到？或者很难？who knows...

代入$g(n)=1$，那么 $$\begin{aligned} 1&=\alpha\\ 1&=3+\gamma n+\beta_0\\ 1&=3+\gamma n+\beta_1 \end{aligned}$$ 所以$\alpha=1,\beta_0=-2,\beta_1=-2,\gamma=0$，进而 $$g(n)=1=a(n)-2b(n)-2c(n)$$