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

Respuesta: 45

Conceptos:aritmética modular recursión análisis por casos

Nivel de dificultad: 2840

Pista pequeña:

Como $100 \equiv 1 \pmod{99},$ la recurrencia se reduce a $a_n \equiv 10 + 11 + \cdots + n$ $\pmod{99}$

Since $100 \equiv 1 \pmod{99},$ the recurrence collapses to $a_n \equiv 10 + 11 + \cdots + n$ $\pmod{99}$

Pista grande:

Necesitas que $99$ divida a $\frac{(n+10)(n-9)}{2}.$ Los factores difieren en $19,$ así que $3$ no puede dividir a ambos; separa casos según a qué factor dividen $9$ y $11$ .

You need $99$ to divide $\frac{(n+10)(n-9)}{2}.$ The factors differ by $19,$ so $3$ cannot divide both; split cases by which factor $9$ and $11$ divide.

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 que $99$ divida a $\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$ divide a $n - 9$ por primera vez en $n = 108;$ $99$ divide a $n + 10$ por primera vez en $n = 89;$ $9$ divide a $n + 10$ con $11$ dividiendo a $n - 9$ por primera vez en $n = 53;$ y $11$ divide a $n + 10$ con $9$ dividiendo a $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$ to divide $\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$ divides $n - 9$ first at $n = 108;$ $99$ divides $n + 10$ first at $n = 89;$ $9$ divides $n + 10$ with $11$ dividing $n - 9$ first at $n = 53;$ and $11$ divides $n + 10$ with $9$ dividing $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

Respuesta: 45

Nivel de dificultad: 2840

Pista pequeña:

Pista grande:

Solución:

El Problema 9 en otros años