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. Proposed by A. Khabrov
Problem
Source: Tuymaada 2009, Junior League, Second Day, Problem 4
Tags: floor function, inequalities, function, algebra unsolved, algebra
26.07.2009 00:12
Denote the given numbers $ a_1 \geq a_2 \geq \cdots \geq a_n \geq 0$, where $ n$ may be taken as large as wanted, by just appending zeroes. Denote $ \sigma = \sum_{i=1}^n a_i$, so $ \sigma \leq 200$ and $ \sum_{i=1}^n a_i^2 \geq 2500$, and denote $ s = a_1 + a_2 + a_3 + a_4$. Take $ k = \left \lfloor \frac {\sigma - a_1 - a_2 - a_3} {a_4} \right \rfloor$ if $ a_4 \neq 0$, and $ k = 1$ otherwise. Then $ \sigma = a_1 + a_2 + a_3 + ka_4 + \varepsilon a_4$, for some $ 0 \leq \varepsilon < 1$. The solution comes in two steps. Step 1. Build a decreasing sequence $ b_1 = a_1 = a$, $ b_2 = a_2 = b$, $ b_3 = a_3 = c$, $ b_i = a_4 = d$ for $ 4 \leq i \leq k+3$, $ b_{k+4} = \varepsilon a_4 = \varepsilon d$, $ b_j = 0$ for $ k+5 \leq j \leq n$. Now, the sequence $ (b_1, b_2, b_3, b_4, \ldots, b_n)$ dominates (in the sense of $ \textsc{Karamata}$'s inequality) the sequence $ (a_1, a_2, a_3, a_4, \ldots, a_n)$, since $ \sum_{i=1}^{\ell} b_i \geq \sum_{i=1}^{\ell} a_i$ for $ 1 \leq \ell \leq n-1$, and $ \sum_{i=1}^{n} b_i = \sum_{i=1}^{n} a_i = \sigma$. As $ f(x) = x^2$ is a convex function, $ \textsc{Karamata}$ yields $ \sum_{i=1}^n b_i^2 \geq \sum_{i=1}^n a_i^2 \geq 2500$ (this result can be obtained also in more elementary ways). Step 2. But $ \sum_{i=1}^n b_i^2 = a^2 + b^2 + c^2 + kd^2 + \varepsilon^2d^2$ = $ \sum a^2 +d(\sigma - \sum a) - \varepsilon d^2(1-\varepsilon) \leq \sum a^2 + d(200 - \sum a)$. Take now $ a = d+\alpha$, $ b = d+\beta$, $ c = d+\gamma$, with $ \alpha, \beta, \gamma \geq 0$. Combining all these yields $ d \geq \frac {2500 - \sum \alpha^2} {200 + \sum \alpha}$. Therefore $ s -50 = 4d + \sum \alpha - 50 \geq 4 \cdot \frac {2500 - \sum \alpha^2} {200 + \sum \alpha} + \sum \alpha - 50$ = $ \frac {3\sum \alpha(50-\alpha) + 2\sum \alpha\beta} {200 + \sum \alpha} \geq (50-s)\frac{3\sum \alpha} {200 + \sum \alpha}$, hence $ s \geq 50$. Remark. Similarly one can get that $ a_1 \geq 12.5$, $ a_1 + a_2 \geq 25$, and $ a_1 + a_2 + a_3 \geq 37.5$, all realized e.g. when $ a_i = 12.5$ for $ 1 \leq i \leq 16$. However, one only has $ \sum_{i=1}^{\ell} a_i \geq 50$ for $ \ell \geq 5$, realized e.g. when $ a_1 = 50$ and $ a_i = 0$ for $ i \geq 2$.
28.06.2010 06:46
This is my 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$. Every transfer operation does not change our three conditions above. 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. Again, these final transfers still do not change our three conditions, which can now be written as: 1. $(50-3d)+d+d+d = 50$. 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.