2005 IMO Problems/Problem 2

Problem

Let $a_1, a_2, \dots$ 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, \dots, a_n$ leave $n$ different remainders upon division by $n$. Prove that every integer occurs exactly once in the sequence.

Solution

${a_n}$ satisfies the conditions if and only if ${a_n-a_1}$ does. Therefore we can assume that $a_1=0$

First of all, $|a_n| Otherwise, $a_n = 0$ mod $a_{a_n}$

Claim: $a_{k+1}$ is either the smallest positive number not in ${a_1, a_2, ..., a_k}$ or the largest negative number not in this set.

• Proof by induction: the induction hypothesis implies that $a_1, a_2, ..., a_k$ are consecutive. Let m and M be the smallest and largest numbers in this consecutive set, respectively. It is clear that $a_{k+1}=m-1=M+1$ mod $k+1$. But since $|a_n|, $a_{k+1}=m-1$ or $M+1$

This proves that if ${a_n}$ contains an infinite number of positive and negative numbers, it must contain each integer exactly once.

~Kscv