The sum of several (not necessarily different) real numbers from $[0,1]$ doesn't exceed $S$. Find the maximum value of $S$ such that it is always possible to partition these numbers into two groups with sums not greater than $9$. (I. Gorodnin)
Problem
Source: 2019 Belarusian National Olympiad 10.4
Tags: combinatorics
01.09.2019 11:35
The answer is $S=171/10$. (A) No larger value of $S$ works. Consider the instance with $19$ copies of the number $0.9+\varepsilon$ for some small (positive) $\varepsilon$ very close to $0$. Then one of the two groups must contain at least $10$ copies, so that its sum is $9+10\varepsilon>9$. (B) The value $S=171/10$ works. Consider such a set of $n$ real numbers $x_1>x_2>\cdots>x_n$. Form two groups: Start with two empty groups. Work through the $x_i$ in order of increasing index, and always put the number into the group with currently smaller sum. Suppose that you get stuck at some moment, while trying to assign $x_k$. (1) At this moment, you have assigned $x_1,\ldots,x_{k-1}$ to the two groups, and the sum of all these assigned numbers is at most $S-x_k$. (2) Hence the smaller sum of the two groups is at most $(S-x_k)/2$, and since you are stuck this means that $x_k+(S-x_k)/2>9$. This inequality is equivalent to $x_k>9/10$. (3) Suppose that $k\ge19$. Then $x_1>x_2>\cdots>x_k>9/10$ implies that the sum of all numbers is strictly above $19\cdot9/10=S$. This contradiction implies $k\le 18$. (4) Now since $k\le18$, one of the two groups (at the moment BEFORE assigning $x_k$) does contain at most $8$ numbers. Since all numbers are from $[0,1]$, this means that the sum of that group is at most $8$, and hence $x_k$ can added to it without exceeding the bound $9$. That's the final contradiction.