2010 USAJMO Problems/Problem 2
Contents
[hide]Problem
Let be an integer. Find, with proof, all sequences of positive integers with the following three properties:
- (a). ;
- (b). for all ;
- (c). given any two indices and (not necessarily distinct) for which , there is an index such that .
Solution
The sequence is .
Proof
We will prove that any sequence , that satisfies the given conditions, is an arithmetic progression with as both the first term and the increment. Once this is proved, condition (b) implies that . Therefore , and the sequence is just the even numbers from to . The sequence of successive even numbers clearly satisfies all three conditions, and we are done.
First a degenerate case. If , there is only one element , and condition (b) gives or . Conditions (a) and (c) are vacuously true.
Otherwise, for , we will prove by induction on that the difference for all , which makes all the differences , i.e. the sequence is an arithmetic progression with as the first term and increment as promised.
So first the case. With , exists and is less than by condition (a). Now since by condition (b) , we conclude that , and therefore by condition (c) for some . Now, since , and can only be . So .
Now for the induction step on all values of . Suppose we have shown that for all , . If we are done, otherwise , and by condition (c) for some . This is larger than , but smaller than by the inductive hypothesis. It then follows that , the only element of the sequence between and . This establishes the result for .
So, by induction for all , which completes the proof.
See Also
2010 USAJMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.