2024阿里巴巴全球数学竞赛预选赛试题及解答

By Long Luo

阿里巴巴达摩院 从 2018 年开始每年都会举办一届全球数学竞赛，之前一方面自己数学水平比较弱，另外一方面也没有报名，但一直很仰慕那些数学大神的风采。今年是第一次报名参加 2024阿里巴巴全球数学竞赛 ，上周末参加了预选赛，但遗憾的是，全部 \(7\) 道题中只有第 \(1, 2, 6\) 题会做，这里分享下我的解答：

Problem 1

几位同学假期组成一个小组去某市旅游. 该市有 \(6\) 座塔，它们的位置分别为 \(A, B, C, D, E, F\) 。同学们自由行动一段时间后，每位同学都发现，自己在所在的位置只能看到位于 \(A, B, C, D\) 处的四座塔，而看不到位于 \(E\) 和 \(F\) 的塔。已知：

1. 同学们的位置和塔的位置均视为同一平面上的点，且这些点彼此不重合；
2. 塔中任意 \(3\) 点不共线；
3. 看不到塔的唯一可能就是视线被其它的塔所阻挡，例如，如果某位同学所在的位置 \(P\) 和 \(A, B\) 共线，且 \(A\) 在线段 \(PB\) 上，那么该同学就看不到位于 \(B\) 处的塔。

（5 分） 请问 这个旅游小组最多可能有多少名同学？

\(A. \ 3 \qquad B. \ 4 \qquad C. \ 6 \qquad D. \ 12\)

Solution

这道题选 \(C\) ，最多只能有 \(6\) 名同学。

1. 假设有 \(1\) 座塔 \(A\) ，那么很显然有无数多同学可以看到塔 \(A\) ，也可以有无数多同学看不到塔 \(A\)​ ；

2. 假设有 \(2\) 座塔 \(A, B\) ，那么只有以 \(A\) 为起点的射线 \(AB\) 且位于 \(B\) 之后的同学无法看到塔 \(A\) ；

3. 假设有 \(3\) 座塔 \(A, B, C\) ，同理可知存在无数位同学至少可以看见 \(2\) 座塔；

4. 假设有 \(4\) 座塔 \(A, B, C, D\) ，同理可知存在无数位同学至少可以看见 \(2\) 座塔；

5. 假设有 \(6\) 座塔 \(A, B, C, D, E, F\) ，如果每位同学都无法看见 \(E, F\) 塔，如下图1 所示：

所以至多有 \(6\) 位同学位于 \(M, N, O, P, R, Q\) 处，无法看到塔 \(E, F\) 。

Problem 2

小明玩战机游戏。初始积分为 \(2\) 。在游戏进行中，积分会随着时间线性地连续减少 (速率为每单位时间段扣除 \(1\) )。游戏开始后，每隔一个随机时间段 (时长为互相独立的参数为 \(1\) 的指数分布)，就会有一架敌机出现在屏幕上。当敌机出现时，小明立即进行操作，可以瞬间击落对方，或者瞬间被对方击落。如被敌机击落，则游戏结束。如小明击落敌机，则会获得 \(1.5\) 个积分，并且可以选择在击落该次敌机后立即退出游戏，或者继续游戏。如选择继续游戏，则须等待到下一架敌机出现，中途不能主动退出。游戏的难度不断递增：出现的第 \(n\) 架敌机，小明击落对方的概率为 \((0.85)^n\) ，被击落的概率为 \(1 - (0.85)^n\) ，且与之前的事件独立。在任何时刻，如果积分降到 \(0\) ，则游戏自动结束。

第 1 问

小问 1 (5分) 如果游戏中，小明被击落后，其之前的积分保持。那么为了游戏结束时的累积积分的数学期望最大化，小明应该在其击落第几架敌机后主动结束游戏？

\(A. \ 1 \qquad B. \ 2 \qquad C. \ 3 \qquad D. \ 4\)

Solution

根据小概率事件原理，我们可以把打飞机事件视为泊松过程¹ ，那么事件分布就是泊松分布² 。其 Python 代码可以直接调用 API numpy.random.exponential 。虽然是 指数分布 ，但在 Java 中 需要使用 -Math.log(1 - random.nextDouble()) 而不是 Math.exp(double a) 。模拟代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public class WarPlaneGame {

    private static Random random = new Random();

    private static double getExpectScore(int planes) {
        double score = 2;

        for (int i = 0; i < planes; i++) {
            double waitTime = -Math.log(1 - random.nextDouble());

            if (waitTime >= score) {
                score = 0;
                break;
            }

            score -= waitTime;

            double possonPr = random.nextDouble();

            double shootDownPr = Math.pow(0.85, i + 1);

            if (possonPr < shootDownPr) {
                score += 1.5;
            } else {
                break;
            }
        }

        return score;
    }

    private static double simulate(int planes) {
        int simulateTimes = 50000;

        double scoreSum = 0.0;

        for (int i = 0; i < simulateTimes; i++) {
            scoreSum += getExpectScore(planes);
        }

        return scoreSum / simulateTimes;
    }

    public static void main(String[] args) {

        for (int i = 1; i < 5; i++) {
            double result = simulate(i);
            System.out.println("Shoot down " + i + " planes, Expect Score: " + result);
        }
    }
}

输出如下：

1
2
3
4

Shoot down 1 planes, Expect Score: 2.2344824425425442
Shoot down 2 planes, Expect Score: 2.290207012168609
Shoot down 3 planes, Expect Score: 2.2653361024420042
Shoot down 4 planes, Expect Score: 2.187342196221392

可以看出击落第 \(2\) 架敌机后主动结束游戏，期望积分最大，所以答案选 \(B\) 。

第 2 问

小问 2 (5分) 如果游戏中，小明被击落后，其之前积累的的积分会清零。那么为了游戏结束时的期望积分最大化，小明也会选择一个最优的时间主动结束游戏。请问在游戏结束时（小明主动结束游戏、或积分减到 \(0\) ），下列哪一个选项最接近游戏结束时小明的期望积分？

\(A. \ 2 \qquad B. \ 4 \qquad C. \ 6 \qquad D. \ 8\)

Solution

通过第一问，我们知道期望积分是随着次数逐渐递减的。

假设击落第 \(n - 1\) 架敌机后，小明所拥有的积分为 \(t\) 。如选择继续等待到下一架敌机出现后结束游戏，积分的数学期望为

\[ \begin{aligned} (0.85)^n \times \int_{0}^{t} (t + 1.5 - x)e^{-x} \mathrm{d}x \\ = (0.85)^n \times \left( t + 0.5 \times (1 - e^{-t}) \right) \end{aligned} \tag{2.1} \]

当 \(n = 1\) 且 \(t \le 2\) 时，上式总是大于 \(t\) 。因此小明至少要等到第一架敌机出现。假如小明击落了第一架敌机，那么手中积分至少为 \(1.5\) 。当 \(n = 2\) 且 $ t $ 时，(2.1) 总是小于 \(t\) 。因此，假设小明已经击落了第一架敌机，那么选择“立即结束游戏”总是优于“击落第二架敌机后立即结束”。由第一问可知，无论小明现有积分为多少，其最优结束时间都应该不晚于击落第二架敌机。综上可得，小明的最优策略为：等待第一架敌机出现，将其击落后立即结束游戏。

在此策略下，小明最终积分的期望应为(2.1)式在 \(n = 1\) 及 \(t = 2\) 时的值，约为 \(2.067\) 。最接近的选项为 \(A\) 。

继续写代码模拟其过程，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

public class WarPlaneGame {

    private static Random random = new Random();

    private static double getExpectScore2(int planes) {
        double score = 2;

        for (int i = 0; i < planes; i++) {
            double waitTime = -Math.log(1 - random.nextDouble());

            if (waitTime >= score / 2) {
                score /= 2;
                break;
            }

            score -= waitTime;

            double possonPr = random.nextDouble();

            double shootDownPr = Math.pow(0.85, i + 1);

            if (possonPr < shootDownPr) {
                score += 1.5;
            } else {
                score = 0;
                break;
            }
        }

        return score;
    }

