2021 AIME I Problems/Problem 12

Problem

Let $A_1A_2A_3\ldots A_{12}$ be a dodecagon ( $12$ -gon). Three frogs initially sit at $A_4,A_8,$ and $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 $\frac mn$ , where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .

Solution 1

Define the distance between two frogs as the number of sides between them that do not contain the third frog.

Let $E(a,b,c)$ denote the expected number of minutes until the frogs stop jumping, such that the distances between the frogs are $a,b,$ and $c$ (in either clockwise or counterclockwise order). Without the loss of generality, assume that $a\leq b\leq c.$

We wish to find $E(4,4,4).$ Note that:

At any moment before the frogs stop jumping, the only possibilities for $(a,b,c)$ are $(4,4,4),(2,4,6),$ and $(2,2,8).$

$E(a,b,c)$ does not depend on the actual positions of the frogs, but depends on the distances between the frogs.

At the end of each minute, each frog has $2$ outcomes. So, there are $2^3=8$ outcomes in total.

We have the following system of equations: $\begin{align*} E(4,4,4)&=1+\frac{2}{8}E(4,4,4)+\frac{6}{8}E(2,4,6), \\ E(2,4,6)&=1+\frac{4}{8}E(2,4,6)+\frac{1}{8}E(4,4,4)+\frac{1}{8}E(2,2,8), \\ E(2,2,8)&=1+\frac{2}{8}E(2,2,8)+\frac{2}{8}E(2,4,6). \end{align*}$ Rearranging and simplifying each equation, we get $\begin{align*} E(4,4,4)&=\frac{4}{3}+E(2,4,6), &(1) \\ E(2,4,6)&=2+\frac{1}{4}E(4,4,4)+\frac{1}{4}E(2,2,8), &\hspace{12.75mm}(2) \\ E(2,2,8)&=\frac{4}{3}+\frac{1}{3}E(2,4,6). &(3) \end{align*}$ Substituting $(1)$ and $(3)$ into $(2),$ we obtain $E(2,4,6)=2+\frac{1}{4}\left[\frac{4}{3}+E(2,4,6)\right]+\frac{1}{4}\left[\frac{4}{3}+\frac{1}{3}E(2,4,6)\right],$ from which $E(2,4,6)=4.$ Substituting this into $(1)$ gives $E(4,4,4)=\frac{16}{3}.$

Therefore, the answer is $16+3=\boxed{019}.$

~Ross Gao ~MRENTHUSIASM

Solution 2 (Markov Chain)

We can solve the problem by removing $1$ frog, and calculate the expected time for the remaining $2$ frogs. In the original problem, when the movement stops, $2$ of the $3$ frogs meet. Because the $3$ frogs cannot meet at one vertex, the probability that those two specific frogs meet is $\frac13$ . If the expected time for the two frog problem is $E'$ , then the expected time for the original problem is $\frac{E'}{3}$ .

The distance between the two frogs can only be $0$ , $2$ , $4$ , $6$ . We use the distances as the states to draw the following Markov Chain. This Markov Chain is much simpler than that of Solution $1$ .

$\begin{align*} E(2) &= 1 + \frac12 \cdot E(2) + \frac14 \cdot E(4)\\ E(4) &= 1 + \frac14 \cdot E(2) + \frac12 \cdot E(4) + \frac14 \cdot E(6)\\ E(6) &= 1 + \frac12 \cdot E(4) + \frac12 \cdot E(6) \end{align*}$

By solving the above system of equations, $E(4) = 16$ . The answer for the original problem is $\frac{16}{3}$ , $16 + 3 = \boxed{\textbf{019}}$

~isabelchen

Remarks (Markov Chain)

Solution 1 Supplement

Summary

The two above Markov Chains are Absorbing Markov Chain. The state of $2$ frogs meeting is the absorbing state. This problem asks for the Expected Number of Steps before being absorbed in the absorbing state.

Let $p_{ij} = P(X_{n+1} = j | X_n = i)$ , the probability that state $i$ transits to state $j$ on the next step.

Let $e_i$ be the expected number of steps before being absorbed in the absorbing state when starting from transient state $i$ .

$e_i = \sum_{j} [p_{ij} \cdot ( 1 + e_{j})] = \sum_{j} (p_{ij} + p_{ij} \cdot e_{j}) = \sum_{j} p_{ij} + \sum_{j} (p_{ij} \cdot e_{j}) = 1 + \sum_{j} (p_{ij} \cdot e_{j})$

$e_i$ is $1$ plus the sum of the products of $p_{ij}$ and $s_j$ of all the next state $j$ , $\sum_{j} p_{ij} = 1$ .

2014 AMC12B Problem 22 is a similar problem with simpler states, both problem can be solved by Absorbing Markov Chain.

~isabelchen

2021 AIME I (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search