Question

Una rana comienza en $P_0 = (0, 0)$ y realiza una sucesión de saltos según la siguiente regla: desde $P_n = (x_n, y_n),$ la rana salta a $P_{n+1},$ que puede ser cualquiera de los puntos $(x_n + 7, y_n + 2),$ $(x_n + 2, y_n + 7),$ $(x_n - 5, y_n - 10),$ o $(x_n - 10, y_n - 5).$ Hay $M$ puntos $(x, y)$ con $|x| + |y| \le 100$ que pueden alcanzarse mediante una sucesión de tales saltos. Halla el residuo cuando $M$ se divide entre $1000.$

A frog begins at $P_0 = (0, 0)$ and makes a sequence of jumps according to the following rule: from $P_n = (x_n, y_n),$ the frog jumps to $P_{n+1},$ which may be any of the points $(x_n + 7, y_n + 2),$ $(x_n + 2, y_n + 7),$ $(x_n - 5, y_n - 10),$ or $(x_n - 10, y_n - 5).$ There are $M$ points $(x, y)$ with $|x| + |y| \le 100$ that can be reached by a sequence of such jumps. Find the remainder when $M$ is divided by $1000.$

Respuesta

Solución:

Cada salto cambia $x + y$ en $+9$ o $-15$ y cambia $x - y$ en $\pm 5.$ Partiendo de $(0, 0),$ todo punto alcanzable tiene por tanto $x + y = 3j$ y $x - y = 5k$ para enteros $j$ y $k;$ además $x = \frac{3j + 5k}{2}$ debe ser entero, así que $j$ y $k$ tienen la misma paridad. Como $|x| + |y| = \max(|x + y|,\, |x - y|),$ la condición $|x| + |y| \le 100$ se convierte en $|j| \le 33$ y $|k| \le 20.$

Recíprocamente, todo punto así es alcanzable: un solo salto se mueve entre rectas vecinas $x - y = 5k$ (cambiando $j$ en $3$ o $-5,$ lo que invierte su paridad), y las combinaciones de dos saltos trasladan en $(9, 9)$ o $(-15, -15),$ que se combinan, dos de las primeras más una de las segundas, en el desplazamiento $(3, 3),$ moviendo $j$ en $2$ a lo largo de una recta fija. Juntas, estas alcanzan todo par $(j, k)$ de igual paridad.

Conteo: los $j$ pares ( $33$ valores) se emparejan con los $k$ pares ( $21$ valores), y los $j$ impares ( $34$ valores) con los $k$ impares ( $20$ valores), así que $M = 33 \cdot 21 + 34 \cdot 20 = 1373.$ El residuo es $373.$

Each jump changes $x + y$ by $+9$ or $-15$ and changes $x - y$ by $\pm 5.$ Starting from $(0, 0),$ every reachable point therefore has $x + y = 3j$ and $x - y = 5k$ for integers $j$ and $k;$ moreover $x = \frac{3j + 5k}{2}$ must be an integer, so $j$ and $k$ have the same parity. Since $|x| + |y| = \max(|x + y|,\, |x - y|),$ the condition $|x| + |y| \le 100$ becomes $|j| \le 33$ and $|k| \le 20.$

Conversely, every such point is reachable: a single jump moves between neighboring lines $x - y = 5k$ (changing $j$ by $3$ or $-5,$ which flips its parity), and two-jump combinations translate by $(9, 9)$ or $(-15, -15),$ which combine — two of the former plus one of the latter — into the shift $(3, 3),$ moving $j$ by $2$ along a fixed line. Together these reach every pair $(j, k)$ of equal parity.

Counting: even $j$ ( $33$ values) pairs with even $k$ ( $21$ values), and odd $j$ ( $34$ values) with odd $k$ ( $20$ values), so $M = 33 \cdot 21 + 34 \cdot 20 = 1373.$ The remainder is $373.$

2012 AIME I Problema 11

Solución:

El Problema 11 en otros años