    private static double simulate(int planes) {
        int simulateTimes = 50000;

        double scoreSum = 0.0;

        for (int i = 0; i < simulateTimes; i++) {
            scoreSum += getExpectScore2(planes);
        }

        return scoreSum / simulateTimes;
    }

    public static void main(String[] args) {

        for (int i = 1; i <= 8; i++) {
            double result = simulate(i);
            System.out.println("Shoot down " + i + " planes, Expect Score: " + result);
        }
    }
}

输出如下：

1
2
3
4
5
6
7
8

Shoot down 1 planes, Expect Score: 2.0230245088842116
Shoot down 2 planes, Expect Score: 1.7658505471404586
Shoot down 3 planes, Expect Score: 1.42047193787333
Shoot down 4 planes, Expect Score: 1.0837167796697962
Shoot down 5 planes, Expect Score: 0.8877915996251725
Shoot down 6 planes, Expect Score: 0.7556905685107955
Shoot down 7 planes, Expect Score: 0.7055539105268976
Shoot down 8 planes, Expect Score: 0.6896372679317954

可以看出最大期望积分是 \(2.023\) 左右，所以答案选 \(A\) 。

Problem 3

对于实数 \(T > 0\) ，称欧式平面 \(\mathbb{R}^2\) 的子集 \(\Gamma\) 为 \(T\) -稠密的，如果对任意 \(v \in \mathbb{R}^{2}\) ，存在 \(w \in \Gamma\) 满足 \(\|v-w\| \leqslant T\) . 设 \(2\) 阶整方阵 \(A \in \mathrm{M}_{2}(\mathbb{Z})\) 满足 \(\operatorname{det}(A) \neq 0\) .

1. 证明题(10分) 假设 \(\operatorname{tr}(A) = 0\) . 证明存在 \(C > 0\) ，使得对任意正整数 \(n\)​ ，集合

\[ A^{n} \mathbb{Z}^{2} := \left \{ A^{n} v: v \in \mathbb{Z}^{2} \right\} \]

是 \(C|\operatorname{det}(A)|^{n / 2}\) -稠密的.

2. 证明题 (10分) 假设 \(A\) 的特征多项式在有理数域上不可约. 证明与(1)相同的结论.

注: 这里 \(\mathbb{R}^{2}\) 和 \(\mathbb{Z}^{2}\) 中的向量约定为列向量, \(\mathbb{R}^{2}\) 中的内积为标准内积, 即 \(\langle v, w\rangle=v^{t} w\) . (提示: 在对(2)的证明中, 可使用如下 \(\text{Minkowski}\) 凸体定理的特殊情形： \(\mathbb{R}^{2}\) 中以原点为中心且面积为 \(4\) 的任意闭平行四边形中总包含 \(\mathbb{Z}^{2}\)​ 中的非零向量.)

Solution

记 \(t = \operatorname{tr}(A)\) , \(d = \det(A)\) . 则 \(A\) 的特征多项式 \(\chi_A(\lambda) = \lambda^2 - t\lambda + d\) . 由 Cayley-Hamilton定理, \(\chi_A(A) = 0\) , 即 \(A^2 = tA - dI_2\) . 下面分两步证明.

第一步. 先证明: 在(1)或(2)的条件下, 对任意正整数 \(n\) , 存在不全为零的整数 \(p_n, q_n\) 和区间 \([-1, 1]\) 中的实数\(x_n, y_n\) , 使得

\[ p_nA^{n+1} + q_nA^n = |d|^{n/2} \left( x_nA + y_nI_2 \right), \tag{2} \]

并且(2)式两边为可逆矩阵.

假设(1)的条件成立, 即 \(t = 0\) . 则 \(A^2 = -dI_2\) .

1. 若 \(n\) 为偶数, 则 \(A^n = (-d)^{n/2}I_2\) , 即(2)式对 \(p_n = 0, q_n = 1, x_n = 0, y_n = \operatorname{sgn} \left( (-d)^{n/2} \right)\) 成立. 此时(2)式两边可逆.

2. 若 \(n\) 为奇数, 则 \(A^n = (-d)^{(n - 1)/2}A\) , 即(2)式对 \(p_n = 0, q_n = 1,x_n = \operatorname{sgn} \left( (-d)^{(n - 1)/2} \right)|d|^{-1/2}\) , \(y_n = 0\) 成立. 此时(2)式两边也可逆.

假设(2)的条件成立, 即 \(\chi_A(\lambda)\) 在 \(\mathbb Q\) 上不可约. 由 \(A^2 = tA - dI_2\) 可知, 对任意 \(n \ge 0\) , 存在 \(a_n, b_n \in \mathbb R\) 使得 \(A^n = a_nA + b_nI_2\) , 并且由于 \(A\) 与 \(I_2\) 线性无关, \(a_n\) 与 \(b_n\) 被 \(n\) 唯一决定. 为了得到进一步的信息, 注意到

\[ a_{n+1}A + b_{n+1}I_2 = A^{n+1} = A(a_nA + b_nI_2) = a_n(tA - dI_2) + b_nA = (ta_n + b_n)A - da_nI_2. \]

这推出

\[ \begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix}t & 1 \\ -d & 0 \end{pmatrix} \begin{pmatrix}a_n \\ b_n \end{pmatrix}. \]

从而对 \(n\ge1\) 有

\[ \begin{pmatrix}a_{n+1} & a_n \\ b_{n+1} & b_n \end{pmatrix} = \begin{pmatrix}t & 1 \\ -d & 0\end{pmatrix} \begin{pmatrix}a_n & a_{n-1}\\b_n & b_{n-1}\end{pmatrix} = \cdots = \begin{pmatrix}t & 1 \\ -d & 0 \end{pmatrix}^n \begin{pmatrix}a_1 & a_0 \\ b_1 & b_0 \end{pmatrix} = \begin{pmatrix}t & 1 \\ -d & 0 \end{pmatrix}^n. \]

特别地，\(\det \begin{pmatrix}a_{n+1} & a_n \\ b_{n+1} & b_n \end{pmatrix} = d^n\) . 考虑以原点为中心的闭平行四边形

\[ \Delta_n := \left \{|d|^{n/2} \begin{pmatrix}a_{n+1} & a_n \\ b_{n+1} & b_n \end{pmatrix}^{-1} \begin{pmatrix} x \\ y \end{pmatrix}: x, y \in[-1,1] \right\}. \]

由于矩阵 \(|d|^{n/2} \begin{pmatrix} a_{n+1} & a_n \\ b_{n+1} & b_n \end{pmatrix}^{-1}\) 的行列式为 \(\pm1\) ，所以 \(\Delta_n\) 的面积为 \(4\) .

由 Minkowski 凸体定理，\(\Delta_n\) 中存在非零整点，即存在 \(x_n, y_n \in [-1, 1]\) 和不全为零的 \(p_n, q_n \in \mathbb Z\) 使得

\[ \begin{pmatrix}a_{n+1} & a_n \\ b_{n+1} & b_n \end{pmatrix} \begin{pmatrix}p_n \\ q_n \end{pmatrix} = |d|^{n/2} \begin{pmatrix} x_n \\ y_n \end{pmatrix}. \]

这推出

\[ \begin{aligned} p_nA^{n+1} + q_nA^n & = p_n(a_{n+1}A + b_{n+1}I_2) + q_n(a_nA + b_nI_2) \\ & = (p_na_{n+1} + q_na_n)A + (p_nb_{n+1} + q_nb_n)I_2 \\ & = |d|^{n/2}(x_nA + y_nI_2), \end{aligned} \]

