Maths Olympiad Prep

Library / /41 of 52

Combinatorics Difficulty 6.4 National olympiad Prove it Belarus

The sum of several (not necessarily different) positive integers not exceeding 1010 is equal to SS.
Find all possible values of SS such that these numbers can always be partitioned into two groups with the sums of the numbers in each group not exceeding 8080.

Solution

Answer: S152S \le 152.
Clearly S160S \le 160. Suppose that S153S \ge 153 and let S=153+mS = 153 + m, where 0m70 \le m \le 7. Consider the next collection: mm numbers equal 1010 and 17m17 - m numbers equal 99 (the total sum equals 153+m153 + m). At least nine of these 1717 numbers will be in the same group. But the sum of nine smallest numbers is at least 8181 — a contradiction.

It remains to prove that any collection of positive integers not exceeding 1010 with the sum S152S \le 152 can be partitioned as required. We will successive put numbers to the first group (in an arbitrary order), and at some moment the sum AA of all numbers of this group will satisfy two conditions: 1) 70<A8070 < A \le 80; and 2) A+a>80A + a > 80 for any remaining number aa. If A72A \ge 72, then SA80S - A \le 80 and we can form the second group from all remaining numbers. If A<72A < 72, then A=71A = 71 and the inequality A+a>80A + a > 80 implies that all remaining numbers equal 1010. There are not more than eight numbers left (otherwise S71+910=161S \ge 71 + 9 \cdot 10 = 161, since S152S \le 152). Hence we can form the second group from them.

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.