Difference between revisions of "2010 USAMO Problems/Problem 3"

Revision as of 11:57, 6 May 2010

Problem

The $2010$ positive numbers $a_1, a_2, \ldots , a_{2010}$ satisfy the inequality $a_ia_j \le i+j$ for all distinct indices $i, j$ . Determine, with proof, the largest possible value of the product $a_1a_2\cdots a_{2010}$ .

Solution

The largest possible value is $\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: $(a_{2i-1},a_{2i}), 1\le i \le 1005$ , the product is at most $(2i-1) + 2i = 4i - 1$ , and so the product of all the pairs is at most:

$\prod_{i=1}^{1005}(4i-1).$

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

$\begin{cases} a_ia_j = i+j = 2i+1 & j=i+1, \\ a_ia_j = i+j = 2n-2 & j = i+2 = 2n, \\ a_ia_j < i+j & i \ne 2n-2, \mbox{ and } i < j-1. \end{cases}$

Given $a_1$ , from the equations $a_ia_{i+1} = 2i+1,\; 1\le i\le 2n-1$ , we obtain the whole sequence recursively: $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:

$a_{i+2} = a_i \cdot \frac{2i+3}{2i+1}\quad 1 \le i \le 2n-2.$

The same equations $a_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, r$ are three positive real numbers, then:

$\begin{align*} p &> q \implies & \frac{p+r}{q+r} &< \frac{p}{q} \\ p &< q \implies & \frac{p+r}{q+r} &> \frac{p}{q} \\ & \mbox{and always} & \frac{p+r}{q} &> \frac{p}{q} \end{align*}$

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

$\frac{a_{j+2}}{a_j} \ge \frac{i+j+2}{i+j} > \frac{j+j+2}{j+j} = \frac{2j+2}{2j} > (2j+3)/(2j+1) = \frac{a_{j+2}}{a_j},$

so our assumption is impossible.

Therefore, we need only verify inequalities with an index difference of $1$ or $2$ , as these imply the rest.

Now, when the indices differ by $1$ 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 > 2$ , prove $a_{i-2}a_i \le 2i-2$ .

We now compare $a_ia_{i+2}/(2i+2)$ with $a_{i+2}a_{i+4}/(2i+6)$ . By our recurrence relations:

$\begin{align*} \frac{a_{i+2}a_{i+4}}{2i+6} &= \frac{a_ia_{i+2}}{2i+2} \cdot \frac{2i+2}{2i+6} \cdot \frac{a_{i+4}}{a_{i+2}}\cdot \frac{a_{i+2}}{a_i} \\ &= \frac{a_ia_{i+2}}{2i+2}\cdot \frac{i+1}{i+3}\cdot \frac{2i+7}{2i+5}\cdot \frac{2i+3}{2i+1} \\ &= \frac{a_ia_{i+2}}{2i+2}\cdot \frac{(i+1)(2i+7)(2i+3)}{(i+3)(2i+5)(2i+1)} \\ &= \frac{a_ia_{i+2}}{2i+2}\cdot \frac{4i^3+24i^2+41i+21}{4i^3+24i^2+41i+15} \\ &= \frac{a_ia_{i+2}}{2i+2}\cdot \left(1+\frac{6}{4i^3+24i^2+41i+15}\right) \\ &> \frac{a_ia_{i+2}}{2i+2}. \end{align*}$

