2010 USAMO Problems/Problem 3
Problem
The positive numbers
satisfy
the inequality
for all distinct indices
.
Determine, with proof, the largest possible value of the product
.
Solution
The largest possible value is
Proof
No larger value is possible, since for each consecutive pair of elements:
, the product is at most
, and so the product of all the pairs is at most:
If we can demonstrate a sequence in which for all the product
, and all the inequalities are satisfied, the above
upper bound will be achieved and the proof complete.
We will construct sequences of an arbitrarily large even length ,
in which:
Given , from the equations
,
we obtain the whole sequence recursively:
And as a result:
The same equations can be used to compute the
whole sequence from any other known term.
We will often need to compare fractions in which the numerator and denominator
are both positive, with fractions in which a positive term is added to both.
Suppose are three positive real numbers, then:
Returning to the problem in hand, for ,
.
If it were otherwise, we would have for some
:
so our assumption is impossible.
Therefore, we need only verify inequalities with an index difference of
or
, as these imply the rest.
Now, when the indices differ by we have ensured equality (and
hence the desired inequalities) by construction. So, we only need
to prove the inequalities for successive even index and successive
odd index pairs, i.e. for every index
, prove
.
We now compare with
. By our
recurrence relations:
So, for both odd and even index pairs, the strict inequality
follows from
and we need only prove the inequalities
and
, the second of which holds (as an equality)
by construction, so only the first remains.
We have not yet used the equation , with this
we can solve for the last three terms (or equivalently their squares)
and thus compute the whole sequence. From the equations:
multiplying any two and dividing by the third, we get:
from which,
With the squares of the last four terms in hand, we can now verify the only non-redundant inequality:
The inequality above follows because the numerator and denominator are both positive for .
This completes the construction and the proof of all the inequalities, which miraculously reduced to just one inequality for the last pair of odd indices.
Additional observations
If we choose a different first term, say , the
sequence
will have the form:
the same holds if we have a longer sequence, at every index of the shorter sequence, the longer sequence will be a constant multiple (for all the odd terms) or dividend (for all the even terms) of the corresponding term of shorter sequence.
We observe that our solution is not unique, indeed for any ,
the same construction with
terms, truncated to just the
first
terms, yields a sequence
which also satisfies all
the required conditions, but in this case
.
We could have constructed this alternative solution directly,
by replacing the right hand side in the equation
with any smaller value for which we still get
.
In the modified construction, for some constant , we have:
and so:
which satisfies the required inequality provided:
The ratio , between the largest and smallest
possible value of
is in fact the ratio between the largest and
smallest values of
that yield a sequence that meets the
conditions for at least
terms.
In the case, the equation for
gives:
. We will next consider what happens to
, and
the sequence of squares in general, as
increases.
Let denote the
odd and
even terms, respectively, of the unique sequence which satisfies our
original equations and has
terms in total.
Let
be the odd and even terms
of the solution with
terms. We already noted that there
must exist a constant
(that depends on
, but not on
),
such that:
This constant is found explicitly by comparing the squares of the last
term of the solution of length
with the square of
the third last term
of the solution of length
:
Clearly for all positive
, and so for fixed
, the
odd index terms
strictly increase with
, while
the even index terms
decrease with
.
Therefore, for ,
The product converges to a finite value even if taken infinitely
far, and we can conclude (by a simple continuity argument) that
there is a unique infinite positive sequence , in which
, that satisfies all the
inequalities
. The
square of the first term of the infinite sequence is:
In summary, if we set ,
and then recursively set
, we get an infinite
sequence that, for all
, yields the maximum possible product
, subject to the conditions
.
See also
2010 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |