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

Respuesta: 373

Conceptos:punto reticular aritmética modular paridad invariante

Nivel de dificultad: 2990

Pista pequeña:

Cada salto cambia $x + y$ en $+9$ o $-15$ y cambia $x - y$ en $+5$ o $-5$

Each jump changes $x + y$ by $+9$ or $-15$ and changes $x - y$ by $+5$ or $-5$

Pista grande:

Los puntos con $x + y = 3j$ y $x - y = 5k$ requieren que $j$ y $k$ tengan la misma paridad, y todos ellos son alcanzables. Nota que $|x| + |y| = \max(|x + y|, |x - y|).$

Points with $x + y = 3j$ and $x - y = 5k$ need $j$ and $k$ of equal parity, and all of them are reachable. Note $|x| + |y| = \max(|x + y|, |x - y|).$

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. Repitiendo un salto que cambie $k$ en la dirección deseada, primero se alcanza algún punto de cada recta $x - y = 5k.$ Las combinaciones de dos saltos trasladan en $(9, 9)$ o $(-15, -15).$ Dos traslaciones de la primera clase y una de la segunda dan $(3, 3),$ mientras que tres de la primera y dos de la segunda dan $(-3, -3),$ de modo que sobre una recta fija cambian $j$ en $2$ o $-2.$ El valor de $j$ alcanzado inicialmente tiene la misma paridad que $k,$ por lo que estos desplazamientos 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. Repeating a jump that changes $k$ in the desired direction first reaches some point on every line $x - y = 5k.$ Two-jump combinations translate by $(9, 9)$ or $(-15, -15).$ Two of the former plus one of the latter give the shift $(3, 3),$ while three of the former plus two of the latter give $(-3, -3),$ so along a fixed line they move $j$ by $2$ or $-2.$ The initially reached value of $j$ has the same parity as $k,$ so these shifts 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

Respuesta: 373

Nivel de dificultad: 2990

Pista pequeña:

Pista grande:

Solución:

El Problema 11 en otros años