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

github仓库：

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

## 第1章 递归问题

### 热身题

#### 2

$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$从$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}$

#### 3

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

$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$在$B,C$的情形同理可得。

#### 4

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

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

### 作业题

#### 8

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

#### 10

$A\to B$：

$0$ $[1,\ldots, n]$
$1$ $[n]$ $[1,\ldots, n-1]$
$2$ $[n]$ $[1,\ldots, n-1]$
$3$ $[1,\ldots, n]$

$B\to A$：

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

• 第一步：$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}$

#### 11

##### (b)

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

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

• $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}$

#### 12

$n=1$，此时

#### 14

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

$n=0$时，

(1)

(2)

(3)

### 考试题

#### 17

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

#### 18

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

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

所以条直线的交点为

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

• $i_1= i_2 = 1$：

• $i_1= 1, i_2= 2$：

• $i_1= i_2 = 2$：

• $i_1= 2, i_2= 1$：

• 注意到

所以

即交点的纵坐标属于区间

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

现在考虑直线$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}$属于不相交的区间，所以

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

#### 19

$\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$个交点：

(2)

(3)

### 重点

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