即(2)式成立。另外，由于 \(\chi_A(\lambda)\) 在 \(\mathbb Q\) 上不可约，所以 \(A\) 在 \(\mathbb Q\) 中无特征值。这推出 \(p_nA + q_nI_2\) 可逆，从而(2)式两边的矩阵可逆。

第二步.

设 \(A = \begin{pmatrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}\) 。我们证明

\[ C: = \Big( \big( |a_{11}| + 1 \big)^2 + a_{12}^2 + a_{21}^2 + \big(|a_{22}| + 1 \big)^2\Big)^{1/2} \]

满足要求。首先，容易验证，对任意 \(x, y \in [-1,1]\) 和 \(u \in \mathbb R^2\) ，有 \(\|(xA + yI_2)u\|\le C\|u\|\) 。设 \(n \ge 1\)， \(v \in \mathbb R^2\)。记

\[ v' = |d|^{-n/2}(x_nA + y_nI_2)^{-1}v. \]

取 \(w' \in \mathbb Z^2\) 使得 \(\|v'-w'\| \le 1\) ，并取

\[ w = |d|^{n/2}(x_nA + y_nI_2)w' = A^n(p_nA + q_nI_2)w' \in A^n \mathbb Z^2. \]

则

\[ \|v-w\| = |d|^{n/2} \big\|(x_nA + y_nI_2)(v'-w')\big\| \le C|d|^{n/2}. \]

这就完成了证明。

Problem 4

设 \(d \geq 0\) 是整数， \(V\) 是 \(2 d + 1\) 维复线性空间，有一组基

\[ \left \{ v_1, v_2, \cdots, v_{2 d + 1} \right \} \text {. } \]

对任一整数 \(j \left( 0 \leq j \leq \dfrac{d}{2} \right)\) ，记 \(U_j\) 是

\[ v_{2j+1}, v_{2j+3}, \cdots, v_{2d-2j+1} \]

生成的子空间. 定义线性变换 \(f: V \rightarrow V\) 为

\[ f \left( v_i \right) = \frac{(i - 1)(2d + 2 - i)}{2} v_{i-1} + \frac{1}{2} v_{i+1}, 1 \leq i \leq 2d+1 . \]

这里我们约定 \(v_0 = v_{2d+2} = 0\) .

1. 证明题 (10分) 证明: \(f\) 的全部特征值为 \(-d, -d+1, \cdots, d\).

2. 问答题 (5分) 记 \(W\) 是从属于特征值 \(-d+2 k(0 \leq k \leq d)\) 的 \(f\) 的特征子空间的和. 求 \(W \cap U_0\) 的维数.

3. 问答题 (5分) 对任一整数 \(j \left( 1 \leq j \leq \dfrac{d}{2} \right)\) ，求 \(W \cap U_j\)​​​​ 的维数.

Solution

在 \(M_2(\mathbb C)\) 中，令

\[ h_0 = \begin{pmatrix} 1 & \\ & -1 \end{pmatrix}, \quad x_0 = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \quad y_0 = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}. \]

计算得

\[ \begin{aligned} [h_0, x_0] & = h_0x_0 - x_0h_0 = 2x_0, \\ [h_0, y_0] & = h_0y_0 - y_0h_0 = -2y_0, \\ [x_0, y_0] & = x_0y_0 - y_0x_0 = h_0. \end{aligned} \]

记

\[ T = \exp \left( \frac{\pi}{4}(x_0 - y_0) \right) = \begin{pmatrix} \frac{\sqrt2}{2} & \frac{\sqrt2}{2} - \frac{\sqrt2}{2} & \frac{\sqrt2}{2} \end{pmatrix}. \]

计算得 \(T(x_0 + y_0)T^{-1} = h\) .

(1)定义线性变换 \(h, x, y:V \to V\) 如下：

\[ x(v_i) = v_{i+1}, \quad y(v_i) = (i - 1)(2d + 2 - i)v_{i-1}, \quad h(v_i) = 2(i - d - 1)v_i. \]

计算得

\[ [h, x] = 2x, \quad [h, y] = -2y, \quad [x, y] = h. \]

定义映射 \(\phi: \mathfrak{sl}(2, \mathbb C) \to \mathfrak{gl}(V)\) 为

\[ \phi(h_0) = h, \quad \phi(x_0) = x, \quad \phi(y_0) = y. \]

则 \(\phi\) 是一个代数同态. 类似于 \(T\) 的定义, 记 \(S = \exp \big( \frac{\pi}{4}(x - y)\big)\) , 则 \(S(x + y)S^{-1} = h\) . 所以, \(f = \frac12(x + y)\) 与 \(\frac12h\) 共轭. 这样, \(f\) 的特征值与 \(\frac12h\) 的相同, 也是 \(-d, -d+1, \dots, d\) .

(2)记 \(A = \exp(\pi if)\) , \(B = \exp(\frac{\pi}{2}h)\) . 则 \(W\) 是属于特征值 \((-1)^d\) 的 \(A\) 的特征子空间, \(U_0\) 是属于特征值 \((-1)^d\) 的 \(B\) 的特征子空间. 以上同态 \(\phi\)是某个李群同态 \(\Phi: \mathrm{SL}(2, \mathbb C)\to\mathrm{GL}(V)\) 的微分.

在 \(\mathrm{SL}(2, \mathbb C)\) 中, 我们有

\[ A_0: = \exp(\pi \mathrm i f_0) = \begin{pmatrix} 0 & \mathrm i \\ \mathrm i & 0 \end{pmatrix} \]

及

\[ B_0:= \exp \big( \frac{\pi}{2}\mathrm i h_0\big)=\begin{pmatrix}\mathrm i&0\\0&-\mathrm i\end{pmatrix}. \]

注意

\[ A_0^2=B_0^2=A_0B_0A_0^{-1}B_0^{-1}=-I \text{ 且 } A_0\sim B_0\sim A_0B_0. \]

由于 \(\Phi(-I) = 1\) , 所以 \(A\) 和 \(B\) 是 \(\mathrm{GL}(V)\) 中交换的对合子, 且 \(A \sim B \sim AB\) . 当 \(d\) 是偶数时, 我们有

\[ \dim W \cap U_0 = \frac12 \left( 3 \dim V^A - \dim V \right) = \frac{1}{2} (d+2). \]

当 \(d\) 是奇数时, 我们有

\[ \dim W \cap U_0 = \frac{1}{2} \left(\dim V - \dim V^A \right) = \frac12(d+1). \]

(3)我们有 \(U_{\lfloor\frac{d+2}{2}\rfloor} = 0\) . 因此, \(\dim W \cap U_{\lfloor \frac{d+2}{2} \rfloor} = 0\) . 有以上(2)中结论, \(\dim W \cap U_0 = \lfloor \frac{d+2}{2} \rfloor\) . 只需证明: 对任意的 \(j \;(0 \le j \le \frac{d}{2})\) , 我们有

\[ \dim W \cap U_j - \dim W \cap U_{j+1} \le 1. \]

这样,

\[ \dim W \cap U_j = \left \lfloor \frac{d + 2}{2} \right \rfloor - j. \]

由于 \(\mathrm{Ad}(A_0)x_0 = y_0\) 以及 \(\mathrm{Ad}(A_0)y_0 = x_0\) , 我们得到 \(\mathrm{Ad}(A)x = y\) 和 \(\mathrm{Ad}(A)y = x\) . 我们也有 \(\mathrm{Ad}(A_0)^{-1}h_0 = -h_0\) . 因此, \(\mathrm{Ad}(A)^{-1}h = -h\) . 记 \(u_0 = v_{d+1}\) , 它是 \(h\) 的 \(0\) -特征子空间的生成元. 由于 \(\mathrm{Ad}(A)^{-1}h = -h\) , 得 \(h(Au_0) = -A(hu_0) = 0\) . 因此, \(Au_0\) 也是 \(h\) 的 \(0\) -特征向量. 这样, \(Au_0 = tu_0, \; t \ne 0\) . 由于 \(A^2 = 1\) , 必有 \(t = \pm1\) . 对任意 \(j\le \frac{d}{2}\) , \(v_{2d+1-2j} = x^{d+1-2j}u_0\) , 而 \(v_{2j+1}\) 与 \(y^{d+1-2j}u_0\) 成比例. 这样, \(A\) 的作用交换 \(v_{2j+1}\) 和 \(c_jv_{2d+1-2j}\) , \(c_j\) 是某个非零常数. 因此, \(\dim W\cap U_j - \dim W \cap U_{j+1}\le1\) .

Problem 5

证明题 (20分) 对于 \(\mathbb{R}^3\) 中的任何中心对称的凸多面体 \(V\) ，证明可以找到一个椭球面 \(E\) ，把凸多面体包在内部，且 \(E\) 的表面积不超过 \(V\) 的表面积的 \(3\) 倍。

Solution

我们可以证明下述一般结论:

1. 设 \(V\) 是 \(\mathbb R^3\) 中的一个关于原点对称的非空有界凸开集。在所有关于原点对称且包含 \(V\) 的椭球面 \(E\) 中，存在唯一一个 \(E_0\) ，使得其包围的体积取到最小值。

我们知道, \(\mathbb R^3\) 中关于原点对称椭球与 \(3\) 元正定二次型一一对应。我们记三元(半)正定二次型全体为 \(Q_+\) ，对于 \(q \in Q_+\) ，它对应的(可能退化的)椭球为 \(\{ q(x, x) \le 1 \}\) .

注意到凸集 \(V\) 唯一对应到\(\mathbb R^3\)的一个范数 \(N\) (这样 \(V = \{x, \, N(x) < 1 \}\) ). 包含 \(V\) 的(可能退化的)椭球面 \(E\) 对应的三元二次型全体就是

\[ K = \bigl\{ q \in Q_+, \, 0 \le q(x, x) \le \big( N(x) \big)^2, \forall x \in \mathbb R^3 \bigr\}. \]

我们容易看到:

• \(K\) 不是空集;

• \(K\) 作为 \(\mathbb R^{3 \times 3}\) 赋予欧氏度量决定的拓扑)中的子集是一个有界闭集, 从而是紧的;

