AIME 2021 I · 第 12 题

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:

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

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

3. 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{aligned} 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{aligned}$$ Rearranging and simplifying each equation, we get

$$\begin{aligned} 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{aligned}$$ 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)

Main article: Markov Chains

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 $\tfrac13$. If the expected time for the two frog problem is $E'$, then the expected time for the original problem is $\tfrac 13 E'$.

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 Supplement in the Remark section.

$$\begin{aligned} 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{aligned}$$ 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

Solution 3 (Pure algebraic manipulation, rigorous)

Let $(x,y,z)$ be the number of positions between every pair of adjacent frogs. Notice that each of these three numbers are always odd as the number of positions can only change by $+2$, $+0$ or $-2$ in every move. We also have that $x+y+z=9$ as the frog themselves occupy $3$ positions.

Let $a_n$ to be the probability that the frogs are at $(3,3,3)$ Situation at the $n$th move.

Let $b_n$ to be the probability that the frogs are at $(1,3,5)$ Situation at the $n$th move.

Let $c_n$ to be the probability that the frogs are at $(1,1,7)$ Situation at the $n$th move.

These are all the cases with $x,y,z$ all odd and sum to $9$.

After listing all the $8$ movements, we get the recurrence

$a_{n+1}=\frac{1}{4}a_n+\frac{1}{8}b_n$ $b_{n+1}=\frac{3}{4}a_n+\frac{1}{2}b_n+\frac{1}{4}c_n$ $c_{n+1}=\frac{1}{8}b_n+\frac{1}{4}c_n$

A $3,3,3$ Situation never leads to the end.

A $1,3,5$ Situation has $\frac{1}{4}$ chance of leading to the end.

A $1,1,7$ Situation has $\frac{1}{2}$ chance of leading to the end.

Then we calculate the probability of the process ending at the $n$th move.

$P($ending at move $1)$$=0$

$P($ending at move $2)$$=\frac{1}{4}b_1+\frac{1}{2}c_1=\frac{3}{16}$

$P($ending at move $3)$$=\frac{1}{4}b_2+\frac{1}{2}c_2=\frac{3}{16}$

$P($ending at move $4)$$=\frac{1}{4}b_3+\frac{1}{2}c_3$

$=\frac{1}{4}(\frac{3}{4}a_2+\frac{1}{2}b_2+\frac{1}{4}c_2)+\frac{1}{2}(\frac{1}{8}b_2+\frac{1}{4}c_2)$ (by plugging in the equations above)

$=\frac{3}{16}a_2+\frac{1}{8}b_2+\frac{1}{16}c_2+\frac{1}{16}b_2+\frac{1}{8}c_2$ $=\frac{3}{16}a_2+\frac{3}{16}b_2+\frac{3}{16}c_2$ $=\frac{3}{16}(a_2+b_2+c_2)$

$a_2+b_2+c_2$ is the probability of the frogs being at a non-ending situation at the $2$nd move. This is equivalent to the process not ending on or before the $2$nd move.

The probability here can be calculated reversely, it is equal to $1-$ (the probability of the process ending on or before the $2$nd move).

It is equal to $1-$ (the probability of the process ending at the $1$st move) $-$ (the probability of the process ending at the $2$nd move).

$P($ending at move $4)$$=\frac{3}{16}(1-\frac{3}{16})=\frac{39}{256}$

Then continue calculations like this.

$P($ending at move $5)$$=\frac{1}{4}b_4+\frac{1}{2}c_4$

$=\frac{3}{16}(a_3+b_3+c_3)$

$=\frac{3}{16}$$P($the process not ending on or before the $3$rd move$)$

$=\frac{3}{16}$$(1-P($the process ending on or before the $3$rd move$))$

$=\frac{3}{16}$$(1-P($the process ending on the $1$st move$)$$-P($the process ending on the $2$nd move$)$$-P($the process ending on the $3$rd move$))$

$=\frac{3}{16}(1-\frac{3}{16}-\frac{3}{16})$ $=\frac{15}{128}$

$P($ending at move $6)$$=\frac{1}{4}b_5+\frac{1}{2}c_5$

$=\frac{3}{16}(a_4+b_4+c_4)$

$=\frac{3}{16}$$P($the process not ending on or before the $4$th move$)$

$=\frac{3}{16}$$(1-P($the process ending on or before the $4$th move$))$

$=\frac{3}{16}(1-\frac{3}{16}-\frac{3}{16}-\frac{39}{256})$ $=\frac{363}{4096}$

.........

In general, $P($ending at move ${n+1})$$=\frac{1}{4}b_n+\frac{1}{2}c_n$

$=\frac{3}{16}(a_{n-1}+b_{n-1}+c_{n-1})$

$=\frac{3}{16}$$P($the process not ending on or before the $n-1$th move$)$

$=\frac{3}{16}$$(1-P($the process ending on or before the $n-1$th move$))$

$=\frac{3}{16}$$(1-\sum_{i=1}^{n-1}P($the process ending at the $i$th move$))$

Notice that $P($ending at move ${n+2})$ has just one more term to minus than $P($ending at move ${n+1})$. Subtracting the equation for $n+2$ and the equation for $n+1$, we derive

$P($ending at move ${n+1})-$$P($ending at move ${n+2})$$=\frac{3}{16}P($ending at move $n)$

Write $P($ending at move $n)$ as $Q_n$.

