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 2 of 4: Apply the pigeonhole principle

Previous step Next step

In plain words

This is the classical pigeonhole step: put more objects into fewer boxes than there are objects, and some box gets at least two.

1024 > 946 \implies \exists\, A\neq B,\ \text{sum}(A)=\text{sum}(B)

Detailed analysis

Since $1024$ subsets ('pigeons') map to only $946$ possible sums ('pigeonholes'), by the pigeonhole principle at least two distinct subsets $A\neq B$ of $S$ must have the same sum: $\text{sum}(A)=\text{sum}(B)$ .