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 $A\le 8$ and $B\le 4$. (I. Gorodnin)
Problem
Source: 2019 Belarusian National Olympiad 11.3
Tags: combinatorics
01.09.2019 23:54
The answer is $S = \boxed{11.2}.$ It's clear that $S > 12$ do not work. To see that $11.2 < S \le 12$ do not work, simply take $14$ copies of $\frac{S}{14}.$ Now, let's show that $S = 11.2$ works. Firstly, observe that if two of our numbers sum to at most one, then we can just combine them. Indeed, this only makes our task more difficult, if anything. Therefore, assume WLOG that any two of our numbers sum to greater than $1.$ This immediately implies that there is at most one number which is $<\frac12$. This leads us to the following two cases. Case 1. $0 < r < \frac12$ is one of our numbers If $r \ge \frac15$, consider the following algorithm. Start by adding $r$ to $B$. Now, we simply keep adding numbers to $B$ until the total sum of the things in $B$ is at least $3.2$. It's clear that the sum in $B$ at this point is at most $4.2$, since it increases by at most one with each number we add. If the sum is actually at most $4$, we are done by just putting all the other numbers in $A$. Otherwise, kick out $r$, and put $r$ and the other numbers in $A$. Otherwise, we have $0 < r < \frac15.$ By our assumption that any two numbers sum to greater than one, all of the other numbers are strictly greater than $0.8$. Hence, just take four of them as group $B$ and the other numbers as group $A$ to finish. Case 2. All of our numbers are at least $\frac12$. If one of our numbers $r$ is in $\left[\frac12, \frac45\right]$, then we will employ a similar strategy. Start by throwing this number $r$ into $B$, and then simply add other numbers until the total exceeds $3.2$. If it's at most $4$, we are done by putting all other numbers in $A$. Otherwise, simply remove $r$ from $B$, and let $A$ be comprised of $r$ and all other numbers. Otherwise, all of our numbers are greater than $\frac45.$ We are again done by simply throwing four arbitrary numbers into $B$. As we've exhausted all cases, we've shown that $S = 11.2$ indeed works, and so our answer is $S = \boxed{11.2}$. $\square$