Let $S$ be a real number. It is known that however we choose several numbers from the interval $(0, 1]$ with sum equal to $S$, these numbers can be separated into two subsets with the following property: The sum of the numbers in one of the subsets doesn’t exceed 1 and the sum of the numbers in the other subset doesn’t exceed 5. Find the greatest possible value of $S$.
Problem
Source: IX International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade
Tags: algebra
Pinko
22.09.2018 19:55
It is obvious that $S$ should be $\leq$ 6 as the sum of the subsets shouldn't exceed 6.
Let S be a number in the interval (5.5, 6]. As the conditions must be satisfied for any numbers from the interval (0, 1], then it is enough to show an example which contradicts with the conditions for S ∈ (5.5; 6]. Let us have 11 numbers $a_1, a_2, . . . , a_{11}$ for which $a_i=0.5+b_i$ for $\forall i=1,2,...11$, $b_1 \neq b_2 \neq ... \neq b_{11}$ and $b_1+b_2+...+b_{11}=S-5.5$ where $b_i$ are positive. Then in the subset that shouldn't exceed 1 we can put only one of the numbers $a_i$ as the sum of any two is greater than 1, but that leave us with 10 numbers greater than 0.5 that should have a sum that doesn't exceed 5 which is a contradiction. So S ∉ (5.5, 6].
Now we will prove that $S=5.5$ satisfies all conditions. If the number of the numbers is less than 12, then there will be a number that is greater or equal to 0.5 and it is enough to put it in the first subset and we will be left out with numbers which sum won't exceed 5. If the number of the numbers is greater than 11 and all numbers are less than 0.5 (otherwise we can do the same as in the first case) then there are some numbers which sum is greater than 0.5 but smaller than 1. Suppose that this isn't true. Then if we take the sum of those numbers that is closest to 0.5, but still less than it, we see that adding any other number has to make the sum greater than 1, but that means that number added must be greater than 0.5. Hence a contradiction. So there are numbers which sum is in the interval [0.5, 1] and it is enough for us to put them in the first subset and the others in the second subset in order to satisfy the conditions. Thus $S=5.5$ is the largest value.