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 17:31, 5 April 2018
Contents
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.