# 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 $|a_i-a_j|$, which violates the given condition for the sequence when $n=|a_i-a_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.