Problem 1

Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.

Step 1 of 4: Count subsets versus possible sums

Previous step Next step

In plain words

There are far more ways to pick a subset of the ten numbers than there are possible totals those subsets could add up to, so some totals must be repeated — the seed of a pigeonhole argument.

2^{10}=1024\text{ subsets, sums lie in }[0,945]

Detailed analysis

Let $S=\{a_1,\dots,a_{10}\}$ be the ten distinct two-digit numbers ( $10\le a_i\le 99$ ). The set $S$ has exactly $2^{10}=1024$ subsets (including the empty set). Every subset's sum is a nonnegative integer, and the largest possible sum is at most $90+91+\cdots+99=945$ (the sum of the ten largest two-digit numbers), so every subset sum lies in $\{0,1,\dots,945\}$ , a set of only $946$ possible values.