• \(K\) 是一个凸集(若 \(0 \le q_1(x, x), q_2(x, x) \le \left( N(x) \right)^2\) , 则对于任意 \(\lambda \in [0, 1]\) , \(0 \le \lambda q_1(x, x) + (1 - \lambda)q_2(x, x) \le \left( N(x) \right)^2\) ).

我们记 \(v(q) =\) 椭球 \(\{q(x, x) \le 1\}\) 的体积, 这是 \(K\) 上的一个连续函数(三个特征值乘积的倒数，注意这是无上界的)，由 \(K\) 的紧性可知存在 \(q_N\) , 使得 \(v(q_N)\) 取到最小值.

现在假设另有一个 \(q'\) 使得 \(v(q') = v(q_N)\) , 我们要说明 \(q' = q_N\) . 为此, 我们利用等式

\[ \iiint e^{-q(x, x)}d^3x = \frac{3}{2}v(q) \int_0^\infty t^{1/2e^{-t}}dt, \]

和指数函数的凸性，可得

\[ I(q) := \iiint e^{-\frac{q'(x, x) - q_N(x, x)}{2}}d^3x \le \frac{1}{2} \left( \iiint e^{-q'(x, x)}d^3x + \iiint e^{-q_N(x, x)}d^3x \right). \]

从而存在唯一一个(对应于 \(q_N\) 的) \(E_0\) , 使得体积取到最小值.

2. 我们还有 \(E_0 \subset \sqrt{3} \overline{V}\) .

椭球面 \(E_0\) 上, 我们取一点使得 \(N(x)\) 达到最大值的点 \(a\) . 容易看到

• 椭球面 \(E_0\) 在 \(a\) 点处的切平面 \(\Pi\) 与 \(E_0\) 只有一个公共点;

• 我们定义 \(H = \{y, \, q_N(a,y) = 0\}\) , 则 \(\Pi = a + H\) ;

• 对于 \(y \in H\) , \(t \in \mathbb R\) , 定义 \(\varphi(t) = N(a + ty)\) , 由范数的性质, 这是一个凸函数, 且满足 \(\varphi(t) \le N(a) \sqrt{1 + t^2q_N(y, y)}\) ;

• 由此, 我们得到 \(\varphi\) 的最小值在 \(t = 0\) 时取到. 如果我们对于任意 \(x \in \mathbb R^3\) , 定义(关于 \(q_N\) 的)向 \(H\) 的正交投影 \(\pi_H(x)\) , 以及 \(\pi_a(x) = x - \pi_H(x)\) , 那么就有 \(N(\pi_a(x)) \le N(x)\) ;

• 现在对于 \(\varepsilon, \delta \in (0, 1)\) 定义

\[ q(x, x) = (1 + \varepsilon)q_N(\pi_a(x), \pi_a(x)) + (1 - \delta)q_N(\pi_H(x), \pi_H(x)), \]

我们有\(q \in Q_+\) , 且 \(I(q) = (1 + \varepsilon)^{-1/2}(1 - \delta)^{-1}I(q_N)\) ;

• 对于任意 \(x \in \mathbb R^3\) , 有 \(q_N(\pi_a(x), \pi_a(x)) + q_N(\pi_H(x), \pi_H(x)) = q_N(x, x) \le N^2(x)\) , 故

\[ \begin{aligned} q(x, x) & = (1 - \delta) \left( q_N(\pi_a(x), \pi_a(x)) + q_N(\pi_H(x), \pi_H(x))\right) + (\delta + \varepsilon)q_N(\pi_a(x), \pi_a(x)) \\ & \le N^2(x) - \left[ \delta - \frac{\delta + \varepsilon}{N^2(a)} \right] N^2(x). \end{aligned} \]

• 如果 \(N^2(a) > 3\) , 那么可以取适当的 \(\varepsilon, \delta \in (0, 1)\) 使得 \(\left[ \delta - \frac{\delta + \varepsilon}{N^2(a)} \right] \ge 0\) 且 \((1 + \varepsilon)^{-1/2}(1 - \delta)^{-1} < 1\) , 这意味着 \(I(q) < I(q_N)\) , 矛盾.

因此 \(N^2(a) \le 3\) , 即 \(E_0 \subset \sqrt{3} \overline{V}\) .

上述 (1) + (2) 是二十世纪四十年代Fritz John证明的定理.

现在, 对于我们所考虑的凸多面体 \(V\) , 这个定理告诉我们, 对于相应的椭球面 \(E_0\) , 成立 \(\dfrac{1}{\sqrt3}E_0 \subset V\) . 这样, 由于凸体的表面积具有单调性(可以用关于凸体表面积的一般 Cauchy 积分公式, 也可以利用这里只涉及一个光滑的椭球面和一个多面体来直接证明), 我们就有

\[ \frac {1}{\sqrt3} E_0 \text{的表面积} \le V \text{的表面积}, \]

从而

\[ E_0 \text{的表面积} \le 3 \times V \text{的表面积}. \]

说明: 这里的 \(3\) 当然(远)不是最优的。

Problem 6

第 1 问

假设有一枚硬币，投掷得到正面的概率为 \(\dfrac{1}{3}\) 。独立地投掷该硬币 \(n\) 次，记 \(X_n\) 为其中得到正面的次数。试求 \(X_n\) 为偶数的概率在 \(n\) 趋于正无穷时的极限。

Solution

由题意可知，设随机变量 \(X_n\) 表示在 \(n\) 次独立投掷中正面出现的次数，每次出现正面的概率为 \(p = \dfrac{1}{3}\) ，则 \(X_n\) 服从参数为 \(\operatorname{B}(n, p)\) 的二项分布³ ，那么 \(n\) 次独立投掷中正面出现 \(k\) 次的概率是：

\[ \operatorname{Pr}(X_n = k) = \binom{n}{k} p^k (1−p)^{n−k} \tag{6.1.1} \]

要求 \(X_n\) 为偶数的概率，即：

\[ \begin{aligned} \operatorname{Pr}(X_n \text { is even}) & = \operatorname{Pr}(X_n = 0) + \operatorname{Pr}(X_n = 2) + \cdots + \operatorname{Pr}(X_n = 2k, k = \left \lfloor \frac{n}{2} \right \rfloor ) \\ & = \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \binom{n}{2k} p^{2k} (1 − p)^{n − 2k} \end{aligned} \]

代入 \(p = \dfrac{1}{3}\) ，可得：

\[ \operatorname{Pr}(X_n \text { is even}) = \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \binom{n}{2k} (\frac{1}{3})^{2k} (\frac{2}{3})^{n−2k} \tag{6.1.2} \]

由 二项式定理 ⁴ 可知：

\[ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n−k} \tag{6.1.3} \]

