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 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 arbitrary large even length ,
in which:
Given , from the equations
,
we obtain the whole sequence recursively:
and in general:
The same equations can be used to compute the
whole sequence from any other known term.
For ,
.
If it were otherwise, we would have for some
:
but the ratio of the term to the next term of the same
parity is
, 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:
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.