Summary of pigeonhole techniques

Basic. $n+1$ pigeons in $n$ holes $\Rightarrow$ some hole has $\ge2$ pigeons.

Generalized. $n$ pigeons in $k$ holes $\Rightarrow$ some hole has $\ge\lceil n/k\rceil$ pigeons.

Key applications.
- Divisibility: among $n+1$ integers, two have same residue mod $n$.
- Consecutive integers: among $n+1$ from $\{1,\ldots,2n\}$, two are consecutive.
- Divisibility chains: among $n+1$ from $\{1,\ldots,2n\}$, one divides another.
- Subset sums: some block has sum divisible by $n$.
- Geometry: $5$ points in unit square $\Rightarrow$ two within $\sqrt2/2$.
- Graph theory: any group has two people with the same number of friends; any graph has two vertices of the same degree.
- Ramsey: any $6$ people contain $3$ mutual friends or $3$ mutual strangers.

Conclusion. Pigeonhole is one of the simplest yet most powerful combinatorial tools.