Let $m,n \in \mathbb{N}$ and $n>m$. The Pigeonhole Principle states that if $n$ items are put into $m$ containers, then there exists a container that has at least $\left \lceil{ \frac{n}{m} }\right \rceil $ items.
Problem (IMO, 1972)
Prove that from a set of ten distinct two-digit numbers, it is possible to select two disjoint subsets whose elements have the same sum.
Solution
Note that the total number of subsets is equal $2^{10}=1024$. Obviously, none of the subsets can be equal to the original set and neither can be empty, therefore there are $1022$ possible subsets to choose from. Since the sum of the elements of any such subset is at most
$$ 90+91+92+93+94+95+96+97+98+99 < 99 \cdot 10 = 990$$
Train for Math Olympiads
Learn morethen there are less than $990$ different sums.
Since
$$\left \lceil{ \frac{1022}{990} }\right \rceil = 2$$
by the Pigeonhole Principle, there are two distinct subsets $A$ and $B$, whose elements have the same sum.
Let us put $C=A \cap B$. Now we can take $A-C$ and $B-C$ to be the needed subsets.
