Maths Olympiad Prep

Library / /46 of 50

Combinatorics Difficulty 6.2 National olympiad Prove it Belarus

The sum of several positive numbers from (0,1](0, 1] is equal to SS. It is known that one with the guarantee can divide all given numbers into two groups such that the sum of numbers in the first group does not exceed 11 and the sum of numbers in the second group does not exceed 55.
Find the maximum possible value of SS.

Solution

Answer: 5.55.5.

We first show that S5.5S \le 5.5 (obviously, S6S \le 6). Suppose that S>5.5S > 5.5. Then we may write S=5.5+19xS = 5.5 + 19x, where 0<x1380 < x \le \frac{1}{38}. It can occur that we have 1111 numbers, 1010 of which are equal to 0.5+2x0.5 + 2x and the last one is equal to 0.5x0.5 - x. It is clear that it is impossible to divide such numbers into two groups as required in the problem conditions.

Now prove that any S5.5S \le 5.5 satisfies the problem conditions. There is nothing to prove if S5S \le 5. So we may assume that 5<S5.55 < S \le 5.5. Then among the given numbers there are several numbers with the sum a<5a < 5 and some number tt such that a+t5a + t \ge 5. Denote by bb the sum of all remaining numbers, a+t+b=S5.5a + t + b = S \le 5.5.

We have b=S(a+t)0.5b = S - (a + t) \le 0.5.

If a4.5a \ge 4.5 then t+b1t + b \le 1, so we can include in the first group all numbers with sum aa, and to the second group include all remaining numbers with sum t+bt + b.

Finally, if a<4.5a < 4.5 then St=a+b<4.5+0.5=5S - t = a + b < 4.5 + 0.5 = 5, hence we can include tt in the first group and all other numbers in the second group.

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.