那么易得共轭表达式：

\[ \begin{aligned} (x + y)^n + (x − y)^n & = 2 \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} x^{2k}y^{n - 2k} \\ (x + y)^n - (x − y)^n & = 2 \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} x^{2k + 1}y^{n - 2k - 1} \end{aligned} \]

可得：

\[ \begin{aligned} \operatorname{Pr}(X_n \text { is even}) & = \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \binom{n}{2k} (\frac{1}{3})^{2k} (\frac{2}{3})^{n−2k} \\ & = \frac{1}{2} \left[ \left( \frac{1}{3} + \frac{2}{3} \right)^n + \left( \frac{1}{3} - \frac{2}{3} \right)^n \right] \\ & = \frac{1}{2} \left[ 1 + \frac{1}{3^n} \right] \end{aligned} \]

故答案为：

\[ \lim_{n \to \infty} \operatorname{Pr}(X_n \text { is even}) = \lim_{n \to \infty} \frac{1}{2} \left( 1 + \frac{1}{3^n} \right) = \frac{1}{2} \]

第 2 问

某人在过年期间参加了集五福活动，在这项活动中此人每扫描一次福字，可以随机地得到五张福卡中的一张。假设其每次扫福得到五福之一的概率固定，分别为 \(p_i \in (0, 1) , i = 1, 2, \cdots , 5\) 且 \(\sum_{i = 1}^{5} p_i = 1\) ，并假设其每次扫描得到的结果相互独立。在进行了 \(n\) 次扫福之后，记 \(X^{i}_n, i =1, 2, \cdots, 5\) 为其得到每种福卡的张数。那么求极限 \(\lim _{n \to \infty} \operatorname{P} \left( X^{(i)}_{2n}, i = 1, 2, \cdots, 5 \text{全部为偶数} \right)\) 。

Solution

由多项式定理⁵ ：

\[ \left( x_{1} + x_{2} + \cdots + x_{m} \right)^{n} = \sum _{\begin{array}{c} \alpha _{1} + \alpha _{2} + \cdots + \alpha _{m} = n \\ \alpha _{1},\alpha _{2},\cdots ,\alpha _{m} \geq 0 \end {array}}{ \frac {n!}{\alpha _{1}! \dots \alpha _{m}!}}x_{1}^{\alpha _{1}} \dots x_{m}^{\alpha _{m}} \tag{6.2.1} \]

设 \(k_i, i = 1,2, \cdots , 5\) 表示是 \(n\) 次独立扫描福卡中得到第 \(i\) 种福卡的张数，则其概率为：

\[ \begin{aligned} \operatorname{Pr} \left (X_{n}^{(i)} = k_i, i=1,2, \cdots ,5 \right) &= \binom {n}{k_1, k_2, \cdots, k_5} p_1^{k_1} p_2^{k_2} \cdots p_5^{k_5} \\ & = \frac {n!}{k_1!k_2! \cdots k_5!} p_1^{k_1} p_2^{k_2} \cdots p_5^{k_5} \end{aligned} \]

观察上式可知，所求概率为多项式 \(\left (p_1 + p_2 + p_3 + p_4 + p_5 \right )^{n}\) 的 \(p_1^{k_1} p_2^{k_2} \cdots p_5^{k_5}\)​ 项， \(\binom {n}{k_1, k_2, \cdots , k_5}\) 为其系数。

和问题 \(1\) 的共轭表达式类似，我们给不同福卡添加符号位，考虑如下求和表达式：

\[ S_{2n} = \frac{1}{2^{5}} \sum_{\beta_{i} = \pm 1} \left( \beta_{1} p_{1} + \beta_{2} p_{2} + \cdots + \beta_{5} p_{5} \right)^{2n} \tag{6.2.3} \]

对上式进行多项式展开，可得：

\[ \begin{aligned} S_{2n} & = \frac{1}{2^{5}} \sum_{\substack {\beta_{i} = \pm 1 \\ x_{1} + x_{2} + \cdots + x_{5} = 2n}} \frac{(2n)!}{x_{1}!x_{2}! \cdots x_{5}!} \beta{1}^{x_{1}} \beta_{2}^{x_{2}} \cdots \beta_{5}^{x_{5}} p_{1}^{x_{1}} p_{2}^{x_{2}} \cdots p_{5}^{x_{5}} \\ & = \frac{1}{2^{5}} \sum_{x_{1} + x_{2} + \cdots + x_{5} = 2n} \frac{(2n)!}{x_{1}!x_{2}! \cdots x_{5}!} p_{1}^{x_{1}} p_{2}^{x_{2}} \cdots p_{5}^{x_{5}} \sum_{\beta_{i} = \pm 1} \beta_{1}^{x_{1}} \beta_{2}^{x_{2}} \cdots \beta_{5}^{x_{5}} \end{aligned} \]

考虑 \(\sum _{\substack {\beta_{i} = \pm 1 \\ x_{1} + x_{2} + \cdots + x_{5} = 2n}} \beta_{1}^{x_{1}} \beta_{2}^{x_{2}} \cdots \beta_{5}^{x_{5}}\) ，如果存在 \(k \in [1, 5]\) 使得 \(x_{k}\) 为奇数的话，那么：

\[ \sum_{\beta_{i} = \pm 1} \beta_{1}^{x_{1}} \beta_{2}^{x_{2}} \cdots \beta_{5}^{x_{5}} = \sum_{\substack {\beta_{i} = \pm 1 \\ i \neq k}} \left[ \left( 1^{x_{k}} + (-1)^{x_{k}} \right) \prod_ {i \neq k} \beta_{i}^{x_{i}} \right]=0 \]

由于奇数项最终都会消去，只有偶数项 \(x_{i}\) 才会留下来，故有：

\[ \sum_{\beta_{i} = \pm 1} \beta_{1}^{x_{1}} \beta_{2}^{x_{2}} \cdots \beta_{k}^{x_{k}} = 2^{k} \]

那么求和表达式为：

\[ \begin{aligned} S_{2n} & = \sum_{\substack{x_{1} + x_{2} + \cdots + x_{k} = 2 n \\ x_{i} \text { is even }}} \frac{(2 n)!}{x_{1}!x_{2}! \cdots x_{k}!} p_{1}^{x_{1}} p_{2}^{x_{2}} \cdots p_{k}^{x_{k}} \\ & = \operatorname{Pr} \left \{ X_{2 n}^{(i)} \text { is all even } \right \} \end{aligned} \]

因此，所求问题转化为在 \(X_{2 n}^{(i)}\) 均为偶数情况下，当 $n $ 时，其极限为：

\[ \lim _{n \to \infty} \operatorname{Pr} \left \{ X_{2 n}^{(i)} \text { is all even } \right \} = \lim _{n \to \infty} S_{2 n} \]

