IMO 2005 Problem 2

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\).

Proof:

We prove by induction that for each \(n\), \(a_1,\ldots,a_n\) are \(n\) consecutive integers after some permutation. Together with infinitely many positive and negative terms in the sequence the desired result follows.

Suppose it holds for \(n\), i.e. the first \(n\) numbers are \(M+1,M+2,\ldots,M+n\) up to permutation. What could \(a_{n+1}\) be? Clearly \(a_{n+1}\equiv M\mod {(n+1)}\). If \(a_{n+1}\) is below \(M\), then with \(M+n\) it has the same remainder when divided by \(n-a_{n+1}\geq n+1\), contradicting the requirement. Similarly \(a_{n+1}\) cannot be greater than \(M+n+1\), so it is either \(M\) or \(M+n+1\), and the first \(n+1\) terms are \(n+1\) consecutive numbers up to permutation.

Q.E.D.