具体数学习题解答——第1章 递归问题 Part1

书籍介绍：

https://book.douban.com/subject/21323941/

github仓库：

https://github.com/Doraemonzzz/Concrete-Mathematics

记录具体数学一书中的习题解答，题目又多又难，所以计划是分为几轮完成，第一轮完成热身题，作业题以及考试题，第二轮再解决其余部分的习题。

这次回顾第一章，递归问题。

第1章 递归问题

热身题

1

错在base case，$n=2$时：

$$\begin{aligned} 1 : n -1&= 1:1\\ 2: n&= 2 :2 \end{aligned}$$

两个区间没有交集，所以无法使用上述证明。

2

移动过程：

步骤	$A$	$B$	$C$
$0$	$[1,\ldots, n]$	空	空
$1$	$[n]$	$[1,\ldots, n-1]$	空
$2$	空	$[1,\ldots, n-1]$	$[n]$
$3$	$[1,\ldots, n-1]$	空	$[n]$
$4$	$[1,\ldots, n-1]$	$[n]$	空
$5$	空	$[1,\ldots, n]$	空

记$n$个圆盘的最少移动次数为$T_n $，那么$T_n$满足

$$T_n\le 3T_{n-1}+2$$

下面证明反方向的不等号：

• $n$从$A$移动到$B$必然要先移动到$C$，此时$[1,\ldots,n-1]$必然在$B$，这部分移动次数至少为$1+T_{n-1}$
• 接着$n$从$C$移动到$B$，移动之前$[1,\ldots, n-1]$要先移动到$A$，这部分移动次数至少为$1+T_{n-1}$
• 最后要将$[1,\ldots, n-1]$从$A$移动到$B$，移动次数至少为$T_{n-1}$

所以

$$T_n \ge 3T_{n-1}+2$$

从而

$$T_n = 3T_{n-1}+2$$

求解可得

$$\begin{aligned} T_n+ 1&= 3(T_{n-1} + 1)\\ &= 3^{n-1}(T_1 + 1)\\ &= 3^n\\ T_n&= 3^n -1 \end{aligned}$$

3

备注：

正确的叠放是指，将$n$个圆盘分为三组，那么每组的顺序从小到大的。

记

• $T(n)$: 在2的限制下,我们会在3根桩柱上都遇到$n $个圆盘的每一种正确的叠放。

关于$n$做数学归纳法即可。

当$k =1$时，$k$的移动路径为$A\to C\to B$，所以结论成立。

假设当$k= n -1$时结论成立，下面证明$k=n$时结论也成立。

考虑之前的移动步骤：

步骤	$A$	$B$	$C$
$0$	$[1,\ldots, n]$	空	空
$1$	$[n]$	$[1,\ldots, n-1]$	空
$2$	空	$[1,\ldots, n-1]$	$[n]$
$3$	$[1,\ldots, n-1]$	空	$[n]$
$4$	$[1,\ldots, n-1]$	$[n]$	空
$5$	空	$[1,\ldots, n]$	空

考虑$n$在的位置：

如果$n$在$A$，由归纳假设可知将$[1,\ldots,n-1]$从$A$移动到$B$会遇到每一种正确的叠放，这也对应了$n$在$A$情形下每一种正确的叠放。

$n$在$B,C$的情形同理可得。

所以$k=n$时结论也成立。

4

记

• $T(n)$: 对于$n$个圆盘的任意摆列方式，按照卢卡斯原来的规则，最多需要$2^n-1$次移动将圆盘移动到$B$。

关于$n$做数学归纳法即可。

当$n=1$时结论显然。

假设当$n= m -1$时结论成立，下面证明$n=m$时结论也成立。

如果$m$在$B$，那么对剩余$n-1$个圆盘运用$T(n-1)$即可，移动次数

$$\le 2^{m-1} - 1 < 2^m -1$$

如果$m$不在$B$，由对称性不妨设$m$在$A$，那么移动过程如下：

• $[1,\ldots, m-1] \to C$
• $[m]\to B$
• $[1,\ldots, m-1] \to B$

所以移动次数

$$\le 1 + 2^{m-1} -1+2^{m-1} -1 \le 2^m -1$$

5

两个圆最多相交于两点，所以第$4$个圆最多和前$3$个圆交于$6$点，最多增加$6$块区域，所以总区域最多为

$$6+8 =14$$

补充说明：

答案中给的卵形和圆的最大不同之处在于，两个卵形可以有$4$个交点。

6

记$n$条直线产生的有界区域最大个数为$a_n$。

考虑第$n$条直线，该直线最多和$n-1$条直线相交，即产生$n-1$个交点，相邻两个点最多可以增加一个有界区域，所以最多增加$n-2$个有界区域，因此

$$\begin{aligned} a_n&= a_{n-1} + n-2\\ a_1&=a_2 =0\\ a_n & =a_1 + \sum_{i=0}^{n-2} i\\ &=\frac{(n-2)(n-1)}{2} \end{aligned}$$

7

$$\begin{aligned} H(1)&= J(2)- J(1)\\ &= 2J(1)-1-J(1)\\ &=0 \end{aligned}$$

即base case结论都不成立，所以无法使用数学归纳法。

作业题

8

