2007 USAMO Problems/Problem 1

Problem

(Sam Vandervelde) 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.

Solutions

Solution 1

Let $S_k = a_1 + a_2 + \cdots + a_k$ and $b_k = \frac{S_k}{k}$ . Thus, because $S_{k+1} = S_k + a_{k+1}$ , $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$ and $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\leq k - 1$ , we have that $a_1 + a_2 + \cdots + a_n\leq n + 1 + 2 + \cdots + n - 1 = \frac{n(n + 1)}{2}.$ Since $a_1 + a_2 + \cdots + a_n = nk$ for some integer $k$ , we can keep adding $k$ to satisfy the conditions, provided that $k\leq n$ . This is true since $k\leq\frac{n + 1}{2}\leq n$ , so the sequence must eventually become constant.

Solution 3

Define $S_k = a_1 + a_2 + \cdots + a_k$ , and $b_k = \frac{S_k}{k}$ . By the problem hypothesis, $b_k$ is an integer valued sequence.

Lemma: There exists a $k$ such that $b_k < k$ .

Proof: Choose any $k$ such that $k^2 + 3k - 2 > 2n$ . Then $\begin{align*} \frac{k^2 + 3k - 2}{2} &> n \\ k^2 &> \frac{k^2 - 3k + 2}{2} + n \\ k^2 &> (k-2) + (k-1) + \cdots + 1 + n \\ k^2 &> a_{k-1} + a_{k-2} + \cdots + a_2 + a_1 \\ k^2 &> S_k \\ k &> \frac{S_k}{k} \\ k &> b_k, \end{align*}$ as desired. $\blacksquare$

Let $k$ be the smallest $k$ such that $b_k < k$ . Then $b_k = m < k$ , and $S_k = km$ . To make $b_{k+1}$ an integer, $S_{k+1} = S_k + a_{k+1}$ must be divisible by $k+1$ . Thus, because $km + m$ is divisible by $k+1$ , $a_{k+1} \equiv m \pmod{k+1}$ , and, because $0 \le a_{k+1} < k$ , $a_{k+1} = m$ . Then $b_{k+1} = \frac{(k+1)m}{k+1} = m$ as well. Repeating the same process using $k+1$ instead of $k$ gives $a_{k+2} = m$ , and an easy induction can prove that for all $N > k+1$ , $a_N = m$ . Thus, $a_k$ becomes a constant function for arbitrarily large values of $k$ .

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

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