Question

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.$

答案

Solution:

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 $\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}.$

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 Problem 9

Solution:

Problem 9 in Other Years