2010 USAJMO Problems/Problem 2
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
.
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.