$$\begin{aligned} Q_0&= \alpha\\ Q_1&= \beta\\ Q_2&=\frac{1+Q_1}{Q_0}\\ &= \frac{1+\beta}{\alpha}\\ Q_3&=\frac{1+Q_2}{Q_1}\\ &= \frac{1+\frac{1+\beta}{\alpha}}{\beta}\\ &= \frac{1+\alpha+\beta}{\alpha \beta}\\ Q_4&=\frac{1+Q_3}{Q_2}\\ &= \frac{1+\frac{1+\alpha+\beta}{\alpha \beta}}{ \frac{1+\beta}{\alpha}}\\ &= \frac{1+\alpha+\beta+\alpha\beta}{(1+\beta) \beta}\\ &=\frac{1+\alpha}{\beta}\\ Q_5 &= \frac{1+\frac{1+\alpha}{\beta}}{\frac{1+\alpha+\beta}{\alpha \beta}}\\ &=\alpha\\ Q_6&=\frac{1+Q_5}{Q_4}\\ &=\frac{1 + \alpha}{\frac{1+\alpha}{\beta}}\\ &=\beta \end{aligned}$$

所以

$$Q_{k} =Q_{k-5},k\ge 5$$

$Q=0,\ldots, 4$的定义如上。

9

(a)

假设$P(n)$成立，令

$$x_{n}=\left(x_{1}+\ldots+x_{n-1}\right) /(n-1)$$

那么

$$\begin{aligned} \frac{x_{1}+\ldots+x_{n}}{n} &= \frac{x_{1}+\ldots+x_{n-1}+\left(x_{1}+\ldots+x_{n-1}\right) /(n-1)}{n}\\ &= \frac{x_{1}+\ldots+x_{n-1}}{n-1} \end{aligned}$$

所以

$$\begin{aligned} x_{1} \ldots x_{n} &\le \left(\frac{x_{1}+\ldots+x_{n}}{n}\right)^{n} \Leftrightarrow\\ x_{1} \ldots x_{n-1}\frac{x_{1}+\ldots+x_{n-1}}{n-1} &\le \left( \frac{x_{1}+\ldots+x_{n-1}}{n-1}\right)^n \Leftrightarrow\\ x_{1} \ldots x_{n-1}&\le \left( \frac{x_{1}+\ldots+x_{n-1}}{n-1}\right)^{n-1} \end{aligned}$$

所以$P(n)\Rightarrow P(n-1)$。

(b)

如果$P(n), P(2)$成立，那么

$$\begin{aligned} \prod_{i=1}^{2n} x_i &= \left(\prod_{i=1}^{n} x_i\right) \times \left(\prod_{i=n+1}^{2n} x_i\right)\\ &\le \left(\frac 1 n \sum_{i=1}^{n} x_i\right)^n \times \left(\frac 1 n\sum_{i=n+1}^{2n} x_i\right)^n\\ &\le \left(\left(\frac 1 n \sum_{i=1}^{n} x_i \right) \times \left(\frac 1 n \sum_{i=n + 1}^{2n} x_i \right)\right)^n\\ &\le \left(\left(\frac 1 {2n} \sum_{i=1}^{2n} x_i\right)^2\right)^n\\ &=\left(\frac 1 {2n} \sum_{i=1}^{2n} x_i\right)^{2n} \end{aligned}$$

所以$P(2n)$成立。

(c)

首先由$P(2)$成立以及(b)的结论可得$P(2^{k})$成立。

接着，对于任意$n \neq 2^k$，总存在$k$，满足$n< 2^k $，所以由(a)可得

$$P(2^k)\Rightarrow P(2^k -1) \Rightarrow\ldots \Rightarrow P(n)$$

从而$P(n)$成立。

10

$A\to B$：

步骤	$A$	$B$	$C$
$0$	$[1,\ldots, n]$	空	空
$1$	$[n]$	空	$[1,\ldots, n-1]$
$2$	空	$[n]$	$[1,\ldots, n-1]$
$3$	空	$[1,\ldots, n]$	空

注意到$A\to C, C\to B$和$B\to A$等价，所以

$$Q_n \le 2 R_{n-1}+1$$

另一方面，要使得第$n$个圆盘移动到$B$，该步骤至少要$1$次，并且此时前$n-1$个圆盘应该在$C$，$A\to C$的最少步骤数为$R_{n-1}$，$C\to B$的最少步骤数为$R_{n-1}$，所以

$$Q_n \ge 2 R_{n-1}+1$$

综上

