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|<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|<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

See Also

2005 IMO (Problems) • Resources
Preceded by
Problem 1
1 2 3 4 5 6 Followed by
Problem 3
All IMO Problems and Solutions