Question

La sucesión $(a_n)$ se define recursivamente por $a_0=1,$ $a_1=\sqrt[19]{2},$ y $a_n=a_{n-1}a_{n-2}^2$ para $n\ge2.$ ¿Cuál es el menor entero positivo $k$ tal que el producto $a_1a_2\cdots a_k$ es un entero?

The sequence $(a_n)$ is defined recursively by $a_0=1,$ $a_1=\sqrt[19]{2},$ and $a_n=a_{n-1}a_{n-2}^2$ for $n\ge2.$ What is the smallest positive integer $k$ such that the product $a_1a_2\cdots a_k$ is an integer?

$17$

$18$

$19$

$20$

$21$

Respuesta: A

Conceptos:recursión aritmética modular orden multiplicativo

Nivel de dificultad: 2650

Pista pequeña:

Escribe $a_n=2^{\frac{b_n}{19}}.$ Entonces $b_0=0,$ $b_1=1,$ y $b_n=b_{n-1}+2b_{n-2}$ .

Write $a_n=2^{\frac{b_n}{19}}.$ Then $b_0=0,$ $b_1=1,$ and $b_n=b_{n-1}+2b_{n-2}$

Pista grande:

El producto es un entero exactamente cuando $b_1+b_2+\cdots+b_k$ es divisible por $19;$ resuelve $b_n=\tfrac13(2^n-(-1)^n)$ y usa el orden de $2$ módulo $19$ .

The product is an integer exactly when $b_1+b_2+\cdots+b_k$ is divisible by $19;$ solve $b_n=\tfrac13(2^n-(-1)^n)$ and use the order of $2$ modulo $19$

Solución:

Escribamos $a_n=2^{\frac{b_n}{19}}.$ La recurrencia se convierte en $b_0=0,$ $b_1=1,$ $b_n=b_{n-1}+2b_{n-2},$ cuya solución es $b_n=\tfrac13\bigl(2^n-(-1)^n\bigr).$ El producto $a_1\cdots a_k$ es entero exactamente cuando $b_1+\cdots+b_k$ es divisible por $19.$ Al sumar la fórmula para $b_n$ , obtenemos $b_1+\cdots+b_k=\dfrac{2^{k+1}-1}{3}$ cuando $k$ es impar, y $b_1+\cdots+b_k=\dfrac{2^{k+1}-2}{3}$ cuando $k$ es par.

El orden de $2$ módulo $19$ es $18$ porque $2^9\equiv-1\pmod{19}$ y $2^6\not\equiv1\pmod{19}.$ Para $k$ impar, la divisibilidad exige que $k+1$ sea divisible por $18,$ lo que ocurre por primera vez en $k=17.$ Para $k$ par, exige que $k$ sea divisible por $18,$ lo que ocurre por primera vez en $k=18.$ Por tanto, el menor $k$ positivo es $17.$

Por lo tanto, la respuesta correcta es A.

Write $a_n=2^{\frac{b_n}{19}}.$ The recursion becomes $b_0=0,$ $b_1=1,$ $b_n=b_{n-1}+2b_{n-2},$ solved by $b_n=\tfrac13\bigl(2^n-(-1)^n\bigr).$ The product $a_1\cdots a_k$ is an integer exactly when $b_1+\cdots+b_k$ is divisible by $19.$ Summing the formula for $b_n$ gives $b_1+\cdots+b_k=\dfrac{2^{k+1}-1}{3}$ when $k$ is odd, and $b_1+\cdots+b_k=\dfrac{2^{k+1}-2}{3}$ when $k$ is even.

The order of $2$ modulo $19$ is $18$ because $2^9\equiv-1\pmod{19}$ and $2^6\not\equiv1\pmod{19}.$ For odd $k,$ divisibility therefore requires $k+1$ to be divisible by $18,$ first occurring at $k=17.$ For even $k,$ it requires $k$ to be divisible by $18,$ first occurring at $k=18.$ Hence the smallest positive $k$ is $17.$

Thus, the correct answer is A.

2016 AMC 12B Problema 25

Respuesta: A

Nivel de dificultad: 2650

Pista pequeña:

Pista grande:

Solución:

El Problema 25 en otros años