Difference between revisions of "2010 USAJMO Problems/Problem 2"
Expilncalc (talk | contribs) m (→Proof: Added clarification) |
|||
Line 42: | Line 42: | ||
x_{n-2} = x_{n-1}</math>. | x_{n-2} = x_{n-1}</math>. | ||
+ | Now for the induction step on all values of <math>m</math>. | ||
Suppose we have shown that for all <math>i \le m</math>, <math>x_1 + x_{n-1-i} = | Suppose we have shown that for all <math>i \le m</math>, <math>x_1 + x_{n-1-i} = | ||
x_{n-i}</math>. If <math>m = n-2</math> we are done, otherwise <math>m < n-2</math>, and by | x_{n-i}</math>. If <math>m = n-2</math> we are done, otherwise <math>m < n-2</math>, and by |
Revision as of 16:31, 5 April 2018
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.