Problem
COM-B1-M05-P021 Two Disjoint Groups
#21
★★★★☆ Level 4 of 5
Prove that among any \(10\) positive integers not exceeding \(99\), one can choose two nonempty disjoint groups with the same sum.
First find two different groups with equal sum, then remove common elements.
There are \(1023\) nonempty subsets. Their sums lie from \(1\) to \(990\), at most \(990\) possible sums. Thus two different nonempty subsets have equal sum. Remove their common elements. The remaining parts still have equal sums; they are not both empty, otherwise the original subsets were equal. Hence we get two nonempty disjoint groups with equal sum.
Strong subset-sum pigeonhole version.