Let a1,a2,…,an (n>3) be real numbers such that a1+a2+⋯+an≥nanda21+a22+⋯+a2n≥n2. Prove that max.
Problem
Source:
Tags: USAMO, inequalities, function, inequalities proposed
21.01.2004 03:38
21.01.2004 17:44
27.06.2004 05:26
Ravi B's sum :Sigma: = :Sigma: (x<sub>i</sub> - 2)(x<sub>i</sub> - 2 + n) made the problem look so simple.
27.06.2004 23:16
The Kalva solution uses something called the smoothing principle, which ends up being fairly important in inequalities... Here was an idea I had when working on this problem... Proof is by contradiction --- For each i, define x_i = 2 - a_i. Our assumption is that all the x<sub>i</sub> are non-negative. Then \sum a_i \ge n \Rightarrow \sum x_i \le n \sum a_i^2 \ge n^2 \Rightarrow 4n - 4 \sum x_i + \sum x_i^2 \ge n^2 \Rightarrow n^2 - 4n \le \sum x_i^2 - 4\sum x_i < (\sum x_i)^2 - 4\sum x_i (*) \le n^2 - 4n (**). (*) Follows since all the x<sub>i</sub> are nonnegative. (**) Follows since n :ge: 4 and \Sum x_i \le n. Contradiction. Assuming my proof is right... I have found quite a few problems that can be solved using this neat substitution of assigning variable quantities to the distance each variable is from where you want it to be ... its a cool trick, when it works.
28.06.2004 05:11
Nice solution! I think you are right that working with positive variables is easier than working with variables less than say 2. That way, inequalities like :Sigma: x<sub>i</sub><sup>2</sup> < (:Sigma: x<sub>i</sub>)<sup>2</sup> become more apparent.
28.06.2004 07:46
Yet another way! I'll first need a (relatively simple) lemma: Given non-negative reals p_1,\ldots,p_t with \sum p_k^2=q, we have \sum p_k\ge\sqrt{q}. Proof: The proof is rather simple. We have \left(\sum p_k\right)^2 = p_1^2+\cdots+p_t^2+(\text{other non-negative terms})\ge q, which establishes the result. The equality case, though easy to find, is unnecessary for this proof. \blacksquare Let x_1, ... , x_n be a set of reals each less than 2, with \sum x_k^2\ge n^2. They can't all be positive, since then we would have \sum x_k^2 < \sum 2^2 = 4n \le n^2, a contradiction. Thus, we can divide them into two classes: the positive ones a_1, \ldots, a_m (each less than 2) and the non-positive ones b_1,\ldots,b_{n-m} where m is an integer less than n. Notice that \displaystyle 4m+\sum_{k=1}^{n-m}b_k^2 > \sum_{k=1}^{m} a_k^2 + \sum_{k=1}^{n-m}b_k^2 = \sum_{k=1}^n x_k^2 \ge n^2, i.e. \displaystyle \sum_{k=1}^{n-m} b_k^2 \ge n^2-4m. We can now apply the lemma to -b_1,\ldots, -b_{n-m} to find that \displaystyle \sum_{k=1}^{n-m}(-b_k) \ge \sqrt{\sum_{k=1}^{n-m}b_k^2} = \sqrt{n^2-4m}. Finally, \displaystyle \sum_{k=1}^n x_k = \sum_{k=1}^m a_k - \sum_{k=1}^{n-m}b_k < 2m -\sqrt{n^2-4m}. Now, the function f(m)=2m-\sqrt{n^2-4m} is an increasing function of m, and so it is maximized when m is maximized, i.e. when m=n-1. Thus, f(m)\le f(n-1) = 2n-2-\sqrt{n^2-4n+4} = n. Therefore, we see that \sum x_k < 2m -\sqrt{n^2-4m} \le n, and so both inequalities in the problem cannot be simultaneously satisfied if all the x_i are less than 2.
28.06.2004 07:54
Nukular wrote: Assuming my proof is right... I have found quite a few problems that can be solved... Can you share the problems? Thanks!
29.06.2004 01:48
The one im thinking of in particular was on the first MOP test in Blue this year... I should probably wait until after mop ends to post it...
12.03.2006 06:07
Another solution, which is pretty fast (drilling for USAMO): The proof is easy for n=4, so I won't put it up. For n>4, assume all a_i<2. Then sum(a_i)<2n. (1) Assume sum(a_i)>=m (We know m is at least n.) Then 2sum(a_i)+2sum{j not equal to i}(a_i*a_j)= sum[a_i(2+sum{j not equal to i}(a_j))]>= sum(a_i*m)>= m^2. (2) By (1) and (2), 2sum{j not equal to i}(a_i*a_j)>=m^2-4n, so sum(a_i^2)+2sum{j not equal to i}(a_i*a_j)=[sum(a_i)]^2>=m^2 + n^2-4n. But then sum(a_i)>=sqrt(m^2 + n^2 - 4n), which is greater than m for all n>4. We may then repeat the algebra done after (2), substituting sqrt(m^2 + n^2 - 4n) for m. But then sum(a_i) has no lower bound. Contradiction. Daniel Litt
12.03.2009 04:19
I'm confused, why can't all the numbers be 1?
12.03.2009 04:25
Then the sum-of-squares condition would not be satisfied.
12.03.2009 04:41
O, wow, my bad.
19.03.2009 19:07
19.03.2009 20:01
How do you show that n a_n^2 \ge n^2?
19.03.2009 21:08
The second equation... \sum a_i^2 \ge n^2
19.03.2009 21:48
How do you know that a_n^2 \ge a_i^2?
12.04.2009 00:11
This is tricky for a #4, IMHO. Say we have i negative terms and n-i nonnegative terms among a_{1},a_{2},\ldots,a_{n}. WLOG, let the negative ones be a_{1},a_{2},\ldots,a_{i}. Assume that a_{1},\ldots,a_{n}<2. Note that i\ge1, or else a_{x}^{2}<4 for all x (as 0\le a_{x}<2), giving a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}<4n\le n^{2} for n\ge4, contradiction. Also, we obviously have n\ge i. We have a_{1}+a_{2}+\cdots+a_{n}\ge n, and a_{i+1}+a_{i+2}+\cdots+a_{n}<2(n-i) by assumption. Thus, a_{1}+a_{2}+\cdots+a_{i}>n-2i. Note that a_{1}^{2}+a_{2}^{2}+\cdots+a_{i}^{2}<(a_{1}+\cdots+a_{i})^{2} since a_{x}<0 for all 1\le x\le i; this is clear upon expanding the RHS. Now, a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2} =(a_{1}+\cdots+a_{i})^{2}+4(n-i) <(n-2i)^{2}+4(n-i) <n^{2}-4(i-1)(n-i) \le n^{2}, contradiction.
30.04.2009 03:37
Hmmm, maybe my method seems super easy and stuff... I don't see anything WRONG, though. There probably is something. Can you guys review this? We proceed by contradiction. Assume that all of the terms are less than 2. We then have a_1^2 + a_2^2 + \dots + a_n^2 < 4n because the maximum value for each term is 4. However, we are given a_1^2 + a_2^2 + \dots + a_n^2 \geq n^2, and this is not always true with the previous inequality. Therefore, not all of the terms are less than 2, i.e. the highest term must be greater than or equal to two. Right?
30.04.2009 03:45
The terms can be negative. Some can be less than -2, and thus your first inequality doesn't hold. We can even have an equality case: n-1 copies of 2 and one of -n+2. I'm pretty sure I got this problem right when I took it live. Of course, that was ten years ago and I don't remember details.
27.07.2010 18:26
03.08.2010 04:32
Quote: If we have a_1 = a_2 = \dots = a_{n-1} = 2, a_n = 2-n, we have a_1^2 + \dots + a_n^2 = 4(n-1) + (2-n)^2 = n^2, which is the maximum sum we can get from the numbers. While this statement is actually true, the justification for this is not strong enough. For instance, you could have a_1 < -2; in this case, a_1^2 > 4.
04.04.2012 04:14
I am not quite sure of what smoothing is. Is this solution right because it seems very easy because the problem seems very weak.
23.12.2014 00:25
Excuse me if I am wrong, but is this trivialized by n-1-EV?
17.02.2015 18:50
It suffices to show that a_i<2\rightarrow \sum a_i^2<n^2. If all are positive, the sum of squares is <4n\le n^2 and we are done. If there are two negatives x,y, then (x+y)^2+0^2 yields a larger sum of squares. So WLOG there is one negative. Taking this negative a and a positive b<2, then (a-2+b)^2+2^2 yields a larger sum of squares (it is equivalent to (2-a)(2-b)>0. So the absolute max is n-1 copies of 2 and 1 copy of -n+2, which yields a sum of squares of n^2. However equality can't be achieved so we are done.
31.08.2017 07:35
Is this rigorous enough: Suppose on the contrary that max(a_1, a_2, ..., a_n) < 2. Let us partition the set of {a_i} into {b_i} of nonnegative integers and {c_i} of negative integers. First, we prove that {c_i} is nonempty. If it was empty, then \sum a_i^2 < 4n \leq n^2, contradiction. WLOG, a_1 \geq a_2 \geq \dots \geq a_n. We now perform a series of steps; each increasing one of s_1 = a_1 + a_2 + \dots + a_n and s_2 = a_1^2 + a_2^2 + \dots + a_n^2 \geq n^2 without breaking any bounds, until we get a maximal sum that leads to a contradiction. This works, since a maximal sum that didn't break any of our bounds contradicting the max a_i \geq 2 statement implies that none of the smaller {a_i} series work, since each can be "smoothed out" to each other. Now for our steps: \textbf{Step 1}: We can increase b_i to 2-\epsilon for some infinitesimally small \epsilon. This increases s_1 and s_2. \textbf{Step 2}: Since \bigg(\sum c_i\bigg)^2 \geq \sum c_i^2, we can collect all the c_i terms into a_n without changing s_1 and increasing s_2. This adds zeros to b_i. \textbf{Step 3}: Repeat step 1 for the zero's. We now have n-1 2-\epsilon's and a large negative number. We can now perform the proof by contradiction: From the first inequality we have: \sum a_i \geq n \rightarrow (n-1) \cdot (2 - \epsilon) + a_n \geq n \rightarrow n-2 > -a_n \rightarrow a_n > 2-nFrom this, we also have: \sum a_i^2 < 4 \cdot (n-1) + a_n^2 < 4\cdot (n-1) + (n-2)^2 = n^2Which contradicts the second inequality. Hence, max(a_1, a_2, \dots a_n) \geq 2.
02.09.2017 05:44
Similar to above, but arrives at finish slightly differently. Assume for sake of contradiction that \max(a_i)<2. WLOG let a_1\leq a_2 \leq \cdots \leq a_n. Furthermore denote s=a_1+a_2+\cdots+a_n. We have that n\leq s<2n. If a_1\geq 0, we have that. 4n>a_1^2+a_2^2+...+a_n^2\geq n^2 \implies 4n>n^2\implies n<4But n>3 and n is an integer, so we have a contradiction, and we are done. Hence, we can assume a_1<0. Now observe that x^2 is convex, hence we can unsmooth by replacing a_1 and a_i with a_1+a_i-2 and 2, for all i\in{2,3\cdots n}. We end up with \sum_{k=1}^{n} a_k^2<(s-2(n-1))^2+(n-1)\cdot 2^2=a_1^2+4(n-1)Note that a_1+2(n-1)\leq n \implies a_1\geq 2-n. Since a_1<0, we have that a_1^2\leq (2-n)^2=(n-2)^2. Thus \sum_{k=1}^{n} a_k^2=a_1^2+4(n-1)\leq (n-2)^2+4(n-1)=n^2which is a contradiction, so we win. \square
02.09.2017 05:59
If anyone had a solution with n-1 EV to share, that would be great.
06.09.2017 17:31
22.09.2019 20:03
I am sleepy now, so I am not sure, but what's wrong with the below solution? After seeing all these solutions, I am feeling like I have made a silly her, bit can't find it WLOG, Assume a_n\geq a_{n-1}\geq\ldots\geq a_1 Then, na_n\geq a_1+a_2+\ldots+a_n\geq n\implies a_n\geq 1>0. And, na_n^2\geq a_1^2+a_2^2+\ldots+a_n^2\geq n^2\implies na_n^2\geq n^2. As a_n greater than 0, a_n\geq\sqrt{n}. As n\geq 4, a_n\geq 2 BTW, this is also a PUTNAM question iirc
23.09.2019 18:53
Umm, can someone plz check th solution, I am really in a confused state
27.09.2019 04:19
Math-wiz wrote: I Then, na_n\geq a_1+a_2+\ldots+a_n\geq n\implies a_n\geq 1>0. And, na_n^2\geq a_1^2+a_2^2+\ldots+a_n^2\geq n^2\implies na_n^2\geq n^2. Try 2,2,2,2,-3 . Then na_n^2< a_1^2+a_2^2+\ldots+a_n^2=n^2 .
27.09.2019 04:22
tetrahedr0n wrote: 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. This is a beautiful problem
Attachments:

27.09.2019 04:27
tetrahedr0n wrote: 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.
27.09.2019 04:51
mihaig wrote: Math-wiz wrote: I Then, na_n\geq a_1+a_2+\ldots+a_n\geq n\implies a_n\geq 1>0. And, na_n^2\geq a_1^2+a_2^2+\ldots+a_n^2\geq n^2\implies na_n^2\geq n^2. Try 2,2,2,2,-3 . Then na_n^2< a_1^2+a_2^2+\ldots+a_n^2=n^2 . Ohh! Yes, got your point
16.04.2021 08:50
Does this work?
24.08.2021 04:10
For the sake of contradiction assume that \max{(a_i)}<2. Suppose we have no negative reals, then 4n>a_{1}^{2} + a_{2}^{2} + \ldots + a_{n}^{2} \geq n^{2}\implies 4>n,which contradicts n\geq 4. Let i<n denote the number of positive reals, a_1,\ldots,a_i. The rest, a_{i+1},\ldots,a_n, are negative. Thus, a_{i+1}+\ldots+a_n> n-2i\Longleftrightarrow 2i-n>\vert a_{i+1}\vert +\ldots+ \vert a_{n}\vert and a_{i+1}^2+\ldots+a_n^2> n^2-4i.Thus, (2i-n)^2>(\vert a_{i+1}\vert +\ldots+ \vert a_{n}\vert )^2\geq a_{i+1}^2+\ldots+a_n^2> n^2-4i.This is equivalent to 4i^2-4ni>-4i\Longleftrightarrow i>n-1.This arrive at a contradiction. We conclude that \max{(a_i)}\geq 2.
20.08.2023 05:25
This problem dies fairly easily to smoothing. Suppose for the sake of contradiction that such a sequence existed with all a_i < 2. The point is that we can actually make most of the variables 2-\varepsilon and one of the variables -n + 2 + (n-1) \varepsilon by fixing some a_i, and pushing a_i and a_j apart for each j \neq i such that a_j = 2 -\varepsilon. Under this process the value of \sum a_i^2 increases while \sum a_i stays constant. So it suffices to show the problem cannot work in that case. Fortunately, this is obvious, as \sum_{i=1}^{n} a_i^2 = (n-2)^2 - 2n(n-1) \varepsilon + (n-1)^2 \varepsilon^2 + 4(n-1) - 2(n-1) \varepsilon = n^2 - (n-1)^2 \varepsilon < n^2.
25.08.2023 17:27
Solved with otis walkthrough. Suppose there existed a sequence with a_i < 2 for all i, and the rest of the problem conditions were true. If everything was positive, then the sum of the squares is less than n\cdot (2^2) = 4n \le n^2, contradiction. Now we assume there is at least one negative term. For any two i\ne j with a_i and a_j both negative, we can replace a_i and a_i with a_i + a_j and 0 and the conditions still must hold true. For any i with a_i \ge 0, we can replace a_i with 2 - \epsilon for some arbitrarily small positive constant \epsilon. Now we can assume there is only one negative term, and the rest of the terms are equal to 2 - \epsilon. Let the negative term be equal to -d. We have n \le \sum a_i \le 2(n-1) - d, so d\le n - 2. Hence \sum a_i^2 < 2^2 \cdot (n-1) + (n-2)^2 = n^2, contradiction. Therefore, there exists a term in the sequence that is at least 2.
11.03.2024 00:59
Assume for contradiction b_i = 2-a_i > 0 for each i. Let S = \sum b_i. Note that S = \sum b_i = \sum (2-a_i) = 2n - \sum a_i\le 2n - n = n.We also have n^2\le \sum a_i^2 = \sum (2-b_i)^2 = 4n - 4S + \sum b_i^2\implies \sum b_i^2\ge n^2 - 4n + 4S.But note that \sum b_i^2 < S^2 as all b_i are positive. Thus we have S^2 > n^2 - 4n + 4S\implies (S-2)^2 > (n-2)^2\implies S < 4-n \text{ or }S > n.We have 4-n \le 0 so we cannot have S < 4-n. We have also shown that S\le n, so S > n is impossible as well. Thus we have arrived at a contradiction.
30.07.2024 16:42
For the sake of contradiction, suppose that a_i <2 for all i, and the problem conditions still hold. If all a_i are nonnegative, then \sum a_i^2 < 4n \le n^2, a contradiction. Hence, at least one term is negative. Then, if there are two terms a_i = -x and a_j = -y that are negative, we may replace them with a_i = -(x+y) and a_j=0 and the conditions still hold true. This means we have reduced the sequence to only containing one negative number, a_n = k. Then, we may smooth out all the nonnegative terms to 2, making the inequalities strict. We know that n \le \sum a_i < 2(n-1)-k \implies k < n-2. Then, \sum a_i^2 < 4(n-1)+(n-2)^2 = n^2, a contradiction. \square