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\) 的塔。已知：
- 同学们的位置和塔的位置均视为同一平面上的点，且这些点彼此不重合；
- 塔中任意 \(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\) 座塔 \(A\) ，那么很显然有无数多同学可以看到塔 \(A\) ，也可以有无数多同学看不到塔 \(A\) ；
假设有 \(2\) 座塔 \(A, B\) ，那么只有以 \(A\) 为起点的射线 \(AB\) 且位于 \(B\) 之后的同学无法看到塔 \(A\) ；
假设有 \(3\) 座塔 \(A, B, C\) ，同理可知存在无数位同学至少可以看见 \(2\) 座塔；
假设有 \(4\) 座塔 \(A, B, C, D\) ，同理可知存在无数位同学至少可以看见 \(2\) 座塔；
假设有 \(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
[!TIP] 这道题考察的就是泊松过程，数学好的同学推出其表达式，然后计算可得。但我数学较弱，写程序模拟其过程，代码如下所示：
1 | public class WarPlaneGame { |
输出如下：1
2
3
4Shoot 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
52public 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
8Shoot 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\) .
- 证明题(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}\) -稠密的.
- 证明题 (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 \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\).
证明题 (10分) 证明: \(f\) 的全部特征值为 \(-d,-d+1, \cdots, d\).
问答题 (5分) 记 \(W\) 是从属于特征值 \(-d+2 k(0 \leq k \leq d)\) 的 \(f\) 的特征子空间的和. 求 \(W \cap U_0\) 的维数.
问答题 (5分) 对任一整数 \(j\left(1 \leq j \leq \frac{d}{2}\right)\) ，求 \(W \cap U_j\) 的维数.
Solution
目前不会做！
Problem 5
证明题 (20分) 对于 \(\mathbb{R}^3\) 中的任何中心对称的凸多面体 \(V\) ，证明可以找到一个椭球面 \(E\) ，把凸多面体包在内部，且 \(E\) 的表面积不超过 \(V\) 的表面积的 \(3\) 倍。
Solution
目前不会做！
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\) 服从参数为 \((n, p)\) 的二项分布 ，那么 \(n\) 次独立投掷中正面出现 \(k\) 次的概率是：
\[ \begin{equation} \label{6.1} \operatorname{Pr}(X_n = k) = \binom{n}{k} p^k (1−p)^{n−k} \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}\) ，可得：
\[ \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} \]
由 二项式定理 可知：
\[ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n−k} \]
那么易得共轭表达式：
\[ \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}[(\frac{1}{3} + \frac{2}{3})^n + (\frac{1}{3} - \frac{2}{3})^n] \\ & = \frac{1}{2}[1 + \frac{1}{3^n}] \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
[!TIP] 直觉告诉我们，五种福卡每种都是偶数的事件是相互独立的。通过第一问，我们已经知道答案是 \(\frac{1}{2}\) ，那么五种福卡每种福卡的张数都是偶数的概率就是 \(\frac{1}{2^5} = \frac{1}{32}\) ，而 \(2n\) 次扫福卡的概率就是 \(\frac{1}{16}\) 。下面我们就来证明下：
由多项式定理：
\[ \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}} \]
设 \(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} \]
对上式进行多项式展开，可得：
\[ \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
Solution
目前不会做！