2007 USAMO Problems/Problem 1

From AoPSWiki

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 $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.

Solution

Solution 1

Define $s_k =\sum_{i=1}^{k} a_i$ , and $b_k = \frac{s_k}{k}$ . If $b_k \le k$ , then for $k + 1$ , $b_{k+1} = \frac{s_{k+1}}{k + 1} = \frac{s_k + a_{k+1}}{k+1} = \frac{b_k \cdot k + a_{k+1}}{k+1}$ . Note that $b_k$ is a permissible value of $a_{k+1}$ since $b_k \le k = (k+1)-1$ : if we substitute $b_k$ for $a_{k+1}$ , we get $b_{k+1} = \frac{b_k (k+1)}{k+1} = b_k$ , the unique value for $a_{k+1}$ . So $b_k = b_{k+1} = b_{k+2} = \cdots$ , from which if follows that the $a_k$ s become constant.

Now we must show that eventually $b_k \le k$ . Suppose that $b_k > k$ for all $k$ . By definition, $\frac {s_k}{k} = b_k > k$ , so $s_k > k^2$ . Also, for $i>1$ , each $a_i \le i-1$ so

$k^2 < s_k \le n + 1 + 2 + \cdots + (k-1) = n + \frac{k^2 - k}2$
$k^2 < n +\frac{k^2 - k}2 \Longrightarrow \frac{k^2 + k}2 < n$

But $n$ is constant while $k$ is increasing, so eventually we will have a contradiction and $b_k \le k$ . Therefore, the sequence of $a_i$ s will become constant.

Solution 2

By the above, we have that

$b_{k+1} = \frac{b_k \cdot k + a_{k+1}}{k+1} = \left(\frac{k}{k+1}\right) \cdot b_k + \frac{a_{k+1}}{k+1}$

$\frac{k}{k+1} < 1$ , and by definition, $\frac{a_{k+1}}{k+1} < 1$ . Thus, $b_{k+1} < b_k + 1$ . Also, both $b_k,\ b_{k+1}$ are integers, so $b_{k+1} \le b_k$ . As the $b_k$ s form a non-increasing sequence of positive integers, they must eventually become constant.

Therefore, $b_k = b_{k+1}$ for some sufficiently large value of $k$ . Then $a_{k+1} = s_{k+1} - s_k = b_k(k + 1) - b_k(k) = b_k$ , so eventually the sequence $a_k$ becomes constant.

Solution 3

Let $a_1=n$ . Since $a_k\le k-1$ , we have that $a_1+a_2+a_3+\hdots+a_n\le n+1+2+\hdots+n-1$ .

Thus, $a_1+a_2+\hdots+a_n\le \frac{n(n+1)}{2}$ .

Since $a_1+a_2+\hdots+a_n=nk$ , for some integer $k$ , we can keep adding $k$ to satisfy the conditions, provided that $k\le n$ because $a_n+1\le n$ .