2007 USAMO Problems/Problem 1

Problem

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 $\displaystyle a_1 + a_2 + \cdots + a_k$ is divisible by $k$ . For instance, when $n=9$ the obtained sequence is $\displaystyle 9, 1, 2, 0, 3, 3, 3, \ldots$ . Prove that for any $n$ the sequence $\displaystyle a_1, a_2, a_3, \ldots$ eventually becomes constant.

Solution

Suppose we create a parallel integer sequence $\displaystyle b_1, b_2, \ldots$ such that for every $\displaystyle k \ge 1$ , we have that $b_k = \displaystyle \sum_{i=1}^{k} / k$ . Consider what happens when $b_k \le k$ . For $\displaystyle k + 1$ , we have that $b_{k+1} = \displaystyle \sum_{i=1}^{k+1} / (k+1) = \left(\displaystyle \sum_{i=1}^{k} + a_{k+1}\right) / (k+1) = \frac{b_k \times k + a_{k+1}}{k+1}$ . $\displaystyle b_k$ is a permissible value of $a_{k+1} \displaystyle$ since $b_k \le k \le (k+1)-1$ : if we substitute $\displaystyle b_k$ for $a_{k+1} \displaystyle$ , we get that $b_{k+1} = \frac{b_k (k+1)}{k+1} = b_k$ . $\displaystyle b_k$ is the unique value for $a_{k+1} \displaystyle$ . We can repeat this argument for $\displaystyle b_k = b_{k+1} = b_{k+2} \ldots$ . As we substituted the $\displaystyle b_k$ s for the $\displaystyle a_k$ s, the $\displaystyle a_k$ s also become constant.

Now we must show that $\displaystyle b_k$ eventually $\le k$ . Suppose that $\displaystyle b_k$ always $\displaystyle > k$ . By definition, $\displaystyle \sum_{i=1}^{k} / k = b_k > k$ , so $\displaystyle \sum_{i=1}^{k} a_i > k^2$ . We also have that each $a_i \le i-1$ so that $k^2 < \displaystyle \sum_{i=1}^{k} \le n + 1 + 2 + \ldots + (k-1) = n + \frac{k^2 - k}2$ . So $k^2 < n +\frac{k^2 - k}2 \Longrightarrow \frac{k^2 + k}2 < n$ . But $\displaystyle n$ is constant while $\displaystyle k$ is increasing, so eventually we will have a contradiction and $b_k \le k$ . Therefore, the sequence of $\displaystyle a_i$ s will become constant.

2007 USAMO (Problems • Resources)
Preceded by First question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2007 USAMO Problems/Problem 1

Problem

Solution