Difference between revisions of "2005 IMO Problems/Problem 2"
m (→Solution) |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
| − | {{ | + | <math>{a_n}</math> satisfies the conditions if and only if <math>{a_n-a_1}</math> does. |
| + | Therefore we can assume that <math>a_1=0</math> | ||
| + | |||
| + | First of all, <math>|a_n|<n</math> | ||
| + | Otherwise, <math>a_n = 0</math> mod <math>a_{a_n}</math> | ||
| + | |||
| + | |||
| + | 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> | ||
| + | |||
| + | |||
| + | This proves that if <math>{a_n}</math> contains an infinite number of positive and negative numbers, it must contain each integer exactly once. | ||
| + | |||
| + | ~Kscv | ||
==See Also== | ==See Also== | ||
{{IMO box|year=2005|num-b=1|num-a=3}} | {{IMO box|year=2005|num-b=1|num-a=3}} | ||
Latest revision as of 08:07, 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 
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 | ||