So, for both odd and even index pairs, the strict inequality $a_ia_{i+2} < 2i+2$ follows from $a_{i+2}a_{i+4} \le 2i+6$ and we need only prove the inequalities $a_{2n-3}a_{2n-1} \le 4n-4$ and $a_{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 $a_{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:

$\begin{align*} a_{2n-1}a_{2n} &= 4n-1 \\ a_{2n-2}a_{2n} &= 4n-2 \\ a_{2n-2}a_{2n-1} &= 4n-3 \end{align*}$

multiplying any two and dividing by the third, we get:

$\begin{align*} a_{2n}^2 &= \frac{(4n-2)(4n-1)}{4n-3} \\ a_{2n-1}^2 &= \frac{(4n-3)(4n-1)}{4n-2} \\ a_{2n-2}^2 &= \frac{(4n-3)(4n-2)}{4n-1} \end{align*}$

from which,

$a_{2n-3}^2 = \frac{(4n-5)^2}{a_{2n-2}^2} = \frac{(4n-5)^2(4n-1)}{(4n-3)(4n-2)}$

With the squares of the last four terms in hand, we can now verify the only non-redundant inequality:

$\begin{align*} a_{2n-3}^2a_{2n-1}^2 &= \frac{(4n-5)^2}{a_{2n-2}^2}a_{2n-1}^2 \\ &= \left(\frac{(4n-5)(4n-1)}{4n-2}\right)^2 \\ &= \left(\frac{16n^2 -24n + 5}{4n-2}\right)^2 \\ &< \left(\frac{16n^2 -24n + 8}{4n-2}\right)^2 \\ &= (4n-4)^2. \end{align*}$

The inequality above follows because the numerator and denominator are both positive for $n > 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 $a_1' = M\cdot a_1$ , the sequence $a_i'$ will have the form:

$\begin{align*} a_{2i-1}' &= Ma_{2i-1} \\ a_{2i}' &= \frac{a_{2i}}{M} \end{align*}$

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>0$ , the same construction with $2n+2k$ terms, truncated to just the first $2n$ terms, yields a sequence $a'_i$ which also satisfies all the required conditions, but in this case $a'_{2n-2}a'{2n} < 4n-2$ .

We could have constructed this alternative solution directly, by replacing the right hand side in the equation $a_{2n-2}a_{2n} = 4n-2$ with any smaller value for which we still get $a_{2n-3}a_{2n-1} \le 4n-4$ .

In the modified construction, for some constant $M > 1$ , we have:

$\begin{align*} a_{2n}^2 &= \frac{1}{M}\cdot \frac{(4n-2)(4n-1)}{4n-3} \\ a_{2n-1}^2 &= M\cdot \frac{(4n-3)(4n-1)}{4n-2} \\ a_{2n-2}^2 &= \frac{1}{M}\cdot \frac{(4n-3)(4n-2)}{4n-1} \end{align*}$

and so:

$\begin{align*} a_{2n-3}^2a_{2n-1}^2 &= \frac{(4n-5)^2}{a_{2n-2}^2}a_{2n-1}^2 \\ &= M^2\left(\frac{(4n-5)(4n-1)}{4n-2}\right)^2 \\ &= M^2\left(\frac{16n^2 -24n + 5}{4n-2}\right)^2 \\ &= M^2\left(\frac{16n^2 -24n + 5}{16n^2 -24n + 8}\right)^2 \cdot \left(\frac{16n^2 -24n + 8}{4n-2}\right)^2 \\ &= M^2\left(\frac{16n^2 -24n + 5}{16n^2 -24n + 8}\right)^2 \cdot (4n-4)^2. \end{align*}$

which satisfies the required inequality provided:

$\begin{align*} M^2 &\le \frac{16n^2 -24n + 8}{16n^2 -24n + 5} \\ &= \frac{(4n-4)(4n-2)}{(4n-5)(4n-1)} = M_{\mathrm{max}}^2. \end{align*}$

The ratio $M_{\mathrm{max}}$ , between the largest and smallest possible value of $a_{2n-3}$ is in fact the ratio between the largest and smallest values of $a_1$ that yield a sequence that meets the conditions for at least $2n$ terms.

In the $n=2$ case, the equation for $a_{2n-3}$ gives: $a_1^2 = \frac{21}{10}$ . We will next consider what happens to $a_1^2$ , and the sequence of squares in general, as $n$ increases.

Let $A_{n,2i-1}, A_{n,2i}$ denote the $i^{\mathrm{th}}$ odd and even terms, respectively, of the unique sequence which satisfies our original equations and has $2n$ terms in total. Let $A_{n+1,2i-1}, A_{n+1,2i}$ be the odd and even terms of the solution with $2n+2$ terms. We already noted that there must exist a constant $M_n$ (that depends on $n$ , but not on $i$ ), such that:

$\begin{cases} A_{n+1,2i-1} = M_n\cdot A_{n,2i-1},& 1 \le i \le n \\ A_{n+1,2i} = \dfrac{A_{n,2i}}{M_n},& 1 \le i \le n \end{cases}$

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

$\begin{align*} (1/M_n)^2 &= \frac{A_{n+1,2n}^2}{A_{n,2n}^2} \\ &= \frac{(4n+1)(4n+2)}{4n+3} \cdot \frac{4n-3}{(4n-2)(4n-1)} \\ &= \frac{32n^3 - 14n - 3}{32n^3 - 14n + 3} \end{align*}$

Clearly $M_n > 1$ for all positive $n$ , and so for fixed $i$ , the odd index terms $A_{n,2i-1}$ strictly increase with $n$ , while the even index terms $A_{n,2i}$ decrease with $n$ .

Therefore, for $n \ge 2$ ,

$A_{n,1}^2 = \frac{21}{10} \prod_{k=2}^{n-1} M_k^2 = \frac{21}{10} \cdot \prod_{k=2}^{n-1} \frac{(n+\frac{3}{4})(n-\frac{1}{2})(n-\frac{1}{4})} {(n-\frac{3}{4})(n+\frac{1}{2})(n+\frac{1}{4})}$

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

$\begin{align*} A_{\omega,1}^2 &= \frac{21}{10} \cdot \lim_{n \to \infty} \prod_{k=2}^{n-1} \frac{(n+\frac{3}{4})(n-\frac{1}{2})(n-\frac{1}{4})} {(n-\frac{3}{4})(n+\frac{1}{2})(n+\frac{1}{4})} \\ &= \frac{21}{10} \cdot \lim_{n \to \infty} \left( \frac{\Gamma(\frac{5}{4}) \Gamma(\frac{5}{2}) \Gamma(\frac{9}{4})} {\Gamma(\frac{11}{4}) \Gamma(\frac{3}{2}) \Gamma(\frac{7}{4})}\cdot \frac{\Gamma(n+\frac{3}{4})\Gamma(n-\frac{1}{2})\Gamma(n-\frac{1}{4})} {\Gamma(n-\frac{3}{4})\Gamma(n+\frac{1}{2})\Gamma(n+\frac{1}{4})} \right) \\ &= \frac{1}{4} \cdot \frac{\Gamma^2(\frac{1}{4})}{\Gamma^2(\frac{3}{4})} \cdot \lim_{n \to \infty} \frac{\Gamma(n+\frac{3}{4})\Gamma(n-\frac{1}{2})\Gamma(n-\frac{1}{4})} {\Gamma(n-\frac{3}{4})\Gamma(n+\frac{1}{2})\Gamma(n+\frac{1}{4})} \\ &= \frac{1}{4} \cdot \frac{\Gamma^2(\frac{1}{4})}{\Gamma^2(\frac{3}{4})} \cdot 1 \quad \mbox{(Stirling's approximation)}\\ &= \frac{\Gamma^4(\frac{1}{4})}{8\pi^2} = \frac{\pi}{\mathrm{AGM}^2(\sqrt{2}, 1)} \approx 2.1884396152264766\ldots \end{align*}$

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

@@ Line 61: / Line 61: @@
 <center>
 <cmath>
-\frac{a_{j+2}}{a_j} \ge \frac{i+j+2}{i+j} > \frac{j+j+2}{j+j} = \frac{2j+2}{2j},
+\frac{a_{j+2}}{a_j} \ge \frac{i+j+2}{i+j} > \frac{j+j+2}{j+j} = \frac{2j+2}{2j} > (2j+3)/(2j+1) = \frac{a_{j+2}}{a_j},
 </cmath>
 </center>
-but the ratio of the <math>j^{\mathrm{th}}</math> term to the next term of the same
+so our assumption is impossible.
-parity is <math>(2j+3)/(2j+1) < (2j+2)/2j</math>, so our assumption is impossible.
 Therefore, we need only verify inequalities with an index difference of

Page

Toolbox

Search