2021 AIME I Problem 12

Below is the professionally curated solution for Problem 12 of the 2021 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:expected valuerandom walkrecursive probability

Difficulty rating: 3160

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.

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.E_1 = 1 + \tfrac{1}{4}E_1 + \tfrac{3}{4}E_2, \qquad E_2 = 1 + \tfrac{1}{2}E_2 + \tfrac{1}{8}E_1 + \tfrac{1}{8}E_3, \qquad E_3 = 1 + \tfrac{1}{4}E_3 + \tfrac{1}{4}E_2. 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 11Full ExamProblem 13

Problem 12 in Other Years