2003 USAMO Problems/Problem 3
Problem
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
.
Solution
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.