Question

设 $a_{10} = 10$ ，且对每个整数 $n \gt 10$ ，令 $a_n = 100a_{n-1} + n$ 。求最小的 $n \gt 10$ ，使得 $a_n$ 是 $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.$

答案

答案：45

知识点：模运算递推分类讨论

难度评级：2840

解答：

因为 $100 \equiv 1 \pmod{99}$ ，递推式给出 $a_n \equiv a_{n-1} + n \pmod{99}$ ，所以 $\begin{aligned} &a_n \equiv 10 + 11 + \cdots + n \\ &\quad \small = \frac{(n + 10)(n - 9)}{2} \pmod{99}. \end{aligned}$ 我们需要 $99 \mid \frac{(n+10)(n-9)}{2}$ 。 $n + 10$ 和 $n - 9$ 中有一个是偶数，所以这等价于要求 $9$ 和 $11$ 都整除这个乘积。由于这两个因子相差 $19$ ，它们不可能都为 $3$ 的倍数。

因此 $9$ 必须完全整除其中一个因子，而 $11$ 整除另一个因子（或者某个因子被 $99$ 整除）。检查各情况： $99 \mid n - 9$ 最早在 $n = 108$ 时发生； $99 \mid n + 10$ 最早在 $n = 89$ 时发生； $9 \mid n + 10$ 且 $11 \mid n - 9$ 最早在 $n = 53$ 时发生； $11 \mid n + 10$ 且 $9 \mid n - 9$ 最早在 $n = 45$ 时发生。

最小值是 $n = 45$ ，此时 $\frac{55 \cdot 36}{2} = 990$ 确实是 $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 第 9 题

答案：45

难度评级：2840

解答：

其他年份的第 9 题