Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Problem and solution. Displayed equations still look sub-optimal (not centered) and don't work right without a paragraph break... :-()
(Work-around lack of automatic centering of displayed equations...)
Line 13: Line 13:
 
<math>(a_{2i-i},a_{2i}), 1\le i \le 1005</math>, the product is at most
 
<math>(a_{2i-i},a_{2i}), 1\le i \le 1005</math>, the product is at most
 
<math>(2i-1) + 2i = 4i - 1</math>, and so the product of all the pairs is at most:
 
<math>(2i-1) + 2i = 4i - 1</math>, and so the product of all the pairs is at most:
−
 
+
<center>
 
<cmath>
 
<cmath>
 
\prod_{i=1}^{1005}(4i-1).
 
\prod_{i=1}^{1005}(4i-1).
 
</cmath>
 
</cmath>
−
 
+
</center>
 
If we can demonstrate a sequence in which for <math>1 \le i \le 1005</math> the product
 
If we can demonstrate a sequence in which for <math>1 \le i \le 1005</math> the product
 
<math>a_{2i-1}a_{2i} = 4i-1</math>, and all the inequalities are satisfied, the above
 
<math>a_{2i-1}a_{2i} = 4i-1</math>, and all the inequalities are satisfied, the above
Line 24: Line 24:
 
We will construct sequences of an arbitrary large even length <math>2n \ge 4</math>,
 
We will construct sequences of an arbitrary large even length <math>2n \ge 4</math>,
 
in which:
 
in which:
−
 
+
<center>
 
<cmath>
 
<cmath>
 
\begin{cases}
 
\begin{cases}
Line 32: Line 32:
 
\end{cases}
 
\end{cases}
 
</cmath>
 
</cmath>
−
 
+
</center>
 
Given <math>a_1</math>, from the equations <math>a_ia_{i+1} = 2i+1,\; 1\le i\le n</math>,
 
Given <math>a_1</math>, from the equations <math>a_ia_{i+1} = 2i+1,\; 1\le i\le n</math>,
 
we obtain the whole sequence recursively:
 
we obtain the whole sequence recursively:
 
<math>a_1 = a_1,\; a_2 = 3/a_1,\; a_3 = 5/a_2 = 5a_1/3,\;
 
<math>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,</math> and in general:
 
a_4 = 7/a_3 = (3\cdot 7)/(5a_1) \ldots,</math> and in general:
−
 
+
<center>
 
<cmath>
 
<cmath>
 
a_{i+2} = a_i \cdot (2i+3)/(2i+1).
 
a_{i+2} = a_i \cdot (2i+3)/(2i+1).
 
</cmath>
 
</cmath>
−
 
+
</center>
 
The same equations <math>a_ia_{i+1} = 2i+1</math> can be used to compute the
 
The same equations <math>a_ia_{i+1} = 2i+1</math> can be used to compute the
 
whole sequence from any other known term.
 
whole sequence from any other known term.
Line 47: Line 47:
 
For <math>i < j</math>, <math>a_ia_j \le i+j \implies a_ia_{j+2} < i+j+2</math>.
 
For <math>i < j</math>, <math>a_ia_j \le i+j \implies a_ia_{j+2} < i+j+2</math>.
 
If it were otherwise, we would have for some <math>i < j</math>:
 
If it were otherwise, we would have for some <math>i < j</math>:
−
 
+
<center>
 
<cmath>
 
<cmath>
 
a_{j+2}/a_j \ge (i+j+2)/(i+j) > (j+j+2)/(j+j) = (2j+2)/2j,
 
a_{j+2}/a_j \ge (i+j+2)/(i+j) > (j+j+2)/(j+j) = (2j+2)/2j,
 
</cmath>
 
</cmath>
−
 
+
</center>
 
but the ratio of the <math>j^{\mathrm{th}}</math> term to the next term of the same
 
but the ratio of the <math>j^{\mathrm{th}}</math> term to the next term of the same
 
parity is <math>(2j+3)/(2j+1) < (2j+2)/2j</math>, so our assumption is impossible.
 
parity is <math>(2j+3)/(2j+1) < (2j+2)/2j</math>, so our assumption is impossible.
Line 64: Line 64:
 
We now compare <math>a_ia_{i+2}/(2i+2)</math> with <math>a_{i+2}a_{i+4}/(2i+6)</math>. By our
 
We now compare <math>a_ia_{i+2}/(2i+2)</math> with <math>a_{i+2}a_{i+4}/(2i+6)</math>. By our
 
recurrence relations:
 
recurrence relations:
−
 
+
<center>
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 85: Line 85:
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
−
 
+
</center>
 
So, for both odd and even index pairs, the strict inequality
 
So, for both odd and even index pairs, the strict inequality
 
<math>a_ia_{i+2} < 2i+2</math> follows from <math>a_{i+2}a_{i+4} \le 2i+6</math>
 
<math>a_ia_{i+2} < 2i+2</math> follows from <math>a_{i+2}a_{i+4} \le 2i+6</math>
Line 95: Line 95:
 
we can solve for the last three terms (or equivalently their squares)
 
we can solve for the last three terms (or equivalently their squares)
 
and thus compute the whole sequence. From the equations:
 
and thus compute the whole sequence. From the equations:
−
 
+
<center>
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 103: Line 103:
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
−
 
+
</center>
 
multiplying any two and dividing by the third, we get:
 
multiplying any two and dividing by the third, we get:
−
 
+
<center>
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 113: Line 113:
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
−
 
+
</center>
 
from which,
 
from which,
−
 
+
<center>
 
<cmath>
 
<cmath>
 
a_{2n-3}^2 = (4n-5)^2/a_{2n-2}^2 = \frac{(4n-5)^2(4n-1)}{(4n-3)(4n-2)}
 
a_{2n-3}^2 = (4n-5)^2/a_{2n-2}^2 = \frac{(4n-5)^2(4n-1)}{(4n-3)(4n-2)}
 
</cmath>
 
</cmath>
−
 
+
</center>
 
With the squares of the last four terms in hand, we can now verify
 
With the squares of the last four terms in hand, we can now verify
 
the only non-redundant inequality:
 
the only non-redundant inequality:
−
 
+
<center>
 
<cmath>
 
<cmath>
 
\begin{align*}
 
\begin{align*}
Line 133: Line 133:
 
\end{align*}
 
\end{align*}
 
</cmath>
 
</cmath>
−
 
+
</center>
 
This completes the construction and the proof of all the inequalities,
 
This completes the construction and the proof of all the inequalities,
 
which miraculously reduced to just one inequality for the last pair
 
which miraculously reduced to just one inequality for the last pair
 
of odd indices.
 
of odd indices.

Revision as of 15:01, 5 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-i},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 $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 arbitrary 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 n$, 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 in general:

\[a_{i+2} = a_i \cdot (2i+3)/(2i+1).\]

The same equations $a_ia_{i+1} = 2i+1$ can be used to compute the whole sequence from any other known term.

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$:

\[a_{j+2}/a_j \ge (i+j+2)/(i+j) > (j+j+2)/(j+j) = (2j+2)/2j,\]

but the ratio of the $j^{\mathrm{th}}$ term to the next term of the same parity is $(2j+3)/(2j+1) < (2j+2)/2j$, 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 = (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*}

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_USAMO_Problems/Problem_3&oldid=34445"