Ravi B's sum :Sigma: = :Sigma: (x_i - 2)(x_i - 2 + n) made the problem look so simple.

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

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_i² < (:Sigma: x_i)² become more apparent.

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.

Nukular wrote: Assuming my proof is right... I have found quite a few problems that can be solved... Can you share the problems? Thanks!

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

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

I'm confused, why can't all the numbers be 1?

Then the sum-of-squares condition would not be satisfied.

O, wow, my bad.

How do you show that $n a_n^2 \ge n^2$?

The second equation...$\sum a_i^2 \ge n^2$

How do you know that $a_n^2 \ge a_i^2$?

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.

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?

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.

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

I am not quite sure of what smoothing is. Is this solution right because it seems very easy because the problem seems very weak.

Excuse me if I am wrong, but is this trivialized by $n-1$-EV?

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.

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-n$$ From this, we also have: $$\sum a_i^2 < 4 \cdot (n-1) + a_n^2 < 4\cdot (n-1) + (n-2)^2 = n^2$$ Which contradicts the second inequality. Hence, $max(a_1, a_2, \dots a_n) \geq 2$.

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<4$$ But $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^2$$ which is a contradiction, so we win. $\square$

If anyone had a solution with $n-1$ EV to share, that would be great.

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

Umm, can someone plz check th solution, I am really in a confused state

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

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

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

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

Does this work?

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

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

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

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.

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$