2005 IMO Shortlist Problems/N2

Problem

Let $a_1,a_2,\ldots$ be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer $n$ the numbers $a_1,a_2,\ldots,a_n$ leave $n$ different remainders upon division by $n$ .

Prove that every integer occurs exactly once in the sequence $a_1,a_2,\ldots$ .

Solution

It is clear that $a_i=a_j$ if and only if $i=j$ , or the sequence would not satisfy the specified property.

If $|a_i-a_j|\geq \max(i,j)$ , then $a_i$ and $a_j$ leave the same remainder when divided by $\max(i,j)$ . It then follows that $|a_i-a_j|<\max(i,j)$ for all positive integers $i$ and $j$ . Now consider $\min(a_1,a_2,\ldots,a_n)$ , and let this be $a_k$ , with $k\in [1,n]$ . It follows that $a_1,a_2,\ldots a_{n}$ are all in the closed interval $[a_k,a_k+n-1]$ , and hence $a_1,a_2,\ldots a_n$ is a permutation of $n$ consecutive numbers, for all $n$ .

Note that there are infinitely many positive and negative terms. Therefore for any arbitrarily large integer $\Delta$ there exists an $i$ such that $a_i\geq \Delta$ and a $j$ such that $a_j\leq -\Delta$ . Since $a_1,a_2,\ldots, a_n$ is a permutation of $n$ consecutive integers, it follows that every integer in the range $[-\Delta,\Delta]$ is in the sequence, and consequently every integer occurs in the sequence.

Page

Toolbox

Search

2005 IMO Shortlist Problems/N2

Problem

Solution

See Also