Pigeonhole Principle

A rigorous treatment of ordinary and generalized pigeonhole arguments, with sharp bounds and applications.

If more objects enter fewer boxes, at least one box receives more than one object. Five labelled objects are assigned to four labelled boxes. The final box contains two objects, providing the forced collision guaranteed by the pigeonhole principle.

Precise definition

The pigeonhole principle says that placing more than $n$ objects into $n$ boxes forces some box to contain at least two objects. The generalized form says that distributing $N$ objects among $k$ boxes forces some box to contain at least $\lceil N/k\rceil$ objects.

Notation and mathematical language

Objects and boxes are modelling choices, not literal items. The ceiling $\lceil x\rceil$ is the least integer at least $x$. A proof often assumes every box has at most $r-1$ objects; then the total is at most $k(r-1)$, so any $N>k(r-1)$ forces a box with at least $r$.

Conceptual picture

The principle converts an average into a guaranteed local concentration. If the average load is $N/k$, at least one box cannot lie below its ceiling. It proves existence but usually does not identify which box or construct the repeated pair.

Fully worked example

Interpretation and application

Pigeonhole reasoning appears in hashing collisions, repeated remainders, scheduling, data compression, and graph degree arguments. A hash table with fewer slots than possible keys must permit collisions; the principle proves necessity but does not evaluate a collision-resolution method's performance.