Pigeonhole Principle

The pigeonhole principle is deceptively simple yet devastatingly powerful: if you put more objects than containers, some container must hold at least two objects. Formal statement: If $n$ items are placed into $m$ containers and $n > m$, then at least one container holds at least $\lceil n/m \rceil$ items. Intuition: Imagine stuffing 11 pigeons into 10 pigeonholes. No matter how cleverly you distribute them, one hole must contain at least 2 pigeons. The principle seems obvious, but its power lies in choosing the right "pigeons" and "holes." Concrete example: Among any 13 people, at least 2 share a birth month. Here the "pigeons" are 13 people and the "holes" are 12 months. Since $13 > 12$, at least one month has $\geq 2$ people. A subtler example: In any sequence of $n^2 + 1$ distinct real numbers, there exists either an increasing subsequence of length $n+1$ or a decreasing subsequence of length $n+1$. (Assign each element the pair (length of longest increasing subsequence ending here, length of longest decreasing subsequence ending here). There are at most $n \times n = n^2$ distinct pairs, but $n^2+1$ elements — so two share the same pair, which forces the conclusion.) When to use: Existence proofs in interviews — "prove that something must happen" without constructing it. Common in number theory, sequences, and scheduling problems. This is a fundamental technique. The trick is always identifying what are the pigeons and what are the holes.