Pigeonhole Principle Reference Cheat Sheet

Key Facts

• Basic pigeonhole principle: if $N>k$, then placing $N$ objects into $k$ boxes guarantees that at least one box contains at least $2$ objects.
• Generalized pigeonhole principle: placing $N$ objects into $k$ boxes guarantees at least one box contains at least $\left\lceil \frac{N}{k} \right\rceil$ objects.
• To guarantee at least $m$ objects in one box among $k$ boxes, it is enough to have $N=k(m-1)+1$ objects.
• If $N$ objects are split among $k$ boxes and no box has more than $m-1$ objects, then the total number of objects is at most $k(m-1)$.
• In a proof, the pigeons are the objects being distributed, and the pigeonholes are the categories, remainders, labels, or possible outcomes.
• When sorting integers by remainders modulo $k$, the only possible pigeonholes are $0,1,2,\ldots,k-1$, so there are exactly $k$ pigeonholes.
• The ceiling value $\left\lceil \frac{N}{k} \right\rceil$ means the smallest integer greater than or equal to $\frac{N}{k}$.
• A pigeonhole conclusion is guaranteed by counting, but it usually does not identify which specific object or box has the repeated property.

Vocabulary

Pigeonhole Principle

A counting rule stating that if more objects than categories are used, at least one category must contain at least two objects.

Pigeon

A pigeon is the object being assigned, such as a person, number, card, or data point.

Pigeonhole

A pigeonhole is the category or container an object is assigned to, such as a birthday month, remainder, or color.

Generalized Pigeonhole Principle

A rule stating that $N$ objects placed into $k$ boxes force some box to contain at least $\left\lceil \frac{N}{k} \right\rceil$ objects.

Ceiling Function

The ceiling function $\left\lceil x \right\rceil$ gives the smallest integer greater than or equal to $x$.

Guarantee

A guarantee is a conclusion that must be true in every possible arrangement, not just in a likely arrangement.