2007 USAMO Problems/Problem 1

Revision as of 22:06, 30 April 2007 by Azjps (talk | contribs) (Solution 2: b_k constant -> a_k constant)

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

Solution 1

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

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

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

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, $\displaystyle b_{k+1} < b_k + 1$. Also, both $b_k,\ b_{k+1}$ are integers, so $b_{k+1} \le b_k$. As the $\displaystyle b_k$s form a non-increasing sequence of positive integers, they must eventually become constant.

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

See also

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