Question

Se coloca una rana en el origen de la recta numérica, y se mueve según la siguiente regla: en un movimiento dado, la rana avanza al punto más cercano con coordenada entera mayor que sea múltiplo de $3,$ o al punto más cercano con coordenada entera mayor que sea múltiplo de $13.$ Una secuencia de movimientos es una sucesión de coordenadas que corresponden a movimientos válidos, que empieza con $0,$ y termina con $39.$ Por ejemplo, $0, 3, 6, 13, 15, 26, 39$ es una secuencia de movimientos. ¿Cuántas secuencias de movimientos son posibles para la rana?

A frog is placed at the origin on the number line, and moves according to the following rule: in a given move, the frog advances to either the closest point with a greater integer coordinate that is a multiple of $3,$ or to the closest point with a greater integer coordinate that is a multiple of $13.$ A move sequence is a sequence of coordinates which correspond to valid moves, beginning with $0,$ and ending with $39.$ For example, $0, 3, 6, 13, 15, 26, 39$ is a move sequence. How many move sequences are possible for the frog?

Respuesta

Solución:

Divide el trayecto en los puntos de referencia $13$ y $26.$ Desde $0$ la rana sube por los múltiplos de $3$ y puede saltar a $13$ desde cualquiera de $0, 3, 6, 9, 12,$ lo que da $5$ rutas de $0$ a $13;$ de igual modo hay $5$ rutas de $13$ a $26$ (saltar a $26$ desde $13, 15, 18, 21, 24$ ) y $5$ de $26$ a $39.$ Para saltarse por completo $13$ la rana debe elegir la opción de múltiplo de $3$ cada vez que pasa por $12 \to 15,$ y luego saltar a $26$ desde uno de $15, 18, 21, 24:$ $4$ rutas de $0$ a $26$ evitando $13.$ De manera similar hay $4$ rutas de $13$ a $39$ evitando $26,$ y $4$ de $0$ a $39$ evitando ambos.

Combinando los segmentos: pasando por ambos puntos de referencia, $5 \cdot 5 \cdot 5 = 125;$ pasando solo por $13$ , $5 \cdot 4 = 20;$ pasando solo por $26$ , $4 \cdot 5 = 20;$ por ninguno, $4.$ El total es $125 + 20 + 20 + 4 = 169.$

Split the journey at the landmarks $13$ and $26.$ From $0$ the frog climbs the multiples of $3$ and may jump to $13$ from any of $0, 3, 6, 9, 12,$ giving $5$ routes from $0$ to $13;$ likewise there are $5$ routes from $13$ to $26$ (jump to $26$ from $13, 15, 18, 21, 24$ ) and $5$ from $26$ to $39.$ To skip $13$ entirely the frog must take the multiple-of- $3$ option every time through $12 \to 15,$ then jump to $26$ from one of $15, 18, 21, 24:$ $4$ routes from $0$ to $26$ avoiding $13.$ Similarly there are $4$ routes from $13$ to $39$ avoiding $26,$ and $4$ from $0$ to $39$ avoiding both.

Combining the segments: through both landmarks, $5 \cdot 5 \cdot 5 = 125;$ through $13$ only, $5 \cdot 4 = 20;$ through $26$ only, $4 \cdot 5 = 20;$ through neither, $4.$ The total is $125 + 20 + 20 + 4 = 169.$

2007 AIME I Problema 6

Solución:

El Problema 6 en otros años