Pigeonhole principle

If $k$ is a positive integer and $k+1$ or more objects are placed into $k$ boxes, then there is at least one box containing two or more of the objects.

Corollary - A function $f$ from a set with $k+1$ or more elements to a set with $k$ elements is not one-to-one.

The Generalized Pogeonhole Principle

If $n$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil n/k\rceil$ objects.