Problem
COM-B1-M05-P020 Two Groups with Equal Sum
#20
★★★☆☆ Level 3 of 5
Prove that among \(10\) positive integers not exceeding \(100\), one can choose two different nonempty groups with the same sum.
Compare the number of nonempty subsets with the number of possible sums.
There are \(2^{10}-1=1023\) nonempty subsets. Any subset sum lies between \(1\) and \(1000\), so there are at most \(1000\) possible sums. By pigeonhole, two different nonempty groups have the same sum.
This does not yet guarantee disjoint groups, but shows the power of subset sums.