Maths Olympiad Prep

Library / /35 of 52

Combinatorics Difficulty 6.1 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 it is always possible to partition these numbers into two groups with sums not greater than 99.

Solution

Answer: maxS=17.1\max S = 17.1.

First we will show that if S>17.1S > 17.1, the required partition can be impossible. Indeed, let S=17.1+19ϵS = 17.1 + 19\epsilon, ϵ>0\epsilon > 0. Suppose that we are given 1919 numbers equal to 0.9+ϵ0.9 + \epsilon. It is evident that for any partition some of the groups will contain at least 1010 of these numbers. But then the sum of the numbers in this group is not less than 9+10ϵ>99 + 10\epsilon > 9, which is forbidden.

Now let S17.1S \le 17.1. We will prove that the required partition exists for any such SS, which will imply maxS=17.1\max S = 17.1. Consider all sums S1S_1 of (some of) the given numbers such that 8<S198 < S_1 \le 9, and let AA be the maximal sum (if such sums don't exist, there is nothing to prove). For any remaining number aa holds A+a>9A + a > 9. Consider the next two cases:

Case 1: A8.1A \ge 8.1. The sum of all remaining numbers doesn't exceed 99 and we can make the required partition into two groups with the sums AA and SAS - A.

Case 2: A<8.1A < 8.1. Let A=8.1xA = 8.1 - x, 0<x<0.10 < x < 0.1. If there are not more than nine numbers left, then their sum doesn't exceed 99 and we can form the second group from them. Suppose that there are at least ten numbers left. Since for any remaining number aa holds A+a>9A + a > 9 and A=8.1xA = 8.1 - x, we have a>0.9+xa > 0.9 + x. Hence SA10(0.9+x)=9+10xS - A \ge 10 \cdot (0.9 + x) = 9 + 10x. But then SA+9+10x=8.1x+9+10x=17.1+9x>17.1S \ge A + 9 + 10x = 8.1 - x + 9 + 10x = 17.1 + 9x > 17.1 - a contradiction.

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.