Maths Olympiad Prep

Library / Belarusian Mathematical Olympiad /133 of 208

Belarusian Mathematical Olympiad

Combinatorics Difficulty 6.3 National Olympiad Prove it Belarus

The sum of several (not necessarily different) real numbers from [0,1][0, 1] does not exceed SS.
Find the maximal value of SS such that these numbers can always be partitioned into two groups with sums A≤8A \le 8 and B≤4B \le 4.

Solution

Answer: max⁡S=11.2\max S = 11.2.

First we will show that if S>11.2S > 11.2, the required partition can be impossible. Indeed, let S=11.2+14ϵS = 11.2 + 14\epsilon, ϵ>0\epsilon > 0. Suppose that we are given 14 numbers equal 0.8+ϵ0.8 + \epsilon. The sum of any ten of these numbers exceeds 88 and the sum of any five of them is greater than 44. Hence the group with sum AA contains at most 9 numbers and the group with sum BB contains at most 4 numbers. Thus, the required partition is impossible.

Now let S≤11.2S \le 11.2. We will prove that the required partition exists for any such SS, which will imply max⁡S=11.2\max S = 11.2. Consider all sums S1S_1 of (some of) the given numbers such that 7<S1≤87 < S_1 \le 8, and let AA be the maximal sum (if such sums don't exist, there is nothing to prove). We will show that the sum of the remaining numbers B=S−AB = S - A satisfies B≤4B \le 4. Indeed, for A≥7.2A \ge 7.2 it is clear. Suppose A<7.2A < 7.2, then A=7.2−xA = 7.2 - x, 0<x<0.20 < x < 0.2. From the maximality of AA it follows that for any remaining number bb holds A+b>8A + b > 8, i.e. b>0.8+xb > 0.8 + x. Since A+5⋅(0.8+x)=11.2+4x>SA + 5 \cdot (0.8 + x) = 11.2 + 4x > S, there are at most four numbers left. And each number doesn't exceed 11, so B≤4B \le 4. Thus the required partition exists.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.