Question

Sea $A_1A_2A_3 \ldots A_{12}$ un dodecágono ( $12$ -ágono). Tres ranas se sientan inicialmente en $A_4,$ $A_8,$ y $A_{12}.$ Al final de cada minuto, simultáneamente, cada una de las tres ranas salta a uno de los dos vértices adyacentes a su posición actual, elegido al azar e independientemente, siendo ambas opciones igualmente probables. Las tres ranas dejan de saltar en cuanto dos ranas llegan al mismo vértice al mismo tiempo. El número esperado de minutos hasta que las ranas dejan de saltar es $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí. Halle $m + n.$

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{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Respuesta

Solución:

Siga los tres huecos entre ranas consecutivas alrededor del círculo; empiezan en $(4, 4, 4)$ y siempre suman $12.$ Si las ranas saltan en $X_1, X_2, X_3 \in \{\pm 1\},$ los huecos cambian en $X_2 - X_1,$ $X_3 - X_2,$ $X_1 - X_3,$ así que cada hueco permanece par y el proceso se detiene exactamente cuando algún hueco llega a $0.$ Enumerando las $8$ elecciones de signo igualmente probables: desde $\{4,4,4\},$ el estado permanece con probabilidad $\frac{2}{8}$ y pasa a $\{2,4,6\}$ con probabilidad $\frac{6}{8}.$ Desde $\{2,4,6\}:$ permanece con probabilidad $\frac{4}{8},$ pasa a $\{4,4,4\}$ o $\{2,2,8\}$ con probabilidad $\frac{1}{8}$ cada uno, y se detiene con probabilidad $\frac{2}{8}.$ Desde $\{2,2,8\}:$ permanece con probabilidad $\frac{2}{8},$ pasa a $\{2,4,6\}$ con probabilidad $\frac{2}{8},$ y se detiene con probabilidad $\frac{4}{8}.$

Sean $E_1, E_2, E_3$ los tiempos restantes esperados desde $\{4,4,4\},$ $\{2,4,6\},$ $\{2,2,8\}.$ Entonces $\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}$ La tercera da $E_3 = \frac{4}{3} + \frac{E_2}{3};$ sustituyendo en la segunda se obtiene $E_2 = 4,$ luego $E_3 = \frac{8}{3}$ y $E_1 = \frac{4}{3} + E_2 = \frac{16}{3}.$

El número esperado de minutos es $\frac{16}{3},$ así que $m + n = 16 + 3 = 19.$

Track the three gaps between consecutive frogs around the circle; they start at $(4, 4, 4)$ and always sum to $12.$ If the frogs jump by $X_1, X_2, X_3 \in \{\pm 1\},$ the gaps change by $X_2 - X_1,$ $X_3 - X_2,$ $X_1 - X_3,$ so each gap stays even and the process stops exactly when some gap becomes $0.$ Enumerating the $8$ equally likely sign choices: from $\{4,4,4\},$ the state stays with probability $\frac{2}{8}$ and moves to $\{2,4,6\}$ with probability $\frac{6}{8}.$ From $\{2,4,6\}:$ stay with probability $\frac{4}{8},$ move to $\{4,4,4\}$ or $\{2,2,8\}$ with probability $\frac{1}{8}$ each, and stop with probability $\frac{2}{8}.$ From $\{2,2,8\}:$ stay with probability $\frac{2}{8},$ move to $\{2,4,6\}$ with probability $\frac{2}{8},$ and stop with probability $\frac{4}{8}.$

Let $E_1, E_2, E_3$ be the expected remaining times from $\{4,4,4\},$ $\{2,4,6\},$ $\{2,2,8\}.$ Then $\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 $E_3 = \frac{4}{3} + \frac{E_2}{3};$ substituting into the second yields $E_2 = 4,$ then $E_3 = \frac{8}{3}$ and $E_1 = \frac{4}{3} + E_2 = \frac{16}{3}.$

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

2021 AIME I Problema 12

Solución:

El Problema 12 en otros años