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

Solution

这道题选 \(C\) ,最多只能有 \(C_{4}^{2} = 6\) 名同学。

[!TIP] 这道题的解题思路是,从假设只有 \(1\) 座塔开始,一直到 \(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 所示:

图1. Solution of Problem 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

[!TIP] 这道题考察的就是泊松过程1 ,数学好的同学推出其表达式,然后计算可得。需要注意的是泊松分布2 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

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

继续写代码模拟其过程,如下所示:

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}\) -稠密的.

  1. 证明题 (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

[!TIP] 先挖坑,等我看懂了大神的解答再来填坑!

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 \frac{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)(2 d+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 \frac{d}{2}\right)\) ,求 \(W \cap U_j\)​​​​ 的维数.

Solution

[!TIP] 先挖坑,等我看懂了大神的解答再来填坑!

Problem 5

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

Solution

[!TIP] 先挖坑,等我看懂了大神的解答再来填坑!

Problem 6

第 1 问

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

Solution

[!TIP] 当 \(n \to \infty\) ,直觉告诉我们,偶数次正面出现的概率和奇数次正面出现的概率是一样的,而奇数偶数是均匀分布的,答案应该是 \(\frac{1}{2}\) 。但这道题不是选择题也不是填空题,我们需要严谨证明这个结论!

由题意可知,设随机变量 \(X_n\) 表示在 \(n\) 次独立投掷中正面出现的次数,每次出现正面的概率为 \(p = \frac{1}{3}\) ,则 \(X_n\) 服从参数为 \(\operatorname{B}(n, p)\) 的二项分布3 ,那么 \(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 = \frac{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} \]

由 二项式定理4 可知:

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

[!TIP] 这道题也可以用 马尔可夫链 来做,构建递推关系式,感兴趣的同学可以试试!

第 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

[!TIP] 直觉告诉我们,当 \(n \to \infty\) 时,五种福卡每种都是偶数的事件是相互独立的。通过第一问,我们已经知道答案是 \(\frac{1}{2}\) ,那么五种福卡每种福卡的张数都是偶数的概率就是 \(\frac{1}{2^5} = \frac{1}{32}\) ,而 \(2n\) 次扫福卡的概率就是 \(\frac{1}{16}\) 。这个猜测对不对呢?下面我们就来证明下。

由多项式定理5

\[ \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)\) 的形式。

图2. Problem 7
  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 . \]

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

  1. 问答题 (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

[!TIP] 这道题考试的时候没做出来,最近几天看了知乎上关于这次考试的讨论 如何评价2024阿里巴巴数学竞赛预选赛试题? ,看了大神们的解答,发现这道题不难,不要以为它是压轴题就觉得很难。这道题的关键在于找到小红和小绿的距离递推关系式,然后对这个关系式进行分析。下面的解法参考了知乎 Fiddie 的解答6喵喵 的解答7 ,我综合他们的解题思路自己推了一遍。

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

不妨设最初条件为小红在小绿的前方,两者的距离为 \(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\) 关于 \(\frac{1}{2}\) 对称,那么存在 \(x_1 = \frac{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(\frac{1}{2}) = 0\)\(g(x)\) 连续,故有且仅存在一个 \(x \in (0, \frac{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 \frac{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) \]

参考文献


  1. 泊松过程↩︎

  2. 泊松分布↩︎

  3. 二项分布↩︎

  4. 二项式定理↩︎

  5. 多项式定理↩︎

  6. Fiddie 的试题解答↩︎

  7. 喵喵 的试题解答↩︎