Maths Olympiad Prep

Library / /37 of 52

Combinatorics Difficulty 6.2 National olympiad Prove it Belarus

The sum of several (not necessary 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 sum of the numbers in each group not exceeding 7070.

Solution

Answer: S133S \le 133.

Clearly S140S \le 140. Suppose that S134S \ge 134 and let S=134+mS = 134 + m, where 0m60 \le m \le 6. Consider the next collection of numbers: one number equals 88, mm numbers equal 1010 and 14m14-m numbers equal 99 (the total sum equals 134+m134+m). At least eight of these 1515 numbers will be in the same group. But the sum of the smallest eight numbers is not less than 18+m9+(7m)10=78m721 \cdot 8 + m \cdot 9 + (7-m) \cdot 10 = 78 - m \ge 72 — a contradiction.

It remains to show that any collection of positive integers not exceeding 1010 with the sum S133S \le 133 can be partitioned into two groups as required. We will successive put numbers to the first group (in an arbitrary order), and at some moment the sum of all numbers of this group will satisfy the next two conditions: 1) 60<A7060 < A \le 70; and 2) A+a>70A + a > 70 for any remaining number aa. If A63A \ge 63, then SA70S - A \le 70 and we can form the second group from all remaining numbers.

Now consider the case A62A \le 62. Then A=62xA = 62 - x, where xx equals 00 or 11. For any remaining number aa the inequality A+a>70A + a > 70 takes the form a>8+xa > 8 + x, which is equivalent to a9+xa \ge 9 + x. If there are not more than seven numbers left, their sum does not exceed 7070 and we can form the second group from them. Otherwise the sum SAS - A of the remaining numbers is not less than 8(9+x)=72+8x8 \cdot (9 + x) = 72 + 8x, therefore
S=(SA)+A72+8x+(62x)=134+7x>133, S = (S - A) + A \ge 72 + 8x + (62 - x) = 134 + 7x > 133,
which contradicts to S133S \le 133. Thus, the required partition is constructed in all cases.

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.