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 "1999 USAMO Problems/Problem 4"

m
m
 
(9 intermediate revisions by 4 users not shown)
Line 10: Line 10:
  
 
== Solution ==
 
== Solution ==
 +
=== Solution 1 ===
 
First, suppose all the <math>a_i</math> are positive.  Then
 
First, suppose all the <math>a_i</math> are positive.  Then
 
<cmath> \max(a_1, \dotsc, a_n) \ge \sqrt{\frac{a_1^2 +
 
<cmath> \max(a_1, \dotsc, a_n) \ge \sqrt{\frac{a_1^2 +
Line 19: Line 20:
 
<cmath> \sum_{i=k+1}^n -a_i \le 2k-n . </cmath>
 
<cmath> \sum_{i=k+1}^n -a_i \le 2k-n . </cmath>
 
Since <math>-a_i</math> is a positive real for all <math>k+1 \le i \le n</math>, it follows that
 
Since <math>-a_i</math> is a positive real for all <math>k+1 \le i \le n</math>, it follows that
−
<cmath> \sum_{i=k+1}^n a_i^2 \le \left( \sum_{i=k+1}^n} -a_i \right)^2 \le (2k-n)^2 . </cmath>
+
<cmath> \sum_{i=k+1}^n a_i^2 \le \left( \sum_{i=k+1}^n-a_i \right)^2 \le (2k-n)^2 . </cmath>
 
Then
 
Then
 
<cmath> \begin{align*}
 
<cmath> \begin{align*}
Line 27: Line 28:
 
\end{align*} </cmath>
 
\end{align*} </cmath>
 
Since <math>k<n</math>, <math>4(n-k) > 4</math>.  It follows that <math>\max(a_1, \dotsc, a_n) \ge \sqrt{4} = 2</math>, as desired.  <math>\blacksquare</math>
 
Since <math>k<n</math>, <math>4(n-k) > 4</math>.  It follows that <math>\max(a_1, \dotsc, a_n) \ge \sqrt{4} = 2</math>, as desired.  <math>\blacksquare</math>
 +
 +
===Solution 2===
 +
Assume the contrary and suppose each <math>a_i</math> is less than 2.
 +
 +
Without loss of generality let <math>a_1 \le a_2 \le a_3 \le ... \le a_n < 2</math>, and let <math>k</math> be the largest integer such that <math>a_k \le 0</math> and <math>0 \le a_{k+1}</math> if it exists, or 0 if all the <math>a_i</math> are non-negative. If <math>k = 0</math>, then (as <math>n \ge 4</math>) <math>\sum_{i=1}^n a_i^2 < \sum_{i=1}^n 4 = 4n \le n^2</math>, a contradiction. Hence, assume <math>n \ge k \ge 1</math>. Then
 +
<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=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=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.
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
−
== Resources ==
+
== See Also ==
−
* [[1999 USAMO Problems]]
+
{{USAMO newbox|year=1999|num-b=3|num-a=5}}
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=63591#63591 Discussion on AoPS/MathLinks]
 
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 +
[[Category:Olympiad Inequality Problems]]
 +
{{MAA Notice}}

Latest revision as of 08:47, 20 July 2016

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

Solution

Solution 1

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 .\] 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.

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1999_USAMO_Problems/Problem_4&oldid=79637"