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

1.17

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

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

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

1.18

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

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

$$
(n^{2j}, 0) \rightarrow (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{cases}
a \pmod b & a \pmod b \neq 0 \\
b & a \pmod b = 0
\end{cases}
$$

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

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

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

$$
\Rightarrow D_{i-2}, D_{i-1}, \boxed{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)
$$

由于只能死坏人，即

$$
\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
$$

满足题设。