Difference between revisions of "2005 IMO Problems/Problem 2"
m (→Solution) |
m (→Solution) |
||
Line 12: | Line 12: | ||
Claim: <math>a_{k+1}</math> is either the smallest positive number not in <math>{a_1, a_2, ..., a_k}</math> or the largest negative number not in this set. | Claim: <math>a_{k+1}</math> is either the smallest positive number not in <math>{a_1, a_2, ..., a_k}</math> or the largest negative number not in this set. | ||
− | + | *Proof by induction: the induction hypothesis implies that <math>a_1, a_2, ..., a_k</math> are consecutive. Let m and M be the smallest and largest numbers in this consecutive set, respectively. It is clear that <math>a_{k+1}=m-1=M+1</math> mod <math>k+1</math>. But since <math>|a_n|<n</math>, <math>a_{k+1}=m-1</math> or <math>M+1</math> | |
Revision as of 01:11, 19 November 2023
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.
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 |