Question

Los nenúfares $1, 2, 3, \ldots$ están en fila en un estanque. Una rana realiza una secuencia de saltos comenzando en el nenúfar $1.$ Desde cualquier nenúfar $k$ la rana salta al nenúfar $k + 1$ o al nenúfar $k + 2$ elegido al azar con probabilidad $\frac{1}{2}$ e independientemente de los demás saltos. La probabilidad de que la rana visite el nenúfar $7$ es $\frac{p}{q},$ donde $p$ y $q$ son enteros positivos primos entre sí. Halle $p + q.$

Lily pads $1, 2, 3, \ldots$ lie in a row on a pond. A frog makes a sequence of jumps starting on pad $1.$ From any pad $k$ the frog jumps to either pad $k + 1$ or pad $k + 2$ chosen randomly with probability $\frac{1}{2}$ and independently of other jumps. The probability that the frog visits pad $7$ is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

Respuesta

Solución:

Sea $p_k$ la probabilidad de que la rana visite el nenúfar $k.$ La rana cae en el nenúfar $k$ exactamente de una de dos maneras disjuntas: visita el nenúfar $k - 1$ y salta $+1$ desde allí (si salta $+2,$ el nenúfar $k$ queda saltado para siempre), o se salta por completo el nenúfar $k - 1$ , lo que requiere visitar el nenúfar $k - 2$ y saltar $+2$ desde él, cayendo en el nenúfar $k.$ Por lo tanto $\begin{aligned} &p_k = \tfrac{1}{2}p_{k-1} + \tfrac{1}{2}p_{k-2}, \\ &\qquad p_1 = 1, \quad p_2 = \tfrac{1}{2}. \end{aligned}$

Iterando: $p_3 = \frac{3}{4},$ $p_4 = \frac{5}{8},$ $p_5 = \frac{11}{16},$ $p_6 = \frac{21}{32},$ y $p_7 = \frac{43}{64}.$ Como $\gcd(43, 64) = 1,$ la respuesta es $43 + 64 = 107.$

Let $p_k$ be the probability that the frog visits pad $k.$ The frog lands on pad $k$ in exactly one of two disjoint ways: it visits pad $k - 1$ and jumps $+1$ from there (if it jumps $+2,$ pad $k$ is skipped forever), or it skips pad $k - 1$ entirely, which requires visiting pad $k - 2$ and jumping $+2$ from it, landing on pad $k.$ Hence $\begin{aligned} &p_k = \tfrac{1}{2}p_{k-1} + \tfrac{1}{2}p_{k-2}, \\ &\qquad p_1 = 1, \quad p_2 = \tfrac{1}{2}. \end{aligned}$

Iterating: $p_3 = \frac{3}{4},$ $p_4 = \frac{5}{8},$ $p_5 = \frac{11}{16},$ $p_6 = \frac{21}{32},$ and $p_7 = \frac{43}{64}.$ Since $\gcd(43, 64) = 1,$ the answer is $43 + 64 = 107.$

2019 AIME II Problema 2

Solución:

El Problema 2 en otros años