Maths Olympiad Prep

Library / /104 of 115

Algebra Difficulty 7.7 National olympiad, round 2 Find the answer

The 20102010 positive numbers a1,a2,,a2010a_1, a_2, \ldots , a_{2010} satisfy
the inequality aiaji+ja_ia_j \le i+j for all distinct indices i,ji, j .
Determine, with proof, the largest possible value of the product a1a2a2010a_1a_2\cdots a_{2010} .

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The largest possible value is i=11005(4i1)=3×7××4019.\prod_{i=1}^{1005}(4i-1) = 3\times 7 \times \ldots \times 4019.
Proof
No larger value is possible, since for each consecutive pair of elements: (a2i1,a2i),1i1005(a_{2i-1},a_{2i}), 1\le i \le 1005 , the product is at most (2i1)+2i=4i1(2i-1) + 2i = 4i - 1 , and so the product of all the pairs is at most:

If we can demonstrate a sequence in which for all 1i10051 \le i \le 1005 the product a2i1a2i=4i1a_{2i-1}a_{2i} = 4i-1 , 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 2n42n \ge 4 ,
in which:

Given a1a_1 , from the equations aiai+1=2i+1,  1i2n1a_ia_{i+1} = 2i+1,\; 1\le i\le 2n-1 ,
we obtain the whole sequence recursively: a1=a1,  a2=3/a1,  a3=5/a2=5a1/3,  a4=7/a3=(37)/(5a1).a_1 = a_1,\; a_2 = 3/a_1,\; a_3 = 5/a_2 = 5a_1/3,\; a_4 = 7/a_3 = (3\cdot 7)/(5a_1) \ldots. And as a result:

The same equations aiai+1=2i+1a_ia_{i+1} = 2i+1 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 p,q,rp, q, r are three positive real numbers, then:

Returning to the problem in hand, for i<ji < j , aiaji+j    aiaj+2<i+j+2a_ia_j \le i+j \implies a_ia_{j+2} < i+j+2 .
If it were otherwise, we would have for some i<ji < j :

so our assumption is impossible.
Therefore, we need only verify inequalities with an index difference of 11 or 22 , as these imply the rest.
Now, when the indices differ by 11 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 i>2i > 2 , prove ai2ai2i2a_{i-2}a_i \le 2i-2 .
We now compare aiai+2/(2i+2)a_ia_{i+2}/(2i+2) with ai+2ai+4/(2i+6)a_{i+2}a_{i+4}/(2i+6) . By our
recurrence relations:

So, for both odd and even index pairs, the strict inequality aiai+2<2i+2a_ia_{i+2} < 2i+2 follows from ai+2ai+42i+6a_{i+2}a_{i+4} \le 2i+6 and we need only prove the inequalities a2n3a2n14n4a_{2n-3}a_{2n-1} \le 4n-4 and a2n2a2n4n2a_{2n-2}a_{2n} \le 4n-2 , the second of which holds (as an equality)
by construction, so only the first remains.
We have not yet used the equation a2n2a2n=4n2a_{2n-2}a_{2n} = 4n-2 , 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 n>1n > 1 .
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 a1=Ma1a_1' = M\cdot a_1 , the
sequence aia_i' 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 k>0k>0 ,
the same construction with 2n+2k2n+2k terms, truncated to just the
first 2n2n terms, yields a sequence aia'_i which also satisfies all
the required conditions, but in this case a2n2a2n<4n2a'_{2n-2}a'{2n} < 4n-2 .
We could have constructed this alternative solution directly,
by replacing the right hand side in the equation a2n2a2n=4n2a_{2n-2}a_{2n} = 4n-2 with any smaller value for which we still get a2n3a2n14n4a_{2n-3}a_{2n-1} \le 4n-4 .
In the modified construction, for some constant M>1M > 1 , we have:

and so:

which satisfies the required inequality provided:

The ratio MmaxM_{\mathrm{max}} , between the largest and smallest
possible value of a2n3a_{2n-3} is in fact the ratio between the largest and
smallest values of a1a_1 that yield a sequence that meets the
conditions for at least 2n2n terms.
In the n=2n=2 case, the equation for a2n3a_{2n-3} gives: a12=2110a_1^2 = \frac{21}{10} . We will next consider what happens to a12a_1^2 , and
the sequence of squares in general, as nn increases.
Let An,2i1,An,2iA_{n,2i-1}, A_{n,2i} denote the ithi^{\mathrm{th}} odd and
even terms, respectively, of the unique sequence which satisfies our
original equations and has 2n2n terms in total.
Let An+1,2i1,An+1,2iA_{n+1,2i-1}, A_{n+1,2i} be the odd and even terms
of the solution with 2n+22n+2 terms. We already noted that there
must exist a constant MnM_n (that depends on nn , but not on ii ),
such that:

This constant is found explicitly by comparing the squares of the last
term An,2nA_{n,2n} of the solution of length 2n2n with the square of
the third last term An+1,2nA_{n+1,2n} of the solution of length 2n+22n+2 :

Clearly Mn>1M_n > 1 for all positive nn , and so for fixed ii , the
odd index terms An,2i1A_{n,2i-1} strictly increase with nn , while
the even index terms An,2iA_{n,2i} decrease with nn .
Therefore, for n2n \ge 2 ,

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 AωA_\omega , in which Aω,iAω,i+1=2i+1A_{\omega,i}A_{\omega,i+1} = 2i+1 , that satisfies all the
inequalities Aω,iAω,j<i+j,  ij2A_{\omega,i}A_{\omega,j} < i+j,\; i \le j - 2 . The
square of the first term of the infinite sequence is:

In summary, if we set a1=πAGM(2,1)a_1 = \frac{\sqrt{\pi}}{\mathrm{AGM}(\sqrt{2}, 1)} ,
and then recursively set ai+1=(2i+1)/aia_{i+1} = (2i + 1)/a_i , we get an infinite
sequence that, for all n1n \ge 1 , yields the maximum possible product a1a2a2na_1a_2\cdots a_{2n} , subject to the conditions aiaji+j,  1i<j2na_ia_j \le i+j,\; 1 \le i < j \le 2n .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.