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\)
\(B. 4\) \(C. 6\) \(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\) \(B. 2\) \(C. 3\) \(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\)
\(B. 4\) \(C. 6\) \(D. 8\)

Solution

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

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

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_{2 j+1}, v_{2 j+3}, \cdots, v_{2 d-2 j+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 2 d+1 . \]

这里我们约定 \(v_0=v_{2 d+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

Problem 5

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

Solution

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\) 次的概率是：

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

要求 \(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}\) ，可得：

\[ \begin{equation} \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} \label{6.1.2} \end{equation} \]

由 二项式定理⁴ 可知：

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

那么易得共轭表达式：

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

可得：

\[ \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} \label{6.2.1} \]

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

\[ \begin{align} \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} \nonumber \\ & = \frac {n!}{k_1!k_2! \cdots k_5!} p_1^{k_1} p_2^{k_2} \cdots p_5^{k_5} \tag{6.2.2} \label{6.2.2} \end{align} \]

观察上式可知，所求概率为多项式 \(\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} \label{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 $ 使得 \(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} \]

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 \left( t_0 \right) = 1\) ，它就会至多等待

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

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

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

\[ X \left(t_0 + \tau \right) = X \left(t_0 \right) + \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

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

不妨设最初条件为小红在小绿的前方，两者的距离为 \(d_0, \ d_0 \in (0, 1)\) ， \(d_0 \le 0\) 或 \(d_0 \ge 1\) 两者相遇无需讨论。

当小红来到树下，此时小绿距离树下还有一段距离，小红将在树下等待一段时间。假设在小红等待时间结束之前，小绿都没能赶到树下，那么在等待时间结束时，记为 \(t_{k}\) 时刻。在 \(t_{k}\) 时小绿距离树下还有 \(d_k\) 的距离，即 \(X(t_k) = 0, \ Y(t_k) = 1 - d_k\) 。

小红继续出发，在 \(d_k\) 时之后，即 \(t_k + d_k\) 时小绿将到达树下。此时小红已经出发了 \(d_k\) 的距离，即 \(X(t_k) = d_k, \ Y(t_k) = 1\) 。

小绿将在树下等待小红 \(\tau = K \left (X \left (d_{k} \right ) \right )\) 的时间，即：

\[ \begin{equation} \tau = K \left (X \left (d_{k} \right ) \right ) = f^{-1}(f(d_k) + \varepsilon) - d_k \tag{7.1.1} \label{7.1.1} \end{equation} \]

分析 \(\eqref{7.1.1}\) 可知：

1. 如果 \(f^{-1}(f(d_k) + \varepsilon) \ge 1\) ，则小红将在等待时间结束之前到达树下，小红和小绿相遇，结束分析。

2. 如果 \(f^{-1}(f(d_k) + \varepsilon) < 1\) ，那么在小绿等待时间结束之前，小红没能赶到树下。

在小绿等待时间结束那一刻，我们记为 \(t_{k+1}\) 时刻，此时 \(X(t_{k+1}) = f^{-1}(f(d_k) + \varepsilon), \ Y(t_{k+1}) = 0\) ，两者距离为：

\[ \begin{equation} d_{k+1} = 1 - f^{-1}(f(d_k) + \varepsilon) \tag{7.1.2} \label{7.1.2} \end{equation} \]

至此我们找到了小红与小绿之间的距离递推关系式。

设两者之间距离数列 ${ d_n } $ 表示一个人刚要从树下出发，另外一个距离树下的距离，那么问题转化为：对于任意初值 \(d_0 \in (0, 1)\) ，除了某个特定的初始距离值之外，都存在某个 \(k \in \mathrm{Z^+}\) ，使得数列 \(d_k \le 0\) 或者 \(d_k \ge 1\) 。

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

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

考虑函数 \(g(x)\) 表示两者之间距离，函数 \(h(x)\) 表示前后时刻（ \(t_{k}\) 和 \(t_{k+1}\) ）两者之间的距离变化，即 \(\Delta d = d_{k+1} - d_k = 1 - f^{-1}(f(d_k) + \varepsilon) - d_k\) 。

则有：

\[ \begin{equation} g(x) = 1 - f^{-1}(f(x) + \varepsilon) , \ x \in (0, 1) \tag{7.1.3} \label{7.1.3} \end{equation} \]

\[ \begin{equation} h(x) = g(x) - x = 1 - f^{-1}(f(x) + \varepsilon) - x \tag{7.1.4} \label{7.1.4} \end{equation} \]

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

\[ \begin{equation} g^{\prime}(x) = \frac{\mathrm{d} g(x)}{\mathrm{d} x} = - \frac{f^{\prime}(x)} {f^{\prime}\left(f^{-1}(f(x) + \varepsilon)\right)} \tag{7.1.5} \label{7.1.5} \end{equation} \]

\[ \begin{equation} h^{\prime}(x) = \frac{\mathrm{d} h(x)}{\mathrm{d} x} = -1 - \frac{f^{\prime}(x)} {f^{\prime}\left(f^{-1}(f(x) + \varepsilon)\right)} \tag{7.1.6} \label{7.1.6} \end{equation} \]

因为 \(f^{\prime}>0 , f^{\prime \prime} < 0\) ，所以 \((f^{-1})^{\prime}>0\) , \(\left(f^{-1}\right)^{\prime \prime}>0\) ，

又 \(h(0) = 1 - f^{-1}(\varepsilon) > 0\) ， \(h(1) = - f^{-1}(f(1) + \varepsilon) < 0\) ，所以 \(h(x)\) 在

针对第 \(1\) 种情况，需要证明：存在性和唯一性。

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

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

进一步化简可得：

\[ \begin{equation} f(1 - d^\ast) = f(d^\ast) + \varepsilon \end{equation} \]

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

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

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

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

\[ \begin{equation} g^{\prime}(x) = - f^{\prime}(1 - x) - f^{\prime}(x) < 0 , \ x \in (0,1) \end{equation} \]

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

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

下面来证明 \(d_0 \ne d^\ast\) 的情况，这里也可以分为 \(2\) 种情况讨论，\(0 < d_0 < d^\ast\) 和 \(d^\ast < d_0 < 1\) 。

\[ \phi_{n+1}=g\left(g\left(\phi_n\right)\right)=1-\left(g\left(\phi_n\right)+K\left(g\left(\phi_n\right)\right)\right)=\phi_n+K\left(\phi_n\right)-K\left(g\left(\phi_n\right)\right)<\phi_n \] , also \(g\left(\phi_{n+1}\right)>g\left(\phi_n\right)\). Then

\[ \phi_{n+1}-\phi_{n+2}=K\left(g\left(\phi_{n+1}\right)\right)-K\left(\phi_{n+1}\right)>K\left(g\left(\phi_n\right)\right)-K\left(\phi_n\right)=\phi_n-\phi_{n+1} \]

, showing that

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

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

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

参考文献