Maths Olympiad Prep

Library / /39 of 52

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 A8A \le 8 and B4B \le 4.

Solution

Answer: maxS=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 S11.2S \le 11.2. We will prove that the required partition exists for any such SS, which will imply maxS=11.2\max S = 11.2. Consider all sums S1S_1 of (some of) the given numbers such that 7<S187 < 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=SAB = S - A satisfies B4B \le 4. Indeed, for A7.2A \ge 7.2 it is clear. Suppose A<7.2A < 7.2, then A=7.2xA = 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 B4B \le 4. Thus the required partition exists.

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.