Browse · MathNet
Print69th Belarusian Mathematical Olympiad
Belarus counting and probability
Problem
The sum of several (not necessarily different) real numbers from does not exceed . Find the maximal value of such that these numbers can always be partitioned into two groups with sums and .
Solution
Answer: .
First we will show that if , the required partition can be impossible. Indeed, let , . Suppose that we are given 14 numbers equal . The sum of any ten of these numbers exceeds and the sum of any five of them is greater than . Hence the group with sum contains at most 9 numbers and the group with sum contains at most 4 numbers. Thus, the required partition is impossible.
Now let . We will prove that the required partition exists for any such , which will imply . Consider all sums of (some of) the given numbers such that , and let 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 satisfies . Indeed, for it is clear. Suppose , then , . From the maximality of it follows that for any remaining number holds , i.e. . Since , there are at most four numbers left. And each number doesn't exceed , so . Thus the required partition exists.
First we will show that if , the required partition can be impossible. Indeed, let , . Suppose that we are given 14 numbers equal . The sum of any ten of these numbers exceeds and the sum of any five of them is greater than . Hence the group with sum contains at most 9 numbers and the group with sum contains at most 4 numbers. Thus, the required partition is impossible.
Now let . We will prove that the required partition exists for any such , which will imply . Consider all sums of (some of) the given numbers such that , and let 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 satisfies . Indeed, for it is clear. Suppose , then , . From the maximality of it follows that for any remaining number holds , i.e. . Since , there are at most four numbers left. And each number doesn't exceed , so . Thus the required partition exists.
Final answer
11.2
Techniques
Coloring schemes, extremal argumentsLinear and quadratic inequalities