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.

Conditions and key results

The boxes must cover every object, and each object must be assigned according to a well-defined rule. For the simple two-in-one conclusion, $N>k$ is essential. For a target of at least $r$ in one box, the sharp forcing threshold is $k(r-1)+1$.

A reliable strategy

1. Choose the objects and define boxes so that the desired coincidence means sharing a box.
2. Count objects $N$ and boxes $k$ accurately, including boundary categories.
3. Apply $\lceil N/k\rceil$ or compare $N$ with $k(r-1)$ for the desired load $r$.
4. State the guaranteed existence conclusion without claiming a particular box unless further information identifies it.

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.

Common mistakes

Verification and reasonableness

• Try the extremal arrangement with at most $r-1$ objects per box and compute its capacity.
• Check sharpness: at $k(r-1)$ objects, can every box still have only $r-1$?
• Verify units—people, residues, dates, or keys—match the object and box counts.

Practice

1. How many people guarantee two share a weekday of birth?
2. What load is guaranteed when 41 files are placed in 10 folders?
3. How many integers guarantee three share the same remainder modulo 5?

Further deduction

Remainders supply natural boxes. Among any $n+1$ integers, two have the same remainder modulo $n$; subtracting them produces a multiple of $n$. The integers are objects and the $n$ possible residues $0,1,\ldots,n-1$ are boxes. This conclusion remains true even when the integers repeat, but if distinctness or a nonzero difference is required, the original problem must provide enough information to exclude choosing the same occurrence as both objects.

Related topics

• Counting
• Graphs and Networks
• Proof by Contradiction