Question

Un insecto parte de un vértice de un triángulo equilátero. En cada movimiento, selecciona al azar uno de los dos vértices donde no se encuentra actualmente, y se arrastra a lo largo de un lado del triángulo hasta ese vértice. Dado que la probabilidad de que el insecto se mueva a su vértice inicial en su décimo movimiento es $\frac{m}{n},$ donde $m$ y $n$ son enteros positivos primos entre sí, halla $m + n.$

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$

Respuesta

Solución:

Sea $p_n$ la probabilidad de que el insecto esté en su vértice inicial después de $n$ movimientos, así que $p_0 = 1.$ El insecto está en casa después del movimiento $n + 1$ exactamente cuando estaba en otro lugar después del movimiento $n$ (probabilidad $1 - p_n$ ) y luego eligió el vértice inicial (probabilidad $\frac{1}{2}$ ): $p_{n+1} = \frac{1}{2}(1 - p_n).$

El punto fijo de esta recurrencia es $\frac{1}{3},$ y $p_{n+1} - \frac{1}{3} = -\frac{1}{2}\left(p_n - \frac{1}{3}\right),$ así que $p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n.$

Para $n = 10:$ $\begin{aligned} p_{10} &= \frac{1}{3}\left(1 + \frac{2}{1024}\right) \\ &= \frac{1}{3} \cdot \frac{1026}{1024} = \frac{171}{512}. \end{aligned}$ Como $171 = 9 \cdot 19$ y $512 = 2^9$ no comparten factor, $m + n = 171 + 512 = 683.$

Let $p_n$ be the probability that the bug is at its starting vertex after $n$ moves, so $p_0 = 1.$ The bug is home after move $n + 1$ exactly when it was elsewhere after move $n$ (probability $1 - p_n$ ) and then chose the starting vertex (probability $\frac{1}{2}$ ): $p_{n+1} = \frac{1}{2}(1 - p_n).$

The fixed point of this recurrence is $\frac{1}{3},$ and $p_{n+1} - \frac{1}{3} = -\frac{1}{2}\left(p_n - \frac{1}{3}\right),$ so $p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n.$

For $n = 10:$ $\begin{aligned} p_{10} &= \frac{1}{3}\left(1 + \frac{2}{1024}\right) \\ &= \frac{1}{3} \cdot \frac{1026}{1024} = \frac{171}{512}. \end{aligned}$ Since $171 = 9 \cdot 19$ and $512 = 2^9$ share no factor, $m + n = 171 + 512 = 683.$

2003 AIME II Problema 13

Solución:

El Problema 13 en otros años