Winkler Puzzle 2: Subsets of 1-100

Here’s another Peter Winkler puzzle:

Prove that any set of 10 integers between 1 and 100 has two disjoint non-empty subsets with the same sum

Here’s a hint:

Show hint

Use the pigeonhole principle

And the solution:

Show solution

The largest sum any 10 integers less than or equal 100 could have is 950 (=5*190). Therefore, there are at most 950 distinct sums in the subset.

There are 1023 distinct subsets of a 10-element set, so two of these subsets must have the same sum. If these subsets happen to overlap, you can discard the common elements; since you have discarded the same elements from both subsets, they will still have the same sum.

2025/05/22