$$Q_{n}=\left\{\begin{array}{cc} 0, & n=0 \\ 2 R_{n-1}+1, & n>0 \end{array}\right.$$

$B\to A$：

步骤	$A$	$B$	$C$
$0$	空	$[1,\ldots, n]$	空
$1$	$[1,\ldots, n-1]$	$[n] $	空
$2$	$[1,\ldots, n-1]$	空	$[n]$
$3$	空	$[1,\ldots, n-1]$	$[n]$
$4$	$[n]$	$[1,\ldots, n-1]$	空
$5$	$[1,\ldots, n]$	空	空

所以

$$\begin{aligned} R_n &\le 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 \end{aligned}$$

另一方面，第$n$个圆盘从$B$到$A$必然要经历两步：

• 第一步：$B\to C$，此时前$n-1$个圆盘必然在$A$，即前$n-1$个圆盘要从$B$移动到$A$，这部分的步骤数$\ge R_{n-1}+1$
• 第二步：$C\to A$，此时前$n-1$个圆盘必然在$B$，即前$n-1$个圆盘要从$A$移动到$B$，所以这部分的步骤数$\ge Q_{n-1}+1$
• 第三步：将$B$上的圆盘移动到$A$，这步分的步骤数$\ge R_{n-1}$

所以

$$\begin{aligned} R_n &\ge 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 \end{aligned}$$

综上

$$R_{n}=\left\{\begin{array}{cc} 0, & n=0 \\ Q_{n}+Q_{n-1}+1, & n>0 \end{array}\right.$$

11

(a)

先将前$2n-2$个圆盘移动到$C$，然后将最后两个圆盘移动到$B$，最后将$C$上的圆盘移动到$B$，所以递推关系为

$$\begin{aligned} A_n &=2 A_{n-1}+2\\ A_1 &= 2\\ \end{aligned}$$

求解可得

$$\begin{aligned} A_n+2 & =2(A_{n-1} +2)\\ &= 2^{n-1}(A_1 + 2)\\ &= 2^{n+1}\\ A_n &= 2^{n+1}-2 \end{aligned}$$

注意这种移动方式保持尺寸大小$\le n-1$的圆盘顺序不变，尺寸大小为$n$的圆盘顺序相反（利用归纳法可证）。

(b)

显然

$$B_1 = 3$$

$B\to A$有如下移动方式：

步骤	$A$	$B$	$C$	步骤数
$0$	$[1,-1,\ldots, n,-n]$	空	空	$0$
$1$	$[n, -n]$	$[1,-1\ldots,-(n-1), (n-1)]$	空	$A_{n-1}$
$2$	$[-n]$	$[1,-1\ldots,-(n-1), (n-1)]$	$[n]$	$1$
$3$	$[-n] $	空	$[1,-1\ldots,(n-1), -(n-1),n]$	$A_{n-1}$
$4$	空	$[-n]$	$[1,-1\ldots,(n-1), -(n-1),n]$	$1$
$5$	$[1,-1\ldots,-(n-1), (n-1),n]$	$[-n]$	$[n]$	$A_{n-1}$
$6$	$[1,-1\ldots,-(n-1), (n-1),n]$	$[n,-n]$	空	$1$
$7$	空	$[1,-1,\ldots,(n-1), -(n-1), n,-n]$	空	$A_{n-1}$

所以

$$B_n \le 4A_{n-1}+3$$

另一方面，$[n,-n]$按照顺序从$A$到$B$至少需要$3$次，具体如下：

• $n: A\to C$，要使得这步能移动，前$2n-2$个圆盘必然在$B$，这部分的步骤数$\ge A_{n-1}+1$
• $-n:A\to B$，要使得这步能移动，前$2n-2$个圆盘必然在$C$，这部分的步骤数$\ge A_{n-1}+1$
• $n:C\to B$，要使得这步能移动，前$2n-2$个圆盘必然在$A$，这部分的步骤数$\ge A_{n-1}+1$
• 最后将$A$上的圆盘移动到$B$，这部分的步骤数$\ge A_{n-1}$

所以

$$B_n \ge 4A_{n-1}+3$$

有注意按照(a)的方式操作$4$次，最终顺序必然是原始的顺序，从而上述不等号可以取到等号。

因此

$$B_n = 4A_{n-1}+3 =2^{n+3}-5$$

12

不妨假设

$$m_1\le m_2\le \ldots \le m_k$$

基本情形：

$n=1$，此时

$$A\left(m_{1}, \ldots, m_{n}\right) =A(m_1)= m_1$$

一般情形：

第一步，把大小为$1,\ldots, n-1$的圆盘移动到另一棵柱子上，接着把$m_n$个大小为$n$的柱子移动到目标柱上，最后把大小为$1,\ldots, n-1$的圆盘移动到目标柱上，递推关系如下：

$$A\left(m_{1}, \ldots, m_{n}\right)= 2A\left(m_{1}, \ldots, m_{n-1}\right) + m_n$$

递推可得

$$\begin{aligned} A\left(m_{1}, \ldots, m_{n}\right) &= 2A\left(m_{1}, \ldots, m_{n-1}\right) + m_n\\ &= 2^2 A\left(m_{1}, \ldots, m_{n-2}\right) + 2m_{n-1} + m_n\\ &= \ldots\\ &= 2^{n-1} A(m_1) + \sum_{i=0}^{n-2} 2^im_{n-i}\\ &=\sum_{i=0}^{n-1} 2^im_{n-i} \end{aligned}$$

如果

$$m_i = 2$$

那么

$$\begin{aligned} A\left(m_{1}, \ldots, m_{n}\right) &=\sum_{i=0}^{n-1} 2^im_{n-i}\\ &= \sum_{i=0}^{n-1} 2^{i+1}\\ &= 2(2^n-1)\\ &=2^{n+1}-2 \end{aligned}$$

注意这种移动方式同样保持尺寸大小$\le n-1$的圆盘顺序不变，尺寸大小为$n$的圆盘顺序相反。

补充

同样的，可以计算$B(m_1,\ldots, m_n)$。

情形1：$n=1$。

将前$m_1-1$个圆盘移动到另一棵柱子上（此时反序），然后将第$m_1$个圆盘移动到目标柱上，最后将另一棵柱子上的圆盘移动到目标柱上，因此

$$\begin{aligned} B\left(m_{1}, \ldots, m_{n}\right) &=B(m_1)\\ &= 2(m_1-1) +1\\ &=2m_1-1 \end{aligned}$$

情形2：$m_n=1$。

此时利用之前的移动方式即可（因为一个元素反序等于没有反序），因此

$$B\left(m_{1}, \ldots, m_{n}\right) =A\left(m_{1}, \ldots, m_{n}\right)$$

情形3：一般情形。

第一步，利用之前的方式将除了最后一个圆盘移动到另一个圆柱上，这一步的操作步数为

$$A\left(m_{1}, \ldots, m_{n} -1\right)$$

第二步，将最后一个圆盘移动到目标柱上，这一步的操作步数为

$$1$$

第三步，将另一个圆盘上的元素移动到目标柱上，这一步的操作步数为

$$A\left(m_{1}, \ldots, m_{n} -1\right)$$

注意到这样操作后，顺序不变，因此

$$\begin{aligned} B\left(m_{1}, \ldots, m_{n}\right) &=2A\left(m_{1}, \ldots, m_{n} -1\right)+1\\ &= 2\left( m_n -1+ \sum_{i=1}^{n-1} 2^im_{n-i} \right)+1\\ &= \sum_{i=0}^{n-1} 2^{i+1}m_{n-i} -1 \end{aligned}$$

对比答案中的结果：

$$B\left(m_{1}, \ldots, m_{n}\right)=\begin{cases} A\left(m_{1}, \ldots, m_{n}\right), &m_{n}=1 \\ 2 m_{n}-1, & n=1 \\ 2 A\left(m_{1}, \ldots, m_{n-1}\right)+2 m_{n}+B\left(m_{1}, \ldots, m_{n-1}\right)& n>1 \text { 且 } m_{n}>1 \end{cases}$$

求解该式：

$$\begin{aligned} B\left(m_{1}, \ldots, m_{n}\right) - B\left(m_{1}, \ldots, m_{n-1}\right) &= 2 A\left(m_{1}, \ldots, m_{n-1}\right)+2 m_{n}\\ B\left(m_{1}, \ldots, m_{n}\right) - B(m_1) &= 2\sum_{i=1}^{n-1}A\left(m_{1}, \ldots, m_{i}\right) + 2 \sum_{i=2}^{n} m_i\\ B\left(m_{1}, \ldots, m_{n}\right)&= 2\sum_{i=1}^{n-1}A\left(m_{1}, \ldots, m_{i}\right) + 2 \sum_{i=1}^{n} m_i -1\\ &= 2\sum_{i=1}^{n-1} \sum_{j=0}^{i-1} 2^jm_{i-j}+ 2 \sum_{i=1}^{n} m_i -1\\ &= 2 \sum_{i=1}^{n-1} \sum_{j=1}^{i} 2^{i-j}m_{j}+ 2 \sum_{i=1}^{n} m_i -1\\ &= 2\sum_{j=1}^{n-1} \sum_{i=j}^{n-1}2^{i-j}m_{j}+ 2 \sum_{i=1}^{n} m_i -1\\ &= 2\sum_{j=1}^{n-1} (2^{n-j} - 1)m_{j}+ 2 \sum_{i=1}^{n} m_i -1\\ &= \sum_{j=1}^{n-1} 2^{n+1-j} m_{j}+ 2 m_n -1\\ &= \sum_{j=1}^{n} 2^{n+1-j} m_{j} -1\\ &= \sum_{i=0}^{n-1} 2^{i+1}m_{n-i} -1 \end{aligned}$$

13

考虑$ZZ_{n-1}$到$ZZ_n$的变化，因为$Z$一共有三段，每一段和之前$3(n-1)$条线最多交于$3(n-1)$个交点，所以增加的区域数量为

$$3\times (3(n-1)+1) = 9n-6$$

另一方面，对于线段部分，有两个增加的区域是和射线部分构成的三角形，这部分重复计算了，所以实际上增加的区域数量为

$$9n-6-2=9n-8$$

所以递推关系为

$$\begin{aligned} ZZ_{n}&= ZZ_{n-1} + 9n-8\\ ZZ_1 &=2=9\times 1 - 8+1 \end{aligned}$$

因此

$$\begin{aligned} ZZ_n &= 9\sum_{i=1}^n i- 8n +1\\ &=9\frac{n(n+1)}{2} -8n +1\\ &=\frac{9}{2}n^2 -\frac 7 2 n +1 \end{aligned}$$

14

考虑$P_n$和$P_{n-1}$的递推关系，将前$n-1$个平面投影到第$n$个平面上，那么第$n$个平面被划分为$L_{n-1}$个区域，所以

$$P_n = P_{n-1} + L_{n-1}$$

所以很容易将此推广到高维空间。

对于$k$维空间，被$n$个$k-1$维超平面最多的划分数量为$P_n^{k}$，那么

$$P_{n}^k = P_{n-1}^{k} + P^{k-1}_{n-1}$$

特别的

$$P_n^1 =1+ n$$

下面证明

$$P_{n}^k =\sum_{i=0}^k \binom n i$$

利用数学归纳法证明该结论。

$k=1$时，即为线段情形，显然有

$$P_{n}^k =\sum_{i=0}^k \binom n i =n +1$$

$n=0$时，

$$P_{n}^k =\sum_{i=0}^k \binom 0 i =1$$

假设结论对于$n’\le n-1, k’ \le k-1$时结论成立，那么

$$\begin{aligned} P_{n}^k - P_{n-1}^{k} &= P^{k-1}_{n-1} \\ P_{n-1}^k - P_{n-2}^{k} &= P^{k-1}_{n-2} \\ \ldots \\ P_{1}^k - P_{0}^{k} &= P^{k-1}_{0} \\ P_n^k - 1&= \sum_{i=0}^{n-1}P^{k-1}_{i}\\ P_n^k & = 1+\sum_{i=0}^{n-1}P^{k-1}_{i} \\ &=1+\sum_{i=0}^{n-1} \sum_{j=0}^{k-1} \binom i j\\ &= 1+\sum_{j=0}^{k-1}\sum_{i=j}^{n-1} \binom i j\\ &= 1+\sum_{j=0}^{k-1} \binom {n} {j+1}\\ &= 1+\sum_{j=1}^{k} \binom {n} {j}\\ &= \sum_{j=0}^{k} \binom {n} {j} \end{aligned}$$

所以结论对$n’=n,k’=k$也成立，从而结论得证。

备注：

这里利用了如下恒等式

$$\sum_{j=i}^n\binom j i =\binom {n+1} {i+1}$$

15

显然$I(n)$和$J(n)$的递推关系相同，为

$$\begin{aligned} I(2 n+j) &=2 I(n)+\beta_{j}, \quad j=0,1\\ \beta_0 &= -1\\ \beta_1 & = 1\\ I(2) & = 2\\ I(3)&=1 \end{aligned}$$

其中$I(1)$无定义。

利用二进制表示法

$$n=\left(b_{m} b_{m-1} \ldots b_{1} b_{0}\right)_{2}, b_m=1$$

我们有

$$\begin{aligned} I\left(\left(b_{m} b_{m-1} \ldots b_{1} b_{0}\right)_{2}\right) &=2 I\left(\left(b_{m} b_{m-1} \ldots b_{1}\right)_{2}\right)+\beta_{b_{0}} \\ &=4 I\left(\left(b_{m} b_{m-1} \ldots b_{2}\right)_{2}\right)+2 \beta_{b_{1}}+\beta_{b_{0}} \\ &= \ldots \\ &=2^{m-1} f\left(\left(b_{m} b_{m-1}\right)_{2}\right)+ \sum_{i=0}^{m-2}\beta_{b_i}\\ &=\begin{cases} 2^{m-1} + \sum_{i=0}^{m-2}\beta_{b_i}& b_{m-1}=1\\ 2^m + \sum_{i=0}^{m-2}\beta_{b_i}& b_{m-1} =0 \end{cases}\\ &= \begin{cases} \left(0 1 \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{2}& b_{m-1}=1\\ \left( 10 \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{2}& b_{m-1} =0 \end{cases} \end{aligned}$$

注意到第一种情形对应$n\ge 2^{m} + 2^{m-1}$，第二种情形对应于$n < 2^m + 2^{m-1}$，那么

$$\begin{aligned} J(n) &=\left( 1\beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{2}\\ &= \begin{cases} \left(1 1 \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{2}& b_{m-1}=1\\ \left( 1(-1) \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{2}& b_{m-1} =0 \end{cases}\\ &= \begin{cases} I(n)+2^{m}& b_{m-1}=1\\ I(n)-2^{m-1}& b_{m-1} =0 \end{cases} \end{aligned}$$

即

$$\begin{aligned} I(n) &= \begin{cases} J(n)-2^{m}& n\ge 2^{m} + 2^{m-1}\\ J(n)+2^{m-1}& n < 2^m + 2^{m-1} \end{cases} \end{aligned}$$

16

由递推式

$$\begin{aligned} g(1)&=\alpha \\ g(2 n+j)&=3 g(n)+\gamma n+\beta_{j} ; \quad j=0,1, \quad n \ge 1 \end{aligned}$$

可设

$$g(n)=A(n) \alpha+B_0(n) \beta_0+B_1(n) \beta_1+C(n) \gamma$$

(1)

取$\gamma = 0$，那么利用13页的(1.18)可得

$$\begin{aligned} g\left(\left(b_{m} b_{m-1} \ldots b_{1} b_{0}\right)_{2}\right) &=g\left(\left(1 b_{m-1} \ldots b_{1} b_{0}\right)_{2}\right)\\ &=\left(\alpha_{b_{m}} \beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_3\\ &=\left(\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_3\\ &=3^m\alpha + \sum_{i=0}^{m-1} \beta_{b_i} 3^i\\ &= 3^m\alpha +\left(\sum_{i\in \{i|b_i=0, i <m\}} 3^i \right) \beta_0 +\left(\sum_{i\in \{i|b_i=1, i <m\}} 3^i \right) \beta_1\\ &=A(n) \alpha+B_0(n) \beta_0+B_1(n) \beta_1 \end{aligned}$$

其中

$$\begin{aligned} n &=2^m + l\\ &=\left(b_{m} b_{m-1} \ldots b_{1} b_{0}\right)_{2}\\ &=\left(1 b_{m-1} \ldots b_{1} b_{0}\right)_{2}\\ &0\le l < 2^{m} , m=0,1,\ldots \end{aligned}$$

因此

$$\begin{aligned} A(n)&= 3^m \\ B_0(n)&=\sum_{i\in \{i|b_i=0, i <m\}} 3^i \\ B_1(n)&=\sum_{i\in \{i|b_i=1, i <m\}} 3^i \\ n &= \left(1 b_{m-1} \ldots b_{1} b_{0}\right)_{2} \end{aligned}$$

(2)

取$g(n)=n$，我们有

$$\begin{aligned} 1&=\alpha \\ 2n +j &=3n +\gamma n +\beta_j, j=0,1 \end{aligned}$$

那么

$$\begin{aligned} \alpha &= 1\\ \gamma &=-1\\ \beta_j&=j , j=0,1 \end{aligned}$$

是使得上式恒成立的参数，因此

$$\begin{aligned} g(n)&=n\\ &=A(n) \alpha+B_0(n) \beta_0+B_1(n) \beta_1+C(n) \gamma\\ &= A(n)+B_1(n) -C(n) \end{aligned}$$

由此可得

$$C(n)= n- A(n)- B_1(n)$$

(3)

取$g(n)=1$，我们有

$$\begin{aligned} 1&=\alpha \\ 1 &=3 +\gamma n +\beta_j, j=0,1 \end{aligned}$$

那么

$$\begin{aligned} \alpha &= 1\\ \gamma &=0\\ \beta_j&=-2 , j=0,1 \end{aligned}$$

是使得上式恒成立的参数，因此

$$\begin{aligned} g(n)&=1\\ &=A(n) \alpha+B_0(n) \beta_0+B_1(n) \beta_1+C(n) \gamma\\ &= A(n)-2B_0(n) -2B_1(n) \end{aligned}$$

将之前的结论代入验证这点：

$$\begin{aligned} A(n)-2B_0(n) -2B_1(n) &= 3^m - 2\left(\sum_{i\in \{i|b_i=0, i <m\}} 3^i+\sum_{i\in \{i|b_i=1, i <m\}} 3^i\right)\\ &=3^m - 2\left(\sum_{i\in \{i|b_i=0, i <m\}} 3^i+\sum_{i\in \{i|b_i=1, i <m\}} 3^i\right)\\ &= 3^m -2 \sum_{i=0}^{m-1} 3^i \\ &=1 \end{aligned}$$

结论成立。

考试题

17

假设$4$根柱子是的$a,b,c,d$，圆盘当前在柱子$a$上，目标是移动到柱子$b$上。

对于$W_{n(n+1) / 2}$，考虑如下移动方式：

• 将前$n(n-1) / 2$个圆盘移动到$c$（可以使用$4$根柱子）
• 将最后$n$个圆盘移动到$b$（可以使用$3$根柱子）
• 将$c$上的$n(n-1) / 2$个圆盘移动到$b$（可以使用$4$根柱子）

所以：

$$W_{n(n+1) / 2} \le 2 W_{n(n-1) / 2}+T_{n}$$

记

$$a_n = n(n+1) / 2$$

然后对不等式两边同除$2^n$，我们有

$$\frac{W_{a_n}} {2^n} \le \frac{W_{a_{n-1}}}{2^{n-1}}+\frac{T_{n}}{2^n}$$

累加可得

$$\begin{aligned} \frac{W_{a_n}} {2^n} &\le \frac{W_{a_{n-1}}}{2^{n-1}}+\frac{T_{n}}{2^n}\\ \frac{W_{a_{n-1}}} {2^{n-1}} &\le \frac{W_{a_{n-2}}}{2^{n-2}}+\frac{T_{n-1}}{2^{n-1}}\\ &\ldots\\ \frac{W_{a_1}} {2^1} &\le \frac{W_{a_{0}}}{2^{0}}+\frac{T_{1}}{2^1}\\ \end{aligned}$$

累加可得

$$\begin{aligned} \frac{W_{a_n}} {2^n} &\le \frac{W_{a_{0}}}{2^{0}} + \sum_{i=1}^n \frac{T_{i}}{2^i}\\ &= \sum_{i=1}^n \frac{2^i - 1}{2^i}\\ &= n - \sum_{i=1}^n 2^{-i}\\ &=n-(1- 2^{-n})\\ &= n - 1+2^{-n}\\ W_{n(n+1) / 2} &\le 2^n(n-1) +1 \end{aligned}$$

18

只需证明$n\ge 2$时的结论，因为$n=1$时结论显然。

只要说明，折线对应的$2n$条直线都不平行，并且，$2n$条直线中任意三条直线不交与一点即可。

对于第一个结论，第$j$条折线的两部分斜率的倒数分别为：

$$\begin{aligned} k_1^{j} & = -n^j\\ k_2^{j} & = -n^j - n^{-n} \end{aligned}$$

所以折线对应的$2n$条直线都不平行。

对于第二个结论，分两种情形讨论：

1. 两条直线来自于一组折线$j$，此时交点为$(n^{2j},0)$，另一条上直线必然不可能交于这点。

2. 三条直线分别来自于不同折线，注意到折线$j$对应的直线可以写成

   $$x=k^{j}_iy + n^{2j}$$

   所以条直线的交点为

   $$\begin{aligned} k^{j_1}_{i_1} y+ n^{2j_1}&=k^{j_2}_{i_2} y+n^{2j_2} \\ y&= -\frac{ n^{2j_1} -n^{2j_2}}{k^{j_1}_{i_1} - k^{j_2}_{i_2}} \end{aligned}$$

   对于该交点，一共有四种情形（假设$j_1 > j_2$）：

   • $i_1= i_2 = 1$：

     • $$\begin{aligned} y &= -\frac{n^{2j_1} -n^{2j_2}}{ -n^{j_1} +n^{j_2}}\\ &= n^{j_1} + n^{j_2} \end{aligned}$$

   • $i_1= 1, i_2= 2$：

     • $$\begin{aligned} y &= -\frac{n^{2j_1} -n^{2j_2}}{ -n^{j_1} +n^{j_2} + n^{-n}}\\ &= \frac{n^{2j_1} -n^{2j_2}}{ n^{j_1} -n^{j_2} -n^{-n}} \end{aligned}$$

   • $i_1= i_2 = 2$：

     • $$\begin{aligned} y &=-\frac{n^{2j_1} -n^{2j_2}}{ -n^{j_1} -n^{-n}+n^{j_2}+n^{-n}}\\ &= -\frac{n^{2j_1} -n^{2j_2}}{ -n^{j_1} +n^{j_2}}\\ &= n^{j_1} + n^{j_2} \end{aligned}$$

• $i_1= 2, i_2= 1$：

  • $$\begin{aligned} y &= -\frac{n^{2j_1} -n^{2j_2}}{ -n^{j_1}-n^{-n}+n^{j_2} }\\ &= \frac{n^{2j_1} -n^{2j_2}}{ n^{j_1}-n^{j_2} +n^{-n}} \end{aligned}$$

    注意到

    $$\begin{aligned} n^n (n^{j_1} -n^{j_2}) &= n^n n^{j_2} (n^{j_1-j_2} -1)\\ &\ge n^n n^{j_2} (3-1) \\ &= n^n n^{j_2} + n^n n^{j_2} \\ &\ge n^{j_1} + 2^2 n^{j_2}\\ &\ge n^{j_1} +n^{j_2} +1\\ &\ge n^{j_1} +n^{j_2} -1\\ n^{-n}&\le \frac {n^{j_1} -n^{j_2}}{ n^{j_1} +n^{j_2} +1}\\ n^{-n}&\le \frac {n^{j_1} -n^{j_2}}{ n^{j_1} +n^{j_2} -1} \end{aligned}$$

    所以

    $$\begin{aligned} \frac{n^{2j_1} -n^{2j_2}}{ n^{j_1} -n^{j_2} -n^{-n}} &\le \frac{n^{2j_1} -n^{2j_2}}{n^{j_1} -n^{j_2} -\frac {n^{j_1} -n^{j_2}}{ n^{j_1} +n^{j_2} +1}}\\ &= \frac{n^{j_1} +n^{j_2}}{1 -\frac {1}{ n^{j_1} +n^{j_2} +1}}\\ &=n^{j_1} +n^{j_2} +1\\ \frac{n^{2j_1} -n^{2j_2}}{ n^{j_1} -n^{j_2} +n^{-n}} &\ge \frac{n^{2j_1} -n^{2j_2}}{n^{j_1} -n^{j_2} +\frac {n^{j_1} -n^{j_2}}{ n^{j_1} +n^{j_2} -1}}\\ &\ge \frac{n^{j_1} +n^{j_2}}{1 +\frac {1}{ n^{j_1} +n^{j_2} -1}}\\ &=n^{j_1} +n^{j_2} -1\\ \end{aligned}$$

    即交点的纵坐标属于区间

    $$[n^{j_1} +n^{j_2} -1, n^{j_1} +n^{j_2} +1]$$

    对于$j_2\neq j_3$，显然有

    $$[n^{j_1} +n^{j_2} -1, n^{j_1} +n^{j_2} +1] \cap [n^{j_1} +n^{j_3} -1, n^{j_1} +n^{j_3} +1] =\varnothing$$

    现在考虑直线$j_1,j_2,j_3$，其中$(j_1>j_2>j_3)$，$j_2$，$j_3$和$j_1$的交点记为$y_{j_1,j_2},y_{j_1,j_3}$，因为$y_{j_1,j_2},y_{j_1,j_3}$属于不相交的区间，所以

    $$y_{j_1,j_2}\neq y_{j_1,j_3}$$

    这就说明任意三条直线不交于一点。

19

考虑两个折线相交的情形，最优的情况应该是两条折线有$4$个交点。

考虑如下三图，其中$\angle AO_1 B= \angle GO_2 B = \angle CO_3 D =\pi / 6 $。

$\angle DO_1 B \le \pi / 6$，此时只有$3$个交点：

$\pi / 6<\angle DO_1 B < 5\pi /6$，此时有$4$个交点：

$ 5\pi / 6 \le \angle DO_1 B \le \pi $，此时只有$3$个交点：

对每个折线，利用参数$(x, y, \theta)$描述，（$x,y$为直线交点的坐标，$\theta$为直线和水平方向夹角，另一条直线和水平方向的夹角为$\theta+\pi /6$）那么从上图中可以看出，两个折线有$4$个交点当且仅当

$$\pi / 6 < |\theta_1 - \theta_2| < 5\pi / 6$$

对于$n$个折线，至少存在两个折线的夹角之差$\le {2\pi }/{n}$，所以如果

$${2\pi }/{n} < \pi / 6 \Leftrightarrow n > 12$$

那么必然存在两个折线的交点不是$4$个，所以结论不成立。

从之前讨论中，不难将结论推广如下：

记第$n$条折线的夹角为$\theta_n\in [0, \pi)$，如果

$$\lim_{n\to\infty}\inf \theta_n \neq 0$$

那么当$n$充分大时，$n$条折线必然无法得到$Z_n$个区域。

20

由递推式

$$\begin{aligned} h(1)&=\alpha \\ h(2 n+j)&=4 h(n)+\gamma_{j} n+\beta_{j}, \quad j=0,1, \quad n \ge 1 \end{aligned}$$

可设

$$h(n)=A(n) \alpha+B_0(n) \beta_0+B_1(n) \beta_1+C_0(n) \gamma_0+C_1(n) \gamma_1$$

取$\gamma_j = 0,j =0,1$，那么利用13页的(1.18)可得

$$\begin{aligned} h\left(\left(b_{m} b_{m-1} \ldots b_{1} b_{0}\right)_{2}\right) &=g\left(\left(1 b_{m-1} \ldots b_{1} b_{0}\right)_{2}\right)\\ &=\left(\alpha_{b_{m}} \beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_4\\ &=\left(\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_4\\ &=4^m\alpha + \sum_{i=0}^{m-1} \beta_{b_i} 4^i\\ &= 4^m\alpha +\left(\sum_{i\in \{i|b_i=0, i <m\}} 4^i \right) \beta_0 +\left(\sum_{i\in \{i|b_i=1, i <m\}} 4^i \right) \beta_1\\ &=A(n) \alpha+B_0(n) \beta_0+B_1(n) \beta_1 \end{aligned}$$

其中

$$\begin{aligned} n &=2^m + l\\ &=\left(b_{m} b_{m-1} \ldots b_{1} b_{0}\right)_{2}\\ &=\left(1 b_{m-1} \ldots b_{1} b_{0}\right)_{2}\\ &0\le l < 2^{m} , m=0,1,\ldots \end{aligned}$$

因此

$$\begin{aligned} A(n)&=4^m \\ B_0(n)&=\sum_{i\in \{i|b_i=0, i <m\}} 4^i \\ B_1(n)&=\sum_{i\in \{i|b_i=1, i <m\}} 4^i \\ n &= \left(1 b_{m-1} \ldots b_{1} b_{0}\right)_{2} \end{aligned}$$

(2)

取$h(n)=n$，我们有

$$\begin{aligned} 1&=\alpha \\ 2n +j &=4n +\gamma_j n +\beta_j, j=0,1 \end{aligned}$$

那么

$$\begin{aligned} \alpha &= 1\\ \gamma_j &=-2\\ \beta_j&=j , j=0,1 \end{aligned}$$

是使得上式恒成立的参数，因此

$$\begin{aligned} h(n)&=n\\ &=A(n) \alpha+B_0(n) \beta_0+B_1(n) \beta_1+C_0(n) \gamma_0+C_1(n) \gamma_1\\ &= A(n)+B_1(n)-2C_0(n) -2C_1(n) \end{aligned}$$

由此可得

$$C_0(n) +C_1(n)=(A(n)+B_1(n) - n )/2$$

(3)

取$h(n)=n^2$，我们有

$$\begin{aligned} 1&=\alpha \\ (2n+j)^2&=4n^2 +\gamma_j n +\beta_j, j=0,1\\ 4n^2 + 4jn +j^2&=4n^2 +\gamma_j n +\beta_j, j=0,1 \end{aligned}$$

那么

$$\begin{aligned} \alpha &= 1\\ \gamma_j &=4j\\ \beta_j&=j^2 , j=0,1 \end{aligned}$$

是使得上式恒成立的参数，因此

$$\begin{aligned} h(n)&=n^2\\ &=A(n) \alpha+B_0(n) \beta_0+B_1(n) \beta_1+C_0(n) \gamma_0+C_1(n) \gamma_1\\ &= A(n)+B_1(n) +4C_1(n) \end{aligned}$$

由此可得

$$C_1(n)=(n^2 - A(n)- B_1(n)) / 4$$

结合

$$C_0(n) +C_1(n)=(A(n)+B_1(n) - n )/2$$

可得

$$\begin{aligned} C_0(n) &=(A(n)+B_1(n) - n )/2 -(n^2 - A(n)- B_1(n)) / 4\\ &= -\frac {n} 2 -\frac{n^2} 4 +\frac {3A(n)}{4}+\frac {3B_1(n)}{4} \end{aligned}$$

因此

$$\begin{aligned} A(n)&=4^m \\ B_0(n)&=\sum_{i\in \{i|b_i=0, i <m\}} 4^i \\ B_1(n)&=\sum_{i\in \{i|b_i=1, i <m\}} 4^i \\ C_0(n)&=-\frac {n} 2 -\frac{n^2} 4 +\frac {3A(n)}{4}+\frac {3B_1(n)}{4}\\ C_1(n)&=n^2 - A(n)- B_1(n)\\ n &= \left(1 b_{m-1} \ldots b_{1} b_{0}\right)_{2} \end{aligned}$$

21

起点的选择是随意的，因为增加一定的偏移量即可。

这里不妨设以$n+1$为起点，那么选择$n+1,\ldots, 2n$的最大公约数$d$即可，这是因为

$$d \equiv 0 \mod {2n}$$

所以第一轮删去$n+1$，此时起点变成$n+2$。

对于第二轮，因为

$$d \equiv 0 \mod {2n-1}$$

所以第二轮删去$n+2$。

利用归纳法可得第$i$轮删去$n+i$，所以结论成立。

重点

4, 6, 10, 11, 12, 18, 19, 21