2010 USAJMO Problems/Problem 2
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 .
The sequence is .
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.
Let . Notice that Then by condition (c), we must have . This implies that , or that . Then we have , and the rest is trivial.
The claim is that in this sequence, if there are elements where , such that , then the sequence contains every number less than .
Proof: Let and be the numbers less than such that . We take this sequence modulo . This means that if is an element in this sequence then is as well. are all elements in the sequence. Clearly, one of and is less than , which means that are in this sequence modulo . Now we want to show every number is achievable. We have already established that and are relatively prime, so by euclidean algorithm, if we take the positive difference of and every time, we will get that is in our sequence. Then, we can simply add or subtract as many times from as desired to get every single number.
We have proved that there are no two numbers that can be relatively prime in our sequence, implying that no two consecutive numbers can be in this sequence. Because our sequence has terms, our sequence must be one of or , the latter obviously fails, so is our only possible sequence.
|2010 USAJMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAJMO Problems and Solutions|