Question

Sea $a_{10} = 10,$ y para cada entero $n \gt 10$ sea $a_n = 100a_{n-1} + n.$ Halla el menor $n \gt 10$ tal que $a_n$ sea múltiplo de $99.$

Let $a_{10} = 10,$ and for each integer $n \gt 10$ let $a_n = 100a_{n-1} + n.$ Find the least $n \gt 10$ such that $a_n$ is a multiple of $99.$

Respuesta

Solución:

Como $100 \equiv 1 \pmod{99},$ la recurrencia da $a_n \equiv a_{n-1} + n \pmod{99},$ así que $\begin{aligned} &a_n \equiv 10 + 11 + \cdots + n \\ &\quad \small = \frac{(n + 10)(n - 9)}{2} \pmod{99}. \end{aligned}$ Necesitamos $99 \mid \frac{(n+10)(n-9)}{2}.$ Uno de $n + 10$ y $n - 9$ es par, así que esto es lo mismo que exigir que $9$ y $11$ dividan cada uno al producto. Como los dos factores difieren en $19,$ no pueden ser ambos múltiplos de $3.$

Así que $9$ debe dividir por completo a un factor y $11$ al otro (o bien un factor es divisible entre $99$ ). Revisando los casos: $99 \mid n - 9$ por primera vez en $n = 108;$ $99 \mid n + 10$ por primera vez en $n = 89;$ $9 \mid n + 10$ con $11 \mid n - 9$ por primera vez en $n = 53;$ y $11 \mid n + 10$ con $9 \mid n - 9$ por primera vez en $n = 45.$

El menor es $n = 45,$ donde $\frac{55 \cdot 36}{2} = 990$ es en efecto múltiplo de $99.$

Because $100 \equiv 1 \pmod{99},$ the recurrence gives $a_n \equiv a_{n-1} + n \pmod{99},$ so $\begin{aligned} &a_n \equiv 10 + 11 + \cdots + n \\ &\quad \small = \frac{(n + 10)(n - 9)}{2} \pmod{99}. \end{aligned}$ We need $99 \mid \frac{(n+10)(n-9)}{2}.$ One of $n + 10$ and $n - 9$ is even, so this is the same as requiring $9$ and $11$ each to divide the product. Since the two factors differ by $19,$ they cannot both be multiples of $3.$

So $9$ must divide one factor entirely and $11$ the other (or one factor is divisible by $99$ ). Checking the cases: $99 \mid n - 9$ first at $n = 108;$ $99 \mid n + 10$ first at $n = 89;$ $9 \mid n + 10$ with $11 \mid n - 9$ first at $n = 53;$ and $11 \mid n + 10$ with $9 \mid n - 9$ first at $n = 45.$

The least is $n = 45,$ where $\frac{55 \cdot 36}{2} = 990$ is indeed a multiple of $99.$

2017 AIME I Problema 9

Solución:

El Problema 9 en otros años