注：本节内容为《具体数学》(原书第二版) 第一章 递归问题 考试题答案。

1.17

本问题同样出现与《算法竞赛进阶》，并且我们可以给出准确答案：

$$W_n=\underset{1\le k<n}{min}\{2W_k+T_{n-k}\}$$

可以发现题目给出的不等式是一个特例。

1.18

考察这 $n$ 组折线中的第 $j$ 组：

$$(n^{2j},0)\to (n^{2j}-n^j-n^{-n},1)$$

$$(n^{2j},0)\to (n^{2j}-n^j,1)$$

两条直线的斜率：

$$k_{j0}=\frac{1}{-n^j-n^{-n}}$$

$$k_{j1}=\frac{1}{-n^j}$$

可以证明：

$$k_{10}<k_{11}<k_{20}<k_{21}<\cdots <k_{n0}<k_{n1}$$

我们获得了一个斜率递增不等式。由此，我们可以证明在这个情况下，从左到右的每一条直线，都与前面的所有直线相交于不同点。

1.19

显然不能，会出现额外的平行情况。

1.20

成套方法的简单应用。略。

1.21

定义新运算：

$$a\otimes b=\{\begin{array}{ll}a(\mathrm{mod}b)& a(\mathrm{mod}b)\ne 0\\ b& a(\mathrm{mod}b)=0\end{array}$$

这样我们可以很轻松地表达编号。

定义：$D_i$ 为第 $i$ 个死人的编号。注意：每死一个人，我们让编号自动填补。即：

$$D_{i-2},D_{i-1},\boxed{{\displaystyle D_i}},\boxed{{\displaystyle D_{i+1},D_{i+2}}}$$

$$\Rightarrow D_{i-2},D_{i-1},\boxed{{\displaystyle D_i,D_{i+1}}}$$

我们有下面的等式：

$$D_1=q\otimes 2n$$

$$D_2=(D_1+q-1)\otimes (2n-1)$$

$$D_3=(D_2+q-1)\otimes (2n-2)$$

$$\cdots$$

$$D_i=(D_{i-1}+q-1)\otimes (2n-i+1)$$

$$\cdots$$

$$D_n=(D_{n-1}+q-1)\otimes (n+1)$$

由于只能死坏人，即

$$\mathrm{\forall }i\in {\mathbb{Z}}^{+}\Rightarrow D_i>n$$

取

$$q=\text{lcm}(n+1,n+2,\cdots ,2n)$$

或取

$$q=\prod _{k=n+1}^{2n}k$$

则有

$$D_1=2n>n$$

$$D_2=2n-1>n$$

$$\cdots$$

$$D_n=n+1>n$$

满足题设。