第一章习题解答
滑稽的小宫
·
·
个人记录
注：“略”的意思是答案浅显易懂，直接看书后答案就好了
热身题
1.1 所有的马都有同样的颜色
本题归纳过程如下：
-
基础：n=1 时，命题成立
-
归纳：n>2 时，n-1\geq 2 ，假设命题对 n-1 成立，那么：
-
结论：[1,n] 的马颜色相同
问题：中间跳过了 n=2 的情形，即没有证明任意两匹马都颜色相同。因此实际上如果任意两匹马颜色相同，那么所有马颜色相同就是不刊之论了。
1.2 不能直接移动的汉诺塔
小的情形：略
命名： 设 f(n) 为把n个圆盘的塔从A移到B所需方案数，称中间柱为C
求解：
过程分析：
- 将其他圆盘从A移动到B
- 移动最大圆盘到C
- 将其他圆盘从B移动到A
- 移动最大圆盘到B
- 将其他圆盘从A移动到B
可以证明这是最优策略，所以 f(n)=3f(n-1)+2
从进制角度考虑，就是一个全部为2的三进制数，因此 f(n)=3^n-1，归纳证明即可。
1.3 不能直接移动的汉诺塔之问题2
问的好奇怪，还是直接去看答案吧（“略”）
1.4 不规则的汉诺塔问题
不存在
转化题意为：证明：只要初始状态合法，那么 n 个圆盘的塔想要放在同一个柱上，最少操作次数不会超过 2^n-1
归纳证明：
- 基础：若只有一个圆盘， n=1 ，只需操作0或1次，不超过 2^1-1=1
- 归纳：假设命题对 n-1 成立
- 先用不超过 2^{n-1}-1 次操作将 n-1 个圆盘都移到非目标柱上
- 再将最大的圆盘移到目标柱上
- 再用不超过 2^{n-1}-1 次操作将其他圆盘移到目标柱上
- 对 n 个圆盘只需要不超过 2*2^{n-1}-2+1=2^n-1次移动
得证
1.5 多集合韦恩图问题
略
1.6 平面上的直线——有界区域问题
考虑有界区域产生的过程，当一条直线交其他不平行直线于多个点时，任意两个相邻点构成的线段必将划分出一个有界区域（而两边的射线则划分了无界区域），这是因为：
- 这条线段一定会包括在至少一个多边形内（所各自交的这两条直线不平行，所以一定会构成三角形），所以答案至少增加1.
- 而这个线段除了端点都不和其他直线相交，所以只会划分多一个有界区域，答案最多增加1.
另外，平行一定会使答案更劣，所以我们不会使直线平行。
因此我们只要让交点尽可能多
考虑现在有 n-1 个不平行直线，加入一条新的直线时，最多和其他直线交于 n-1 个点，产生 n-2 个线段，也就是 n-2 个有界区域
所以设 L(n) 表示 n 个直线最多交出的有界区域个数，就有：
L(n)=L(n-1)+(n-2)
展开得：
L(n)=(n-2)+(n-3)+\cdots+1=\frac{(n-1)(n-2)}{2},n>0
1.7 约瑟夫问题的幸存者偏“差”
该问题的归纳过程：
- 基础：不知道
- 归纳：若 n\geq 1，分奇偶讨论：
明显可以发现，该问题的基础是不清晰的，而且当我们试图找一个基础，就会发现 H(1)=0\neq 2 而 H(2)=2
因此进一步探究，就会发现所有依赖于 H(1) 的 n 都不满足 H(n)=1，其他的却满足。这些不满足的是 n=1,3,7,15\cdots，它们的二进制表示全部为1，因此无法依赖于一个偶数，最终只能依赖于 H(1)。而其他二进制表示中有0的 n 都满足 H(n)=2
1.8 大水题
略
1.9 均值不等式的证明
这里直接转化为证明均值不等式：
若 P(n) 成立，不妨令 x_n=\frac{(x_1+\cdots+x_{n-1})}{n-1}，则 x_n\geq 0
带入 P(n)，有
\begin{aligned}
x_1\cdots x_{n-1}\cdot\frac{(x_1+\cdots+x_{n-1})}{n-1}&\leq(\frac{(n-1)(x_1+\cdots+x_{n-1})+(x_1+\cdots+x_{n-1})}{n(n-1)})^n\\
x_1\cdots x_{n-1}\cdot\frac{(x_1+\cdots+x_{n-1})}{n-1}&\leq(\frac{x_1+\cdots+x_{n-1}}{n-1})^n\\
x_1\cdots x_{n-1}&\leq(\frac{x_1+\cdots+x_{n-1}}{n-1})^{n-1}\\
\end{aligned}
所以 P(n-1) 成立
已知 P(2) 成立，有：
\begin{aligned}
x_1x_{n+1}&\leq(\frac{x_1+x_{n+1}}{2})^2\\
x_2x_{n+2}&\leq(\frac{x_2+x_{n+2}}{2})^2\\
&\cdots\\
x_ix_{n+i}&\leq(\frac{x_i+x_{n+i}}{2})^2\\
&\cdots\\
x_nx_{2n}&\leq(\frac{x_n+x_{2n}}{2})^2\\
\end{aligned}
同向非负不等式相乘，得：
x_1\cdots x_{2n}\leq \left(\left(\frac{x_1+x_{n+1}}{2}\right)\cdots\left(\frac{x_n+x_{2n}}{2}\right)\right)^2
若 P(n) 成立，有：
\left(\left(\frac{x_1+x_{n+1}}{2}\right)\cdots\left(\frac{x_n+x_{2n}}{2}\right)\right)^2\leq \left(\frac{x_1+x_2+\cdots+x_{2n}}{2n}\right)^{2n}
综上：
x_1\cdots x_{2n}\leq \left(\frac{x_1+x_2+\cdots+x_{2n}}{2n}\right)^{2n}
可知 P(2n) 成立
归纳证明：
- 基础：P(1),P(2) 成立
- 归纳：n\geq 2,2n-1\geq 3 时，假设对于所有小于 2n-1 的情况命题都成立：
- 因为 P(n) 和 P(2) 成立且 n<2n-1，P(2n) 成立。
- 若 P(2n) 成立，则 P(2n-1) 成立
所以对于 n>2 的奇数和偶数，P(n) 成立
得证.
1.10 顺时针河内塔
证明：
设三个柱为ABC
实际上，题目中的 Q 就是顺时针转一个柱的最小步数，R 就是顺时针转两个柱的最小步数。
用同样的方法：对于 Q
- 我们必然要移动最大的圆盘一步到B，那么就需要让其他圆盘走到C
- 然后移动最大的圆盘到B
- 然后把C上的其他圆盘移动到B
所以 Q_n=2R_{n-1}+1,n>0
对于 R
- 我们必然要移动最大的圆盘到C，就先要移动到B，一共 R_{n-1}+1 步
- 接着其他在C上的圆盘要移到A，使得最大的圆盘可以移到C，一共 Q_{n-1}+1 步
- 最后其他圆盘要从A移到C上，共 R_{n-1} 步
所以 R_n=2R_{n-1}+1+Q_{n-1}+1=Q_n+Q_{n-1}+1,n>0
1.11 多重河内塔
a
设至少需要 A_n 次移动
由于每种盘有两个，可以用普通河内塔的思路，就是先用 A_{n-1} 步将前 n-1 种盘移到非目标柱上，然后用两步把第 n 种两个圆盘移到目标柱上，再用 A_{n-1} 步将其他盘移回目标柱，因此 A_{n}=2A_{n-1}+2
令 T_n=A_n+2,T_n=2T_{n-1},T_0=2，所以 T_n=2^{n+1},A_n=2^{n+1}-2
b
设至少需要 B_n 次移动
注意这次排序要保证稳定，因此我们移动两个盘的时候需要捯两次：
- 将其他盘移到C
- 将最大的两个盘移到B，顺序颠倒
- 将其他盘移回A
- 将最大的两个盘移到C，顺序恢复
- 将其他盘移到C
有人可能会以为，需要三次 B_{n-1} （好吧可能只有蒟蒻我会这么想），但是实际上前两次 n-1 组的移动不必有序，因此是 B_n=B_{n-1}+2A_{n-1}+4=B_{n-1}+2^{n+1}
由于 B_1=3，展开得 B_n=2^{n+1}+2^{n}+\cdots+2^{3}+3=2^{n+2}-1-2^2=2^{n+2}-5
1.12 上一题的推广
略
1.13 平面上的Z形线
答案给出的方法非常妙，这里给出一个略繁琐但好想的做法：
一个Z形线由两条平行射线和一个线段构成，我们不妨把它转化为两条平行直线和一条和这两条平行线都相交的直线，如图：
可以看到，Z形线只比三条直线的模型失去了四个区域（虚线划分出来的），如果我们安排得当（让定点在所有其他Z之外），那么这就是我们失去的全部。
因此我们转化一下模型来解决：
- 首先放置 n 组平行直线，设 L_n 为n组平行直线划分的区域个数
- 一条直线加入，可以交出 2n-2 个点，也就是划分 2n-1 个区域
- 总共区域个数：L_n=L_{n-1}+4n-2,L_0=1
- 等差数列求和：L_n=4*\frac{n(n+1)}{2}-2n+1=2n^2+10
- 然后放置 n 条直线，与原来直线都不平行
- 放置第 i 条直线时最多可以划分出 2n+i 个区域，因此等差数列求和：\frac{(2n+1+3n)n}{2}=\frac{5}{2}n^2+\frac{1}{2}n
- 最后减去每个Z失去的4个区域，就是 -4n
求和 Z_n=\frac{9}{2}n^2-\frac{7}{2}n+1
1.14 空间中的平面
略
1.15 倒数第二个幸存者
观察小的情形：I(2)=2,I(3)=1,I(4)=3,I(5)=5\cdots
命名并求解：
考虑一下和普通约瑟夫问题同样的过程，如果是奇数个人，那么走完一圈以后新的编号×2+1就是原来编号，如果是偶数个人，那么走完一圈以后新的编号×2-1就是原来的编号，因此递推式和普通约瑟夫问题一样：
\begin{aligned}
I(2)&=2;\\
I(3)&=1;\\
I(2n)&=2I(n)-1,n>1;\\
I(2n+1)&=2I(n)+1,n>1.
\end{aligned}
但是由于基础不一样，最终递推式的答案也不一样：
- 由于 I(3)=1 可以得到 I(6)=I(12)=I(24)=I(48)=I(3*2^m)=1
- 对于 I(3*2^m+l) 来说，相当于先去掉 l 个人，然后所在的位置就是倒数第二个幸存者
所以就有 I(3\cdot2^m+l)=2l+1
1.16 不成套的成套方法
设 g(n)=A(n)\alpha+B(n)\beta_0+C(n)\beta_1+D(n)\gamma
实际上这道题并不能直接用成套方法做，还是需要先进制展开：
根据不同基数的拓展约瑟夫问题，我们可以得到，当 \gamma=0 时
g((b_mb_{m-1}\cdots b_1b_0)_2)=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
就可以得到：若 n=(b_mb_{m-1}\cdots b_1b_0)_2
\begin{aligned}
A(n)&=(100\cdots)_3=3^m\\
B(n)&=(0100101\cdots)_3\\
C(n)&=(0011010\cdots)_3
\end{aligned}
其中 B(n) 中 b_i=0 的位置为1，C(n) 中 b_i=1 的位置为1（除了第一位）
然后为了和 D(n) 产生联系，我们尝试带入函数 g(n)=n，也就是说：
\begin{aligned}
\alpha&=1\\
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
因此 A(n)+C(n)-D(n)=n\Rightarrow D(n)=A(n)+C(n)-n
这样就都求出来了。
（实际上可以带入 g(n)=1 得到 A(n)-1=2B(n)+2C(n) 这个更简洁表示 B(n) 或 C(n) 的式子）