因为 \(\left | \beta_{1} p_{1} + \beta_{2} p_{2} + \cdots + \beta_{5} p_{5} \right | \leq 1\) , 所以当 \(n \to \infty\) 时，只有 \(\beta_i\) 全为 \(1\) 或者 \(-1\) 情况下，

\[ \left| \sum_{i=1}^{5} \beta_{i} p_{i} \right| = 1 \]

因此，我们可以得到答案：

\[ \lim _{n \to \infty} \operatorname{Pr} \left \{ X_{2n}^{(i)} \text { is all even } \right \} = \frac{1}{2^{5}} \left[ (+1)^{2n} + (-1)^{2n} \right] = \frac{1}{16} \]

马尔可夫链 ( \(\textit{Markov Chain}\) )

1. 考虑按照第一次投掷的正反来进行分类：

   • 如果第一次投掷的结果为正面，则需要此后 \(n - 1\) 次出现正面的总次数为奇数；
   • 反之，则需要此后 \(n - 1\) 次出现正面的总次数为偶数。

记 \(p_n = P(X_n \text{为偶数})\) ，根据全概率公式我们有

\[ p_n = \frac{1}{3} \times (1 - p_{n-1}) + \frac{2}{3} \times p_{n-1} = \frac{1}{3} + \frac{p_{n-1}}{3} \]

因此

\[ \left( p_n - \frac{1}{2} \right) = \frac{1}{3} \times \left( p_{n-1} - \frac{1}{2} \right) \]

成为一个压缩映射，故 \(\lim_{n \to \infty} p_n = \frac{1}{2}\) 。

2. 在第一问的基础上，令 \(p_n(q)\) 为正面概率为 \(q\) 时 \(n\) 次投掷得到偶数个正面的概率。通过与上一问相同的计算易见对于一切 \(q \neq \frac{1}{2}\) ，\(\lim_{n \to \infty} p_n(q) = \frac{1}{2}\) 。当 \(q = \dfrac{1}{2}\) 时，我们同理有

\[ p_n \left( \frac{1}{2} \right) = \frac{1}{2} \times \left[ 1 - p_{n-1} \left( \frac{1}{2} \right) \right] + \frac{1}{2} \times p_{n-1} \left( \frac{1}{2}\right) \equiv \frac{1}{2} \]

因此我们即得到了“只有两种不同福卡”情形下的概率极限。下面考虑三种不同福卡，其概率分别为 \(p_1, p_2, p_3\)。注意到此时三种福卡各自的张数 \((X_1, X_2, X_3)\) 服从参数

为 \((2n, p_1, p_2, p_3)\) 的多项分布。1号福卡的张数 \(X_1\) 服从参数为 \((2n, p_1)\) 的二项分布。此外，给定 \(X_1 = n_1\) 的前提下，\(X_2\) 的条件分布服从参数为 \((2n-n_1, \dfrac{p_2}{p_2+p_3})\) 的二项分布。

记我们关心的事件为 \(A_{2n}^{(3)}\) ，再次利用全概率公式，我们有

\[ P(A_{2n}^{(3)}) = \sum_{k=0}^{n} P(X_1 = 2k) p_{2n-2k} \left( \frac{p_2}{p_2+p_3} \right) \tag{6.2.5} \]

注意到我们已经证明了 \(\lim_{m \to \infty} p_m \left( \frac{p_2}{p_2+p_3} \right) = \frac{1}{2}\) 。对于一切 \(\epsilon > 0\) 存在整数 \(M_1\) 使得

\[ p_m \left( \frac{p_2}{p_2 + p_3} \right) \in (1/2 - \epsilon, 1/2 + \epsilon), \quad \forall m \geq 2M_1 \]

同时，存在 \(N_1\) 使得

\[ p_m(p_1) \in (1/2 - \epsilon, 1/2 + \epsilon), \quad \forall m \geq 2N_1 \]

最后对于已确定的 \(M_1\) ，注意到 \(X_1\) 服从参数为 \((2n, p_1)\) 的二项分布。使用切比雪夫不等式可知对上述 \(\epsilon > 0\) 存在 \(N_2\) 使得对任意 \(n \geq N_2\) ，有

\[ P(X_1 \geq 2n-2M_1) < \epsilon \]

令 \(N = \max\{N_1, N_2\}\) ，根据公式 (6.2.5)，对任意的 \(n \geq N\) 有：

\[ \begin{aligned} P(A_{2n}^{(3)}) &= \sum_{k=0}^{n} P(X_1 = 2k) p_{2n-2k} \left( \frac{p_2}{p_2+p_3} \right) \\ & \leq \sum_{k=0}^{n-M} P(X_1 = 2k) p_{2n-2k} \left( \frac{p_2}{p_2+p_3} \right) + P(X_1 \geq 2n-2M) \\ & \leq \left(\frac{1}{2}+\epsilon\right) \sum_{k=0}^{n-M} P(X_1 = 2k) + \epsilon \\ &\leq \left( \frac{1}{2} + \epsilon \right) p_{2n}(p_1) + \epsilon \leq \left(\frac{1}{2} + \epsilon \right)^2 + \epsilon \end{aligned} \]

与此同时，

\[ \begin{aligned} P(A_{2n}^{(3)}) & = \sum_{k=0}^{n} P(X_1 = 2k) p_{2n-2k} \left( \frac{p_2}{p_2+p_3} \right) \\ & \geq \sum_{k=0}^{n-M} P(X_1 = 2k) p_{2n-2k} \left( \frac{p_2}{p_2 + p_3} \right) \\ & \geq \left( \frac{1}{2} - \epsilon \right) \sum_{k=0}^{n-M} P(X_1 = 2k) \\ & \geq \left( \frac{1}{2} - \epsilon \right) \left[ p_{2n}(p_1) - P(X_1 \geq 2n-2M) \right] \\ & \geq \left( \frac{1}{2} - \epsilon \right) \left( \frac{1}{2} - 2\epsilon \right) \end{aligned} \]

由 \(\epsilon\) 的任意性，易见 \(P(A_{2n}^{(3)}) \to \dfrac{1}{4}\) 。因此，我们即可以递归地证明 \(P(A_{2n}^{(5)}) \to 2^{-4}\) ，证毕。

Problem 7

有这么一个音乐盒，它上面有一个圆形的轨道，轨道上的一点处还有一棵开花的树。当音乐盒处于开启模式时，音乐盒会发出音乐，轨道会按照顺时针匀速转动。

你可以在轨道上放置象征恋人的两颗棋子，我们不妨称它们为小红和小绿。当小红和小绿没有到达树下时，它们就会在轨道上各自移动。当某一颗棋子到达树下时，它就会在树下原地等待一段时间。此段时间内，如果另外一颗棋子也达到了树下，那么两颗棋子就会相遇，之后在它们将随即一起顺着轨道移动，不再分开；否则，等待时间结束，两颗棋子将各自顺着轨道继续移动。

考虑这个音乐盒的数学模型。我们把这个圆形轨道参数化成一个周长为 \(1\) 的圆环，我们认为棋子和树都可以用圆环上点表示。具体来说，我们用 \(X(t) \in [0, 1]\) 和 \(Y(t) \in [0, 1]\) 分别表示 \(t\) 时刻小红和小绿的在轨道上的位置坐标，而树的坐标是 \(\phi = 1\) ，或者，等价地， \(\phi = 0\) 。

当他们都没有抵达树下时 (见左图) ，他们的位置变化规律满足

\[ \frac{\mathrm{d}}{\mathrm{d} t} X(t) = 1, \quad \frac{\mathrm{d}}{\mathrm{d} t} Y(t) = 1 \]

假设在 \(t_0\) 时刻，小绿到达了树下（见中图），即 \(Y(t_0) = 1\) ，它就会至多等待

\[ \tau = K \left( X(t_0) \right) \]

的时间，换句话说，最长等待时间依赖于小红的当时的位置。

