Question

Una sucesión $a_1, a_2, \ldots$ de enteros no negativos se define por la regla $a_{n+2} = |a_{n+1} - a_n|$ para $n \ge 1.$ Si $a_1 = 999,$ $a_2 \lt 999,$ y $a_{2006} = 1,$ ¿cuántos valores distintos de $a_2$ son posibles?

A sequence $a_1, a_2, \ldots$ of non-negative integers is defined by the rule $a_{n+2} = |a_{n+1} - a_n|$ for $n \ge 1.$ If $a_1 = 999,$ $a_2 \lt 999,$ and $a_{2006} = 1,$ how many different values of $a_2$ are possible?

$165$

$324$

$495$

$499$

$660$

Respuesta: B

Conceptos:máximo común divisor paridad inclusión-exclusión

Nivel de dificultad: 2520

Solución:

La regla da $a_n \equiv a_{n+3} \pmod 2,$ así que $a_2$ tiene la misma paridad que $a_{2006} = 1;$ por tanto, $a_2$ es impar.

Cada término es múltiplo de $\gcd(a_1, a_2),$ y $a_{2006} = 1$ obliga a que $\gcd(999, a_2) = 1.$ Como $999 = 3^3 \cdot 37,$ necesitamos que $a_2$ no sea divisible entre $3$ ni $37.$

Entre los enteros impares de $[1, 998]$ hay $499;$ quitando los $166$ múltiplos de $3$ y los $13$ múltiplos de $37,$ y añadiendo de nuevo los $4$ múltiplos de $111,$ quedan $499 - 166 - 13 + 4 = 324.$

Cada uno de estos valores de $a_2$ funciona. Para términos positivos consecutivos $u,v,$ la actualización $(u,v)\mapsto(v,|v-u|)$ reduce su máximo en a lo sumo dos pasos. Como ambos términos iniciales son a lo sumo $999,$ aparece algún $a_N=0$ con $N\le1999.$

El máximo común divisor de cada pareja consecutiva es invariante, así que los términos iguales justo antes de ese cero son ambos $\gcd(999,a_2)=1.$ La sucesión entra entonces en el ciclo $1,1,0.$ Finalmente, $2006\equiv2\pmod3,$ así que $a_{2006}$ tiene la misma paridad impar que $a_2;$ dentro de este ciclo, debe ser $1.$

Por lo tanto, la respuesta correcta es B.

The rule gives $a_n \equiv a_{n+3} \pmod 2,$ so $a_2$ has the same parity as $a_{2006} = 1;$ thus $a_2$ is odd.

Every term is a multiple of $\gcd(a_1, a_2),$ and $a_{2006} = 1$ forces $\gcd(999, a_2) = 1.$ Since $999 = 3^3 \cdot 37,$ we need $a_2$ not divisible by $3$ or $37.$

Among the odd integers in $[1, 998]$ there are $499;$ removing the $166$ multiples of $3$ and $13$ multiples of $37,$ then adding back the $4$ multiples of $111,$ leaves $499 - 166 - 13 + 4 = 324.$

Each such $a_2$ works. For consecutive positive terms $u,v,$ the update $(u,v)\mapsto(v,|v-u|)$ reduces their maximum within at most two steps. Since both initial terms are at most $999,$ some $a_N=0$ occurs by $N\le1999.$

The gcd of each consecutive pair is invariant, so the equal terms immediately before that zero both equal $\gcd(999,a_2)=1.$ The sequence then cycles through $1,1,0.$ Finally, $2006\equiv2\pmod3,$ so $a_{2006}$ has the same odd parity as $a_2;$ in this cycle it must therefore be $1.$

Thus, the correct answer is B.

2006 AMC 12B Problema 25

Respuesta: B

Nivel de dificultad: 2520

Solución:

El Problema 25 en otros años