Question

La rueda que se muestra a continuación consta de dos círculos y cinco radios, con una etiqueta en cada punto donde un radio se encuentra con un círculo. Un insecto camina a lo largo de la rueda, empezando en el punto $A.$ En cada paso del proceso, el insecto camina de un punto etiquetado a un punto etiquetado adyacente. A lo largo del círculo interior el insecto solo camina en sentido antihorario, y a lo largo del círculo exterior el insecto solo camina en sentido horario. Por ejemplo, el insecto podría recorrer el camino $AJABCHCHIJA,$ que tiene $10$ pasos. Sea $n$ el número de caminos con $15$ pasos que empiezan y terminan en el punto $A.$ Halle el residuo cuando $n$ se divide entre $1000.$

The wheel shown below consists of two circles and five spokes, with a label at each point where a spoke meets a circle. A bug walks along the wheel, starting at point $A.$ At every step of the process, the bug walks from one labeled point to an adjacent labeled point. Along the inner circle the bug only walks in a counterclockwise direction, and along the outer circle the bug only walks in a clockwise direction. For example, the bug could travel along the path $AJABCHCHIJA,$ which has $10$ steps. Let $n$ be the number of paths with $15$ steps that begin and end at point $A.$ Find the remainder when $n$ is divided by $1000.$

Respuesta

Solución:

Desde cualquier punto interior el insecto tiene exactamente dos movimientos, en sentido antihorario a lo largo del círculo interior o hacia afuera por un radio; desde cualquier punto exterior tiene exactamente dos, en sentido horario a lo largo del círculo exterior o hacia adentro por un radio. Llame a un movimiento $X$ si es antihorario o hacia adentro y $Y$ si es horario o hacia afuera. Entonces cada cadena en $\{X, Y\}^{15}$ describe exactamente un camino de $15$ pasos desde $A.$

Un paso llega al círculo interior exactamente cuando es una $X,$ así que el camino termina en el círculo interior exactamente cuando su último movimiento es una $X;$ en ese caso los números de movimientos hacia adentro y hacia afuera son iguales. Midiendo la posición angular en quintos de vuelta (antihorario $+1,$ horario $-1,$ radios $0$ ), el camino regresa a $A$ exactamente cuando termina en el círculo interior y la rotación neta es un múltiplo de $5,$ es decir, cuando el último movimiento es $X$ y $\#X - \#Y \equiv 0 \pmod 5.$ Con $15$ movimientos esto significa que el número de $X$ es $5,$ $10,$ o $15.$

Fijando el último movimiento como $X,$ los primeros $14$ movimientos contienen $4,$ $9,$ o $14$ copias de $X,$ por lo que $\begin{aligned} n &= \binom{14}{4} + \binom{14}{9} + \binom{14}{14} \\ &= 1001 + 2002 + 1 = 3004, \end{aligned}$ y el residuo es $4.$

From any inner point the bug has exactly two moves, counterclockwise along the inner circle or outward along a spoke; from any outer point it has exactly two, clockwise along the outer circle or inward along a spoke. Call a move $X$ if it is counterclockwise or inward and $Y$ if it is clockwise or outward. Then every string in $\{X, Y\}^{15}$ describes exactly one $15$ -step path from $A.$

A step arrives on the inner circle exactly when it is an $X,$ so the path ends on the inner circle exactly when its last move is an $X;$ in that case the numbers of inward and outward moves are equal. Measuring angular position in fifths of a turn (counterclockwise $+1,$ clockwise $-1,$ spokes $0$ ), the path returns to $A$ exactly when it ends on the inner circle and the net rotation is a multiple of $5,$ that is, when the last move is $X$ and $\#X - \#Y \equiv 0 \pmod 5.$ With $15$ moves this means the number of $X$ s is $5,$ $10,$ or $15.$

Fixing the last move as $X,$ the first $14$ moves contain $4,$ $9,$ or $14$ $X$ s, so $\begin{aligned} n &= \binom{14}{4} + \binom{14}{9} + \binom{14}{14} \\ &= 1001 + 2002 + 1 = 3004, \end{aligned}$ and the remainder is $4.$

2018 AIME I Problema 10

Solución:

El Problema 10 en otros años