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

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

Page

Toolbox

Search

2005 IMO Problems/Problem 2

Problem

Solution

See Also