We have $Q_{n+1}-Q_{n+2}=\frac{3}{16}Q_n$.

We have $Q_{n+2}=Q_{n+1}-\frac{3}{16}Q_n$

We can actually prove the convergence of the expected value now in order to be rigorous. $Q_n$ is a probability, a non-negative real number. For all postive integers $n$ we have $Q_{n+2}\leq Q_{n+1}$, the sequence is non-increasing since $Q_3$.

$Q_{n+2}=Q_{n+1}-\frac{3}{16}Q_n\leq Q_n-\frac{3}{16}Q_n=\frac{13}{16}Q_n$ for $n\geq3$.

Thus each term of the sequence $Q$ is no more than the corresponding term of two alternating geometric sequences, one for its odd terms and one for its even terms. The infinite sum of $Q$ converges, and the expected value $Q_1+2Q_2+3Q_3+4Q_4+......$ converges as well.

Now we calculate $Q_1+Q_2+Q_3+Q_4+Q_5......$. We set this finite number equal to $S$.

$S=Q_2+Q_3+Q_4+Q_5+......$ (because $Q_1$ is $0$)

$S=\frac{3}{16}+Q_2-\frac{3}{16}Q_1+Q_3-\frac{3}{16}Q_2+Q_4-\frac{3}{16}Q_3+Q_5-\frac{3}{16}Q_4+......$ $S=\frac{3}{16}+S-\frac{3}{16}S$ $\frac{3}{16}-\frac{3}{16}S=0$ $S=1$

Knowing $S=1$, we can find the expected value $Q_1+2Q_2+3Q_3+4Q_4+5Q_5+......$.

Set this finite value equal to $E$.

$E=Q_1+2Q_2+3Q_3+4Q_4+5Q_5+......$ $E=\frac{3}{8}+3(Q_2-\frac{3}{16}Q_1)+4(Q_3-\frac{3}{16}Q_2)+5(Q_4-\frac{3}{16}Q_3)+6(Q_5-\frac{3}{16}Q_4)+......$ $E=\frac{3}{8}+3Q_2+4Q_3+5Q_4+6Q_5+......-\frac{3}{16}(3Q_1+4Q_2+5Q_3+6Q_4+......)$ $E=\frac{3}{8}+E+S-\frac{3}{16}(4Q_2+5Q_3+6Q_4+7Q_5......)$ $E=\frac{3}{8}+E+S-\frac{3}{16}(E+2S)$ $E=\frac{3}{8}+E+1-\frac{3}{16}(E+2)$ $3(E+2)=22$ $E=\frac{16}{3}$

The answer to the problem is $16+3=19$.

~AOPS Community - G2JFForever

Remark (Markov Chain)

Solution 1 Supplement

Solution 1 can be represented by the following Markov Chain:

• From state $(4, 4, 4)$ to state $(4, 4, 4)$: the $3$ frogs must jump in the same direction, $2 \cdot \frac18 = \frac14$.

• From state $(4, 4, 4)$ to state $(2, 4, 6)$: $2$ frogs must jump in the same direction, and the other must jump in the opposite direction, $\binom32 \cdot 2 \cdot \frac18 = \frac34$.

• From state $(2, 4, 6)$ to state $(4, 4, 4)$: the $2$ frogs with a distance of $4$ in between must jump in the same direction so that they will be further away from the other frog, and the other frog must jump in the opposite direction as those $2$ frogs, $\frac18$.

• From state $(2, 4, 6)$ to state $(2, 4, 6)$: the $3$ frogs can all jump in the same direction; or the $2$ frogs with a distance of $2$ in between jumps away from each other and the other frog jumps closer to the closest frog; or the $2$ frogs with a distance of $6$ in between jump closer to each other and away from the third frog, the third frog jumps closer to the closest frog; $(2 + 1 + 1) \cdot \frac18 = \frac12$.

• From state $(2, 4, 6)$ to state $(2, 2, 8)$: the $2$ frogs with a distance of $2$ in between must jump closer to the other frog and the other frog must jump close to those $2$ frogs, $\frac18$.

• From state $(2, 2, 8)$ to state $(2, 4, 6)$: $2$ frogs that have no frogs in between must both jump in the same direction away from the other frog, the other frog must also jump away from those $2$ frogs, $2 \cdot \frac18 = \frac14$.

• From state $(2, 2, 8)$ to state $(2, 2, 8)$: the $3$ frogs must all jump in the same direction, $2 \cdot \frac18 = \frac14$.

• From state $(2, 2, 8)$ to state $(0, x, y)$: frogs with a distance of $2$ must jump closer to each other, the other frog can jump in any direction, $\frac12 \cdot \frac12 \cdot 2 = \frac12$.

• From state $(2, 4, 6)$ to state $(0, x, y)$: the frogs with a distance of $2$ must jump closer to each other, the other frog can jump in any direction, $\frac12 \cdot \frac12 = \frac14$.

Because $a + b + c = 12$, we can use $(a, b)$ to represent the states which is simpler than using $(a, b, c)$ in Solution 1.

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 AMC 12B Problem 22 and 2017 AMC 12A Problem 22 are similar problem with simpler states, both problems can be solved by Absorbing Markov Chain.

~isabelchen

Video Solution

https://www.youtube.com/watch?v=nt4xwt5Ldtc

~Math Problem Solving Skills