The Pigeonhole Principle

If you have more pigeons than pigeonholes, at least one hole must contain more than one pigeon. This seemingly trivial observation — formalised by Dirichlet in 1834 — is one of the most powerful tools in combinatorics. It proves that in any group of 367 people, at least two share a birthday. It proves that in London, at least two people have exactly the same number of hairs on their head. It underlies key results in number theory, graph theory, and computer science. Simple in statement, astonishing in reach.