Difference between revisions of "1999 USAMO Problems/Problem 4"

Revision as of 15:29, 28 September 2014

Problem

Let $a_{1}, a_{2}, \dots, a_{n}$ ( $n > 3$ ) be real numbers such that $a_{1} + a_{2} + \cdots + a_{n} \geq n \qquad \mbox{and} \qquad a_{1}^{2} + a_{2}^{2} + \cdots + a_{n}^{2} \geq n^{2}.$ Prove that $\max(a_{1}, a_{2}, \dots, a_{n}) \geq 2$ .

Hint

Remember that the problem said real numbers, which can be negative!

Solution

First, suppose all the $a_i$ are positive. Then $\max(a_1, \dotsc, a_n) \ge \sqrt{\frac{a_1^2 + \dotsb + a_n^2}{n}} \ge \sqrt{n} \ge 2 .$ Suppose, on the other hand, that without loss of generality, $a_1 \ge a_2 \ge \dotsb \ge a_k \ge 0 > a_{k+1} \ge \dotsb \ge a_n,$ with $1\le k <n$ . If $a_1 >2$ we are done, so suppose that $a_1 \le2$ . Then $\sum_{i=1}^k a_i \le 2k$ , so $\sum_{i=k+1}^n -a_i \le 2k-n .$ Since $-a_i$ is a positive real for all $k+1 \le i \le n$ , it follows that

\[\sum_{i=k+1}^n a_i^2 \le \left( \sum_{i=k+1}^n} -a_i \right)^2 \le (2k-n)^2 .\] (Error compiling LaTeX. Unknown error_msg)

Then $\begin{align*} \max(a_1, \dotsc, a_n)^2 &\ge \sum_{i=1}^k a_i^2 /k \\ &\ge \left( n^2 - \sum_{i=k+1}^n a_i^2 \right)/k \\ &\ge \frac{n^2 - (2k-n)^2}{k} = 4(n-k). \end{align*}$ Since $k<n$ , $4(n-k) > 4$ . It follows that $\max(a_1, \dotsc, a_n) \ge \sqrt{4} = 2$ , as desired. $\blacksquare$

Solution 2

Assume the contrary and suppose each $a_i$ is less than 2.

Without loss of generality let $a_1 \le a_2 \le a_3 \le ... \le a_n < 2$ , and let $k$ be the largest integer such that $a_k \le 0$ and $0 \le a_{k+1}$ if it exists, or 0 if all the $a_i$ are non-negative. If $k = 0$ , then (as $n \ge 4$ ) $\sum_{i=1}^n a_i^2 < \sum_{i=1}^n 4 = 4n \le n^2$ , a contradiction. Hence, assume $n \ge k \ge 1$ . Then $\sum_{i=1}^k a_i \ge n - \sum_{i=k+1}^n a_i > n - 2(n-k) = 2k - n.$ Because $a_i \le 0$ for $i \le k$ , both sides of the inequality are non-positive, so squaring flips the sign. But we also know that $a_i a_j \ge 0$ for $i, j \le k$ , so $\sum_{i=1}^k a_i^2 \le \left(\sum_{i=1}^k a_i \right)^2 < (2k - n)^2 = 4k^2 - 4kn + n^2,$ which results in $\sum_{i=1}^n a_i^2 = \sum_{i=1}^k a_i^2 + \sum_{i=k+1}^n a_i^2 < 4k^2 - 4kn + n^2 + 4(n-k) = n^2 - 4(k-1)(n-k) \le n^2,$ a contradiction to our given condition. The proof is complete.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

@@ Line 38: / Line 38: @@
 <cmath>\sum_{i=1}^k a_i \ge n - \sum_{i=k+1}^n a_i > n - 2(n-k) = 2k - n.</cmath>
 Because <math>a_i \le 0</math> for <math>i \le k</math>, both sides of the inequality are non-positive, so squaring flips the sign. But we also know that <math>a_i a_j \ge 0</math> for <math>i, j \le k</math>, so
-<cmath>\sum_{i=0}^k a_i^2 \le \left(\sum_{i=0}^k a_i \right)^2 < (2k - n)^2 = 4k^2 - 4kn + n^2,</cmath>
+<cmath>\sum_{i=1}^k a_i^2 \le \left(\sum_{i=1}^k a_i \right)^2 < (2k - n)^2 = 4k^2 - 4kn + n^2,</cmath>
 which results in
-<cmath>\sum_{i=0}^n a_i^2 = \sum_{i=0}^k a_i^2 + \sum_{i=k+1}^n a_i^2 < 4k^2 - 4kn + n^2 + 4(n-k) = n^2 - 4(k-1)(n-k) \le n^2,</cmath>
+<cmath>\sum_{i=1}^n a_i^2 = \sum_{i=1}^k a_i^2 + \sum_{i=k+1}^n a_i^2 < 4k^2 - 4kn + n^2 + 4(n-k) = n^2 - 4(k-1)(n-k) \le n^2,</cmath>
 a contradiction to our given condition. The proof is complete.

1999 USAMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search