Difference between revisions of "2010 USAJMO Problems/Problem 2"
(→Solution 3) |
(→Solution 3) |
||
Line 65: | Line 65: | ||
==Solution 3== | ==Solution 3== | ||
− | We will first look at <math>x_1</math> and <math>x_{n-2}</math>. Notice that since <math>x_{n-2}<x_{n-1}</math> condition <math>(c)</math> applies to these numbers. Therefore, <math>x_1</math> and <math>x_{n-2}</math> must sum to the only index greater than <math>x_{n-2}</math>, which is <math>x_{n-1} = 2n - x_1</math>. We also know that <math>x_{n-2} = 2n - x_2</math>. Equating, <math>x_1 + 2n - x_2 = 2n - x_1 \implies 2x_1 = x_2</math>. We can similarly force <math>x_1 + x_{n-3} = x_{n-2}</math> and <math>x_2 + x_{n-3} = x_{n-1}</math>. These both result in <math>3x_1 = x_3</math>. | + | We will first look at <math>x_1</math> and <math>x_{n-2}</math>. Notice that since <math>x_{n-2}<x_{n-1}</math> condition <math>(c)</math> applies to these numbers. Therefore, <math>x_1</math> and <math>x_{n-2}</math> must sum to the only index greater than <math>x_{n-2}</math>, which is <math>x_{n-1} = 2n - x_1</math>. We also know that <math>x_{n-2} = 2n - x_2</math>. Equating, <math>x_1 + 2n - x_2 = 2n - x_1 \implies 2x_1 = x_2</math>. We can similarly force <math>x_1 + x_{n-3} = x_{n-2}</math> and <math>x_2 + x_{n-3} = x_{n-1}</math>. These both result in <math>3x_1 = x_3</math>. It can easily be verified by induction that <math>x_k = kx_1</math>. |
− | Therefore, <math>x_{n-1} = 2n - x_1 = (n-1)x_1</math>. Taking the last equality and simplifying, we get <math>x_1 = 2</math>. | + | Therefore, <math>x_{n-1} = 2n - x_1 = (n-1)x_1</math>. Taking the last equality and simplifying, we get <math>x_1 = 2</math>. The desired sequence is <math>2, 4, 6, ... 2n-2</math>. |
+ | |||
+ | ~Leonard_my_dude~ | ||
== See Also == | == See Also == |
Revision as of 21:53, 25 January 2021
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.
Solution 2
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.
Solution 3
We will first look at and
. Notice that since
condition
applies to these numbers. Therefore,
and
must sum to the only index greater than
, which is
. We also know that
. Equating,
. We can similarly force
and
. These both result in
. It can easily be verified by induction that
.
Therefore, . Taking the last equality and simplifying, we get
. The desired sequence is
.
~Leonard_my_dude~
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.