2005 IMO Problems/Problem 2
Problem
Let be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer the numbers leave different remainders upon division by . Prove that every integer occurs exactly once in the sequence.
Solution
satisfies the conditions if and only if does. Therefore we can assume that
First of all, Otherwise, mod
Claim: is either the smallest positive number not in or the largest negative number not in this set.
- Proof by induction: the induction hypothesis implies that are consecutive. Let m and M be the smallest and largest numbers in this consecutive set, respectively. It is clear that mod . But since , or
This proves that if 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 |