在等待期间，小绿不动，小红继续移动。如果等待期间的某时刻 \(t^\ast \in \left( t_0, t_0 + \tau \right]\) ，小红也达到了树下，即 \(X(t^\ast) = 1\) ，那么两棋子相遇。如果等待时间结束时（见右图），小红仍没有到达树下，那么它们俩继续移动，此时他们的位置分别是

\[ X \left( t_0 + \tau \right) = X(t_0) + \tau, \quad Y \left( t_0 + \tau \right) = 0 . \]

注意，虽然小绿的坐标被重置了，但是它在圆环上的位置并没有变。

如果在某时刻小红到达树下，它也会按照相同的规则等待，最长等待时间取决于此时小绿的位置。显然，小红小绿的命运取决于最长等待时间函数 \(K(\phi)\) 的形式。

1. 证明题 (10分) 我们设 \(f: \mathbb{R} \to \mathbb{R}\) 是一个光滑函数， 满足

\[ f^{\prime} > 0, \quad f^{\prime \prime} < 0, \quad f(0)=0, \quad f(1) = 1 . \]

并设 \(\varepsilon\) 是一个充分小的正的常数。我们定义等待时间函数

\[ K(\phi) = f^{-1}(f(\phi) + \epsilon) - \phi . \]

证明除了唯一的例外（特定的初始距离）之外，无论小红和小绿的初始距离如何，他们最终会相遇的。

2. 问答题 (10分) 我们考虑一个如下形式的 \(f\) 函数

\[ f(\phi) = \frac {1}{b} \ln \left( 1 + \left( e^b - 1 \right) \phi \right) \]

这里 \(b > 0\) 是一个常数。当 \(b \ll 1, \varepsilon \ll 1\) 时，请估算出相遇之前小红小绿走过的圈数的数量级。

Solution

循环分析

由题设条件，我们知道当小红和小绿都没有在树下时，都随着圆形轨道顺时针匀速转动，也因此小红和小绿只可能在树下相遇。

由于对称性，不妨设最初条件为小红在小绿的前方。我们关注当一颗棋子等待时间结束准备从树下出发的那个时刻，记为 \(t_{k}, k \in \mathbb{N}^+\) 时刻。设此时两者的距离为 \(d_0, \ d_0 \in (0, 1)\) ， \(d_0 \le 0\) 或 \(d_0 \ge 1\) 两者相遇无需讨论。

1. 在 \(t_{k}\) 时，此时小红坐标 \(X(t_k) = 0\) ，小绿坐标 \(Y(t_k) = d_0\) ，小红从树下准备出发，此时两者距离为：

\[ d_k = d_0 \tag{7.1.1} \]

2. 在经过 \(1 - d_0\) 时之后，也就是 \(t_{k} + 1 - d_0\) 时，小绿到达树下，此时小红坐标 \(X(t_k) = 1 - d_0\) ，小绿坐标 \(Y(t_k) = 0\) ，小绿在树下的等待时间为 \(\tau_0 = K(1 - d_{0})\) ；

   • 如果 \(1 - d_0 + K(1 - d_{0}) \ge 1\) 时，小红会赶到树下与小绿相遇；

   • 如果 \(1 - d_0 + K(1 - d_{0}) < 1\) 时，我们将讨论这种情况。

3. 当 \(1 - d_0 + K(1 - d_{0}) < 1\) 时，当小绿准备从树下出发，记为 \(t_{k+1}\) 时刻，此时小红坐标为 \(X(t_{k+1}) = 1 - d_0 + K(1 - d_{0})\) ，小绿坐标 \(Y(t_{k+1}) = 0\) ，此时两者距离为：

\[ \begin{aligned} d_{k+1} & = 1 - d_{k} + K(1 - d_{k}) \\ & = 1 - d_{k} + f^{-1} \left( f(1 - d_{k}) + \epsilon \right) - (1 - d_{k}) \\ & = f^{-1} \left( f(1 - d_k) + \epsilon \right) \end{aligned} \tag{7.1.2} \]

4. 当经过 \(1 - X(t_{k+1})\) 时之后，也就是 \(t_{k+1} + 1 - X(t_{k+1})\) 时小红到达树下，此时小红坐标为 \(X \left( t_{k+1} + 1 - X(t_{k+1}) \right) = 0\) ，小绿坐标 \(Y \left( t_{k+1} + 1 - X(t_{k+1}) \right) = 1 - X(t_{k+1})\) ；

5. 小红到达树下，将会等待 \(\tau_1 = K \left( 1 - X(t_{k+1}) \right)\) 时刻，此时分为 \(2\) 种情况：

   • 如果 \(1 - X(t_{k+1}) + K \left( 1 - X(t_{k+1}) \right) \ge 1\) ，小绿将赶到树下与小红相遇；

   • 如果 \(1 - X(t_{k+1}) + K \left( 1 - X(t_{k+1}) \right) < 1\) ，小绿无法赶到树下，回到初始情况。

6. 如果小红在等待 \(\tau_1\) 时间之后，小绿没有赶到树下，此时小红准备从树下出发，我们就回到了最初情况，完成了一次循环。我们记此时为 \(t_{k+2}\) 时刻，即 \(t_{k+2} = t_{k+1} + 1 - X(t_{k+1}) + K \left( 1 - X(t_{k+1}) \right)\) 时，此时小红坐标 \(X(t_{k+2}) = 0\) ，小绿坐标 \(Y(t_{k+2}) = 1 - X(t_{k+1}) + K \left( 1 - X(t_{k+1}) \right)\) ，两者距离为：

\[ \begin{aligned} d_{k+2} & = 1 - d_{k+1} + K(1 - d_{k+1}) \\ & = 1 - d_{k+1} + f^{-1}(f(1 - d_{k+1}) + \epsilon) - (1 - d_{k+1}) \\ & = f^{-1} \left( f(1 - d_{k+1}) + \epsilon \right) \end{aligned} \tag{7.1.3} \]

根据上述分析，可知假如小红和小绿一直没有相遇，在 \(t_k\) 时刻两者之间距离为 \(d_k\) ，在第 \(t_{k+1}\) 时两者之间距离为 \(d_{k+1}\) ，在 \(t_{k+2}\) 时两者距离距离为 \(d_{k+2}\) ，而在 \(t_{k+2}\) 时又回到了 \(t_k\) 情况，这样就完成了一轮循环。

设两者之间距离数列 \(\{ d_n \}\) ，那么问题转化为：对于任意初值 \(d_0 \in (0, 1)\) ，除了某个特定的初始距离值之外，都存在某个 \(k \in \mathbb{N}^+\) ，使得数列 \(d_k \le 0\) 或者 \(d_k \ge 1\) 。

这里我们需要证明 \(2\) 种情况：

1. 存在某个特定的初始距离，使得小红和小绿永远不相遇；
2. 除了某个特定的初始距离之外，小红和小绿总会相遇。

根据式 (7.1.3) 小红与小绿之间的距离递推关系式，定义函数 \(g\) :

\[ g(x) := f^{-1} \left( f(1 - x) + \epsilon \right), \ x \in (0, 1) \tag{7.1.4} \]

