2007 USAMO Problems/Problem 1

Revision as of 22:52, 17 March 2012 by Quantumbyte (talk | contribs) (Solution 2)

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

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 2

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

Because $k\le \frac{n+1}{2}\le n$, the sequence must eventually become 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