## Sunday, February 26, 2006

### Legend of Max. Topic: Inequalities. Level: Olympiad.

Problem: (1999 USAMO - #4) Let $a_{1}, a_{2}, \ldots, a_{n}$ ($n > 3$) be real numbers such that

$a_{1} + a_{2} + \cdots + a_{n} \geq n \qquad$ and $\qquad a_{1}^{2} + a_{2}^{2} + \cdots + a_{n}^{2} \geq n^{2}$.

Prove that $\max(a_{1}, a_{2}, \ldots, a_{n}) \geq 2$.

Solution: To simply things, let $x_i = 2-a_i$. We wish to show that there exists an $x_i \le 0$.

Our conditions become

$(2-x_1)+(2-x_2)+\cdots+(2-x_n) \ge n \Rightarrow x_1+x_2+\cdots+x_n \le n$.

$(2-x_1)^2+(2-x_2^2)+\cdots+(2-x_n)^2 \ge n^2$.

Assume for the sake of contradiction that $x_i > 0$ for all $i$ and let $x_1+x_2+\cdots+x_n = k \le n$. We have

$(2-x_1)^2+(2-x_2)^2+\cdots+(2-x_n^2) = (x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n)+4n \ge n^2$, or

$(x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) \ge n^2-4n$.

But we have $x_1^2+x_2^2+\cdots+x_n^2 < (x_1+x_2+\cdots+x_n)^2 = k^2$, so

$(x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) < k^2-4k$.

However, since $n \ge k$ and $n \ge 4$, we have $n^2-4n \ge k^2-4k$ (looking at the parabola it is easy to see; $x^2-4x$ has zeros at $x = 0, 4$). Therefore

$(x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) < k^2-4k \le n^2-4n$.

$(x_1^2+x_2^2+\cdots+x_n^2) - 4(x_1+x_2+\cdots+x_n) \ge n^2-4n$,

so that gives us a contradiction. Hence our assumption must be false and there exists an $x_i \le 0 \Rightarrow a_i \ge 2$ as desired. QED.

--------------------

Comment: This wasn't a particularly difficult inequality, but it has some key ideas. Using all parts of the question is important (in this case $n > 3$ is actually relevant). Another note is that this didn't really require any of the classical inequalities, just algebraic manipulation. Lastly, the crucial step was setting converting the real $a_i$ to positive $x_i$ which makes things a whole lot nicer.

--------------------

Practice Problem: Go take the 2006 Mock AIME 5 below.