2021 AIME I Problem 12

Attempt Problem 12 of the 2021 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2021 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

12.

Let A1A2A3A12A_1A_2A_3 \ldots A_{12} be a dodecagon (1212-gon). Three frogs initially sit at A4,A_4, A8,A_8, and A12.A_{12}. At the end of each minute, simultaneously, each of the three frogs jumps to one of the two vertices adjacent to its current position, chosen randomly and independently with both choices being equally likely. All three frogs stop jumping as soon as two frogs arrive at the same vertex at the same time. The expected number of minutes until the frogs stop jumping is mn,\frac{m}{n}, where mm and nn are relatively prime positive integers. Find m+n.m + n.

Answer: 19
Concepts:expected valuerandom walkrecursive probability
Difficulty rating: 3160
Solution:

Track the three gaps between consecutive frogs around the circle; they start at (4,4,4)(4, 4, 4) and always sum to 12.12. If the frogs jump by X1,X2,X3{±1},X_1, X_2, X_3 \in \{\pm 1\}, the gaps change by X2X1,X_2 - X_1, X3X2,X_3 - X_2, X1X3,X_1 - X_3, so each gap stays even and the process stops exactly when some gap becomes 0.0. Enumerating the 88 equally likely sign choices: from {4,4,4},\{4,4,4\}, the state stays with probability 28\frac{2}{8} and moves to {2,4,6}\{2,4,6\} with probability 68.\frac{6}{8}. From {2,4,6}:\{2,4,6\}: stay with probability 48,\frac{4}{8}, move to {4,4,4}\{4,4,4\} or {2,2,8}\{2,2,8\} with probability 18\frac{1}{8} each, and stop with probability 28.\frac{2}{8}. From {2,2,8}:\{2,2,8\}: stay with probability 28,\frac{2}{8}, move to {2,4,6}\{2,4,6\} with probability 28,\frac{2}{8}, and stop with probability 48.\frac{4}{8}.

Let E1,E2,E3E_1, E_2, E_3 be the expected remaining times from {4,4,4},\{4,4,4\}, {2,4,6},\{2,4,6\}, {2,2,8}.\{2,2,8\}. Then E1=1+14E1+34E2,E2=1+12E2+18E1+18E3,E3=1+14E3+14E2. \begin{aligned} E_1 &= 1 + \tfrac{1}{4}E_1 + \tfrac{3}{4}E_2, \\ E_2 &= 1 + \tfrac{1}{2}E_2 + \tfrac{1}{8}E_1 \\ &\quad {}+ \tfrac{1}{8}E_3, \\ E_3 &= 1 + \tfrac{1}{4}E_3 + \tfrac{1}{4}E_2. \end{aligned} The third gives E3=43+E23;E_3 = \frac{4}{3} + \frac{E_2}{3}; substituting into the second yields E2=4,E_2 = 4, then E3=83E_3 = \frac{8}{3} and E1=43+E2=163.E_1 = \frac{4}{3} + E_2 = \frac{16}{3}.

The expected number of minutes is 163,\frac{16}{3}, so m+n=16+3=19.m + n = 16 + 3 = 19.

← Problem 11#11
Full Exam

Problem 12 in Other Years