pigeonhole principle

If $f:X\to Y$ and $|X|>|Y|$, then there are elements $x_1,x_2\in X$ such that $x_1\ne x_2$ and $f(x_1)=f(x_2)$.

Intuition

If there are more pigeons than pigeonholes, then there is at least one pigeonhole with more than one pigeon in it.

The pigeonhole principle is useful for proving statements about matching elements of a set to another smaller set. The difficult part is to recognize sets (sometimes inventively) even when they are not explicitly mentioned.