Question

设 $S$ 为 $20^9$ 的正整数因数的集合。从集合 $S$ 中独立随机选取三个数，并按选取顺序记为 $a_1$ 、 $a_2$ 、 $a_3$ 。同时满足 $a_1$ 整除 $a_2$ 且 $a_2$ 整除 $a_3$ 的概率为 $\frac{m}{n}$ ，其中 $m$ 与 $n$ 是互质正整数。求 $m$ 。

Let $S$ be the set of positive integer divisors of $20^9.$ Three numbers are chosen independently and at random from the set $S$ and labeled $a_1,$ $a_2,$ and $a_3$ in the order they are chosen. The probability that both $a_1$ divides $a_2$ and $a_2$ divides $a_3$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m.$

答案

答案：77

知识点：质因数分解基本概率隔板法

难度评级：2840

解答：

写 $20^9 = 2^{18} \cdot 5^9$ ，所以每个 $a_i = 2^{x_i} 5^{y_i}$ ，其中 $0 \le x_i \le 18$ 、 $0 \le y_i \le 9$ ；共有 $19 \cdot 10 = 190$ 个因数，并且两个质数的指数独立且均匀地被选择。链 $a_1 \mid a_2 \mid a_3$ 成立，恰好当 $x_1 \le x_2 \le x_3$ 且 $y_1 \le y_2 \le y_3$ 。

从 $k$ 个值中选出的非递减三元组对应大小为 $3$ 的可重组合，数量为 $\binom{k+2}{3}$ 。因此概率为 $\begin{aligned} \frac{\binom{21}{3}}{19^3} \cdot \frac{\binom{12}{3}}{10^3} &= \frac{1330}{6859} \cdot \frac{220}{1000} \\ &= \frac{70}{361} \cdot \frac{11}{50} \\ &= \frac{77}{1805}. \end{aligned}$

因为 $1805 = 5 \cdot 19^2$ 与 $77 = 7 \cdot 11$ ，没有公因数，所以分数已是最简形式， $m = 77$ 。

Write $20^9 = 2^{18} \cdot 5^9,$ so each $a_i = 2^{x_i} 5^{y_i}$ with $0 \le x_i \le 18$ and $0 \le y_i \le 9;$ there are $19 \cdot 10 = 190$ divisors, and the exponents of the two primes are chosen independently and uniformly. The chain $a_1 \mid a_2 \mid a_3$ holds exactly when $x_1 \le x_2 \le x_3$ and $y_1 \le y_2 \le y_3.$

Non-decreasing triples from a set of $k$ values correspond to multisets of size $3,$ counted by $\binom{k+2}{3}.$ So the probability is $\begin{aligned} \frac{\binom{21}{3}}{19^3} \cdot \frac{\binom{12}{3}}{10^3} &= \frac{1330}{6859} \cdot \frac{220}{1000} \\ &= \frac{70}{361} \cdot \frac{11}{50} \\ &= \frac{77}{1805}. \end{aligned}$

Since $1805 = 5 \cdot 19^2$ shares no factor with $77 = 7 \cdot 11,$ the fraction is in lowest terms and $m = 77.$

2020 AIME I 第 9 题

答案：77

难度评级：2840

解答：

其他年份的第 9 题