Tuymaada Yakut Olympiad, Day 2 Problem 4

The sum of several non-negative numbers is not greater than 200, while the sum of their squares is not less than 2500. Prove that among them there are four numbers whose sum is not less than 50.

Solution

The problem does not change if we delete all the zeroes, so we can assume that all numbers are positive. Let $a_1 \geq a_2 \geq \cdots \geq a_n$ be those numbers, and suppose all sums of four are less than 50. So now we have three conditions:

1. $a_1 + a_2 + a_3 + a_4 < 50$.


2. $a_1 + \cdots + a_n \leq 200$.


3. $a_1^2 + \cdots + a_n^2 \geq 2500$.

Extend the sequence by adding numbers $a_{n+1}, \cdots, a_m$ where $a_{n+1} = a_{n+2} = \cdots = a_{m-1} \geq a_m$ such that $a_1 + \cdots + a_m = 200$. This addition will not disrupt condition one and three, so we now have:

1. $a_1 + a_2 + a_3 + a_4 < 50$.


2. $a_1 + \cdots + a_m = 200$.


3. $a_1^2 + \cdots + a_m^2 \geq 2500$.

Let us now define a transfer operation as follows. Given $a,b$ with $a \geq b$, we replace them with $a+ \epsilon,b - \epsilon$ with $\epsilon > 0$. One can easily verify that a transfer on two numbers will not change their linear sums, but will only increase their sum of squares, because

$(a+\epsilon)^2 + (b-\epsilon)^2 > a^2+b^2 \iff \epsilon(a-b)+\epsilon^2 > 0$

So now we can apply a series of transfers, beginning with $(a_1,a_m)$, followed by $(a_1, a_{m-1}), (a_1, a_{m-2}), ... $ and so on. In each step, we apply as much transfer as possible, possibly reducing the smaller number to zero in the process. We stop when $a_1 + a_2 + a_3 + a_4$ reach $50$, at which points our three conditions become:

1. $a_1 + a_2 + a_3 + a_4 = 50$.


2. $a_1 + \cdots + a_m = 200$.


3. $a_1^2 + \cdots + a_m^2 > 2500$.

(Note that the sign for condition 3 changed because equality is no longer possible. In order to reach condition 1, we must do at least one non-trivial transfer and that transfer strictly increase the sum of squares).

Now we apply another series of transfers similar to above. We start with the last numbers and apply the transfer, this time not to $a_1$ but to $a_5$. Our goal is such that $a_4 = a_5 = \cdots = a_{k-1} \geq a_k > a_{k+1} = \cdots = a_m = 0$ for some $k$. One can achieve this configuration by transferring from the smallest number each time, and raising the largest number that's less than $a_4$ to be up to par with $a_4$. After we are done, our sequence looks like this: $a, b, c, d, d, \cdots, d, e$.

Lastly, we transfer $(c-d)$ from $c$ to $a$, and $(b-d)$ from $b$ to $a$ to arrive at configuration $50-3d,d,d,d,\cdots,d,e$ where there are $N$ $d$'s. Our conditions can be rewritten to be:

1. $(50-3d)+d+d+d = 50$. This condition is self-satisfactory and will be removed from our consideration.
   


2. $(50-3d) + Nd + e = 200$.
   


3. $(50-3d)^2 + Nd^2 + e^2 > 2500$

But because $50-3d \geq d$, then $d \leq 12.5$, and thus $12d \leq 150$. Then

$(50-3d)^2 + Nd^2 + e^2 = (50-3d)^2 + e^2 + d(200-e-(50-3d))$


$= 2500 - 150d + 12d^2 + e^2 - ed$

$= 2500 + d(12d-150) + e(e-d) \leq 2500$

which contradicts condition 3.