The sum of several (not necessarily different) positive integers not exceeding $10$ is equal to $S$. Find all possible values of $S$ such that these numbers can always be partitioned into two groups with the sum of the numbers in each group not exceeding $70$. (I. Voronovich)
Problem
Source: 2019 Belarusian National Olympiad 9.4
Tags: Sets, partition, combinatorics
04.09.2019 04:53
The answer is all $S \le 133$. First of all, notice that if $S$ does not satisfy the property in question, then neither does $S+1$ because we can simply add a $1$ to our set of numbers. Therefore, it suffices simply to show that $133$ has the property in question while $134$ does not. To see that $134$ does not, consider the set of numbers $\{9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8\}.$ This doesn't work because one of the groups must contain at least $8$ numbers, and the sum of those $8$ numbers would necessarily be at least $9 \cdot 7 + 8 = 71.$ Now, let's show that $133$ works. It suffices to show that for any set $T$ of positive integers not exceeding $10$, there exists a subset $A \subseteq T$ with the sum of its elements in the interval $[63, 70].$ Case 1. There is an element $t$ of $T$ which is in $[2, 8].$ We will construct the subset $A$ as follows. Start by adding $t$ to $A$. Now, continually add random elements of $T$ to $A$ until the sum is at least $63$. If the sum of the elements in $T$ is in $[63, 70]$, then we win. Otherwise, it is in $[71, 72]$ and so we can just delete $t$ from $A$. Case 2. All elements of $T$ are either $1, 9,$ or $10$. If there are at least two ones, then we can simply combine them into a two and apply logic as in Case $1$. Hence, suppose that there is at most one $1$ in $T$. Then, since the sum of the other elements is at least $132$, we know that there are at least $7$ elements which are either $9$ or $10$. The sum of these elements would necessarily lie in the interval $[63, 70]$, and so the problem is solved. $\square$