为了保证在 \(t_k\) 和 \(t_{k+1}\) 时刻之间没有相遇，需要满足 \(1 - x + K(1 - x) < 1\) ，即 \(f^{-1} \left( f(1 - x) + \epsilon \right) < 1\) ，根据 \(f' > 0\) ，所以反函数 \(f^{-1}\) 也是单调递增函数，故有 \(f(1 - x) + \epsilon < f(1) = 1\) ，则有： \(f(1 - x) < 1 - \epsilon\) 。

因为函数 \(f\) 单调递增，所以 \(1 - x < f^{-1}(1 - \epsilon)\) ，移项：\(x > 1 - f^{-1}(1 - \epsilon)\) ，设 \(\delta = 1 - f^{-1}(1 - \epsilon)\) ，所以函数 \(g\) 的定义域为：\(\delta < x < 1\) 。

对 \(g(x)\) 求导可得：

\[ g'(x) = -(f^{-1})'(f(1 - x) + \epsilon)f'(1 - x) = -\frac {f'(1 - x)}{f'(f^{-1}(f(1 - x) + \epsilon))} \tag{7.1.5} \]

因为 \(f^{-1}(f(1 - x) + \epsilon) > 1 - x\) ，\(f^{-1} > 0\) 所以 \(g'(x) < -1\) 。

定义函数 \(h(x)\) 表示 \(t_{k}\) 和 \(t_{k+1}\) 前后时刻两者之间的距离变化，即：

\[ h(x) = g(x) - x = f^{-1} \left( f(1 - x) + \epsilon \right) - x \tag{7.1.6} \]

对 \(h(x)\) 求导可得：

\[ h'(x) = g'(x) - 1 = -\frac {f'(1 - x)}{f'(f^{-1}(f(1 - x) + \epsilon))} - 1 < 0 \tag{7.1.7} \]

可见两者距离变化函数 \(h(x)\) 是单调递减的。

\[ h(0) = f^{-1} \left( f(1 - 0) + \epsilon \right) - 0 = f^{-1} (1 + \epsilon) > 0 \]

\[ h(1) = f^{-1} \left( f(1 - 1) + \epsilon \right) - 1 = f^{-1} (\epsilon) - 1 < 0 \]

因为 \(h(x)\) 在 \([0, 1]\) 区间连续单调递减，同时 \(h(0) > 0, \ h(1) < 0\) ，那么根据介值定理⁶ 必然存在某个值 \(x^\ast\) 使得 \(h(x^\ast) = 0\) 。严谨证明如下：

1. 存在性

设距离数列 \(\left \{ d_n \right \}\) 存在某个初值 \(d_0 = d^\ast\) 满足公式 (7.1.4) 使得 \(d_k = d^\ast , k = 0, 1, \cdots , n\) ，所以：

\[ d_{k+1} = d_k \Leftrightarrow d^\ast = f^{-1} \left( f(1 - d^\ast) + \epsilon \right) \]

进一步化简可得：

\[ f(1 - d^{\ast}) = f(d^{\ast}) + \epsilon \tag{7.1.8} \]

设 \(x_1 = d^{\ast}, \ x_2 = 1 - d^{\ast}\) ，那么 \(x_1, \ x_2\) 关于 \(\dfrac{1}{2}\) 对称，那么存在 \(x_1 = \dfrac{1}{2} - \epsilon^{\ast}, \ x_2 = \dfrac{1}{2} + \epsilon^{\ast}, \ \epsilon^{\ast} > 0\) 。

根据题设条件 \(f' > 0, \ f(0) = 0, \ f(1) = 1\) ， \(f\) 在 \([0, 1]\) 是单调递增的光滑函数，那么 \(f(x_2) > f(x_1) > 0\) ，故存在性得证。

2. 唯一性

下面来证明唯一性，由公式 (7.1.8) ，可得： \(f(1 - d^{\ast}) - f(d^{\ast}) = \epsilon\) 。

令函数 \(p(x) = f(1 - x) - f(x), \ x \in (0,1)\) ，对 \(p(x)\) 求导：

\[ p'(x) = - f'(1 - x) - f'(x) < 0, \ x \in (0, 1) \]

所以 \(p(x)\) 单调递减， \(p(0) = 1, \ p(\dfrac{1}{2}) = 0\) ，\(p(x)\) 连续，故有且仅存在一个 \(x \in (0, \dfrac{1}{2})\) ，使得 \(p(x) = \epsilon\) ，所以唯一性得证。

故存在某个特定的初始距离 \(d_0 = d^{\ast}\) ，使得小红和小绿永远不相遇。

3. 非特定初始距离

下面来证明 \(d_0 \ne d^{\ast}\) 的情况，这里也可以分为 \(2\) 种情况讨论，\(0 < d_0 < d^{\ast}\) 和 \(d^{\ast} < d_0 < 1\) ，根据刚才证明可知 \(h(d^\ast) = 0\) 。

• 当 \(0 < d_0 < d^{\ast}\) 时，可知 \(d_{k+1} < d_{k}\) ， \(h(k + 1) < h(k)\) 则有：

\[ d_k = d_0 - (d_0 - d_1) - (d_1 - d_2) - \cdots - (d_{k-1} - d_k) < d_0 - k(d_0 - d_1) \]

故所求上界 \(k = \left \lceil \dfrac{d_0}{d_0 - d_1} \right \rceil\) ，使得 \(d_k \leq 0\) ，小红和小绿终将相遇。

• 当 \(d^{\ast} < d_0 < 1\) 时，可知 \(d_{k+1} > d_{k}\) ，\(h(k + 1) > h(k)\) 则有：

\[ d_k = d_0 - (d_0 - d_1) - (d_1 - d_2) - \cdots - (d_{k-1} - d_k) > d_0 - k(d_0 - d_1) \]

故所求上界 \(k = \left \lceil \dfrac{d_0}{d_0 - d_1} \right \rceil\) ，使得 \(d_k \geq 1\) ，小红和小绿终将相遇。

迭代映射法

定义函数 \(H(x)\) 为：

\[ H(x) = g(g(x)) \tag{7.1.9} \]

可知表示 \(t_{k}, \ t_{k+1}, \ t_{k+2}\) 时刻两者之间的距离分别为： \(x, \ g(x), \ H(x)\) 。

对 \(H(x)\) 求导可得：

\[ H'(x) = g'(g(x))g'(x) > 1 \tag{7.1.10} \]

分析 \(H(x)\) 函数，如果两次观察后没有相遇，那么易知 \(H\) 的定义域为 \((\delta, g^{-1}(\delta))\)。显然当 \(\epsilon\) 充分小时，这个定义域非空。

下面我们研究 \(H\) 的不动点和稳定性。首先易知 \(g(x)\) 在 \((\delta, g^{-1}(\delta))\) 上有唯一的不动点，设为 \(x^*\) 。那么自然也有 \(H(x^*) = x^*\) 。再由 \(H' > 1\) ，我们容易得出当 \(x > x^*\) 时， \(H(x) > x\) ；当 \(\phi < \phi^*\) 时，\(H(x) < x\) 。

即 \(H\) 有唯一的不稳定平衡点。

所以除非两个棋子初始时的坐标差距是 \(x^*\) ，两个棋子一定会相遇。

第二问

因为 \(f(\phi) = \frac {1}{b} \ln \left( 1 + \left( e^b - 1 \right) \phi \right)\) ，所以

\[ f^{-1}(\phi)= \frac{e^{b\phi} - 1}{e^b - 1}. \]

我们可以直接计算得到

\[ H'(\phi) = -\frac{g'(f(1 - \phi) + \epsilon)}{g'(f(1 - \phi))} = -e^{b\epsilon}. \]

于是我们得到 \(H'(\phi) = e^{2b\epsilon}\) ，即 \(H\) 是线性函数。那么再由 \(H(\phi^*) = \phi^*\) 我们得到

\[ H(\phi) = e^{2b\epsilon}(\phi - \phi^*) + \phi^*. \]

如果我们记

\[ \phi_k = H^k(\phi_0), \quad \Delta_0 = |\phi_0 - \phi^*|, \quad \Delta_k = |\phi_k - \phi^*| \]

那么，可以直接算出

\[ \Delta_k = e^{2b\varepsilon k}\Delta_0. \]

注意到，第 \(2k\) 次观察时，每个棋子转过的圈数是 \(k\) ，且当 \(\Delta_k = O(1)\) 时，就会发生两个棋子相遇，于是推算出相遇时

\[ k = O \left( \frac{1}{b\varepsilon} \ln \frac{1}{\Delta_0} \right). \]

相遇时，棋子走过的圈数也是 \(O\left( \frac{1}{b\varepsilon} \ln \frac{1}{\Delta_0} \right)\) 。

参考文献