2007 USAMO 第 1 题

Let $n$ be a positive integer. Define a sequence by setting $a_1 = n$ and, for each $k>1$, letting $a_k$ be the unique integer in the range $0 \le a_k \le k-1$ for which $a_1 + a_2 + \cdots + a_k$ is divisible by $k$. For instance, when $n=9$ the obtained sequence is $9, 1, 2, 0, 3, 3, 3, \ldots$. Prove that for any $n$ the sequence $a_1, a_2, a_3, \ldots$ eventually becomes constant.

令 $n$ 为正整数。通过设置 $a_1 = n$ 来定义序列，并且对于每个 $k>1$，令 $a_k$ 为 $0 \le a_k \le k-1$ 范围内的唯一整数，其中 $a_1 + a_2 + \cdots + a_k$ 可被 $k$ 整除。例如，当$n=9$时，获得的序列为$9,1,2,0,3,3,3,\ldots$。证明对于任何 $n$，序列 $a_1, a_2, a_3, \ldots$ 最终变为常数。