Question

La rana Freddy salta por el plano coordenado buscando un río, que está en la recta horizontal $y = 24.$ Una cerca está ubicada en la recta horizontal $y = 0.$ En cada salto Freddy elige aleatoriamente una dirección paralela a uno de los ejes coordenados y se mueve una unidad en esa dirección. Cuando está en un punto donde $y = 0,$ con iguales probabilidades elige una de tres direcciones en las que salta paralelo a la cerca o salta alejándose de la cerca, pero nunca elige la dirección que lo haría cruzar la cerca hacia donde $y \lt 0.$ Freddy comienza su búsqueda en el punto $(0, 21)$ y se detendrá al llegar a un punto del río. Halla el número esperado de saltos que le tomará a Freddy llegar al río.

Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line $y = 24.$ A fence is located at the horizontal line $y = 0.$ On each jump Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where $y = 0,$ with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where $y \lt 0.$ Freddy starts his search at the point $(0, 21)$ and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river.

Respuesta

Solución:

Los saltos horizontales no cambian nada relevante, así que sea $T(y)$ el número esperado de saltos para llegar al río desde la altura $y.$ Entonces $T(24) = 0;$ para $1 \le y \le 23$ cada salto va hacia arriba, hacia abajo o de lado con probabilidades $\frac{1}{4}, \frac{1}{4}, \frac{1}{2},$ así que $\begin{aligned} T(y) &= 1 + \tfrac{1}{4}T(y + 1) \\ &\quad {}+ \tfrac{1}{4}T(y - 1) \\ &\quad {}+ \tfrac{1}{2}T(y), \end{aligned}$ lo cual se simplifica a $2T(y) = 4 + T(y - 1)$ $+ T(y + 1).$ En la cerca los tres movimientos igualmente probables dan $T(0) = 1 + \frac{2}{3}T(0) + \frac{1}{3}T(1),$ es decir $T(0) = 3 + T(1).$

Sumar $2T(y) = 4 + T(y - 1)$ $+ T(y + 1)$ sobre $y = 1, \ldots, 23$ telescopa a $T(1) + T(23) = 92 + T(0)$ $+ T(24).$ Sustituir $T(0) = 3 + T(1)$ y $T(24) = 0$ da $T(23) = 95.$

Ahora ejecuta la recurrencia hacia abajo como $T(y - 1) = 2T(y) - T(y + 1)$ $- 4:$ desde $T(24) = 0$ y $T(23) = 95,$ obtenemos $T(22) = 2 \cdot 95 - 0 - 4 = 186$ y $T(21) = 2 \cdot 186 - 95 - 4 = 273.$ Freddy comienza en la altura $21,$ así que la respuesta es $273.$

Horizontal jumps change nothing that matters, so let $T(y)$ be the expected number of jumps to reach the river from height $y.$ Then $T(24) = 0;$ for $1 \le y \le 23$ each jump goes up, down, or sideways with probabilities $\frac{1}{4}, \frac{1}{4}, \frac{1}{2},$ so $\begin{aligned} T(y) &= 1 + \tfrac{1}{4}T(y + 1) \\ &\quad {}+ \tfrac{1}{4}T(y - 1) \\ &\quad {}+ \tfrac{1}{2}T(y), \end{aligned}$ which simplifies to $2T(y) = 4 + T(y - 1)$ $+ T(y + 1).$ At the fence the three equally likely moves give $T(0) = 1 + \frac{2}{3}T(0) + \frac{1}{3}T(1),$ that is $T(0) = 3 + T(1).$

Summing $2T(y) = 4 + T(y - 1)$ $+ T(y + 1)$ over $y = 1, \ldots, 23$ telescopes to $T(1) + T(23) = 92 + T(0)$ $+ T(24).$ Substituting $T(0) = 3 + T(1)$ and $T(24) = 0$ yields $T(23) = 95.$

Now run the recurrence downward as $T(y - 1) = 2T(y) - T(y + 1)$ $- 4:$ from $T(24) = 0$ and $T(23) = 95,$ we get $T(22) = 2 \cdot 95 - 0 - 4 = 186$ and $T(21) = 2 \cdot 186 - 95 - 4 = 273.$ Freddy starts at height $21,$ so the answer is $273.$

2016 AIME I Problema 13

Solución:

El Problema 13 en otros años