2003 USAMO Problems/Problem 3
Let . For every sequence of integers
satisfying , for , define another sequence
by setting to be the number of terms in the sequence that precede the term and are different from . Show that, starting from any sequence as above, fewer than applications of the transformation lead to a sequence such that .
Consider some sequence as the image of after has been applied some finite number of times.
Lemma 1. If , then ().
Proof. Since the terms are all less than , no other terms that precede can be unequal to . The lemma follows.
Lemma 2. If , then (where ).
Proof. Since only terms precede the term , we will have , for any integer . This means that we will always have . This means that , and the lemma follows by iteration.
Thus we may regard a term as stable if . We will call a sequence stable if all of its terms are stable.
Lemma 3. If is not stable, then .
Proof. We have , so we always have . Equality implies that is stable.
We will now prove the problem by induction. For the base case, , we have either 0,0 or 0,1, both of which are stable. Now, suppose that are stable. We must then have . If , then it is already stable. If , then either it is already stable or , which is stable. If , then must already be stable. The only possibilities remaining are and . In the first case, we must have equal to or , both of which will make it stable. In the second case, we must have , giving us , which will make it stable. Thus the induction is complete.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
|2003 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|