Someone may freely choose ten numbers. You promise that, hidden among all their possible subsets, you will find two separate groups with exactly the same total.
The Chosen Ten
Riddle statement
A person chooses ten distinct integers from 1 to 100.
You make the following promise:
“Whatever ten numbers are chosen, I will be able to select some of them and separate them into two nonempty groups with no number in common, such that the two groups have exactly the same sum.”
Can you always keep that promise?
Show solution
Solution
Ten numbers have:
2¹⁰ = 1024 subsets.
The smallest possible subset sum is 0, from the empty set. The largest cannot exceed the sum of the ten largest integers from 1 to 100:
91 + 92 + ··· + 100 = 955.
Every subset sum is therefore an integer from 0 through 955, giving only 956 possible values.
Since there are 1024 subsets but only 956 possible sums, the pigeonhole principle guarantees that two distinct subsets, call them A and B, have the same sum.
The two subsets may share some numbers. Remove every common element from both. Their sums remain equal because the same amount is subtracted from each side, and the resulting groups are disjoint.
Neither resulting group can be empty. If the group coming from A were empty, then A would be a subset of B. Because A and B are distinct, B would contain at least one additional positive integer, making its sum strictly greater than the sum of A—a contradiction. The same argument applies with A and B reversed.
Thus there are always two nonempty, disjoint groups with exactly the same sum.