The Pigeonhole Principle

Take 13 people at a party. Must two of them share a birth month? This is a concrete instance of a deceptively simple idea. If you distribute enough objects into few enough containers, some container must receive more than one object. The Pigeonhole Principle turns this everyday observation into a precise combinatorial tool. Its power lies in the gap between how obvious it sounds and how sharp its conclusions are. The principle matters because it proves existence without constructing anything. It never tells you which pigeonhole is crowded, only that one must be. This non-constructive flavor makes it indispensable across combinatorics, number theory, analysis, and computer science. Whenever a counting mismatch between a domain and codomain is unavoidable, the pigeonhole principle converts that mismatch into a guaranteed collision, coincidence, or repetition. The big picture is that the principle is really a statement about Functions between finite sets. A function $f: N \to K$ with $|N| > |K|$ cannot be injective. Some two inputs must share an output. Once you see it this way, applications multiply. Sequences must repeat a residue mod $n$ . Subsets must share a sum. Points must fall close together in a partitioned region. The principle is a single sentence, but its instantiations range widely. They span from a two-line party trick to deep results like Dirichlet's approximation theorem. This article gives the precise statement of both the basic and generalized pigeonhole principle. It includes a complete proof from first principles using the Sum and Product Rules. It also offers two fully worked non-trivial examples. It takes a careful look at what happens when hypotheses are dropped. Finally, it surveys where the idea resurfaces in mathematics and computing.

Key takeaways

The Pigeonhole Principle says $n$ objects in $k$ boxes with $n > k$ forces some box to hold $\ge 2$ objects.
The generalized version: $n$ objects in $k$ boxes forces some box to hold $\ge \lceil n/k \rceil$ objects.
It is equivalent to the statement that a function from a larger finite set to a smaller one cannot be injective.
The proof is by contrapositive/contradiction and uses only the Sum Rule for counting.
It is a purely existential tool: it never identifies which box or which objects collide.
Key idea: counting a mismatch between set sizes is enough to force a collision, with no further information needed.

Where this lives today

In number theory, the pigeonhole principle underlies Dirichlet's approximation theorem: for any irrational $\alpha$ and any $N$ , there exist integers $p,q$ with $1 \le q \le N$ and $|\alpha - p/q| < 1/(qN)$ , proved by partitioning $[0,1)$ into $N$ subintervals and pigeonholing the fractional parts $\{q\alpha\}$ for $q = 0,\dots,N$ . In computer science, hash table collision analysis, the impossibility of perfect lossless compression for all inputs, and lower bounds in data structures all rest on pigeonhole counting: if a hash function maps more keys than table slots, collisions are unavoidable, and no compression algorithm can shrink every possible input string without some inputs growing, since there are strictly more short strings than shorter ones. In cryptography, the principle bounds the security of hash functions against collision resistance: any hash function with output space of size $k$ must have a collision among any $k+1$ distinct inputs, motivating the birthday-attack style analysis of hash collision probabilities. In combinatorics and graph theory, it is the seed of Ramsey theory: in any graph on $6$ vertices, pigeonhole-style degree-counting forces a monochromatic triangle in any red/blue edge coloring, the simplest nontrivial Ramsey number $R(3,3)=6$ . In analysis and probability, discretizing continuous ranges into finitely many bins and pigeonholing sample points into them is a recurring technique for proving existence of clusters, recurrence, or bounded gaps (e.g., in ergodic theory and the study of equidistribution).

Ask the tutor: How do I choose the right "boxes" when the pigeonhole setup isn't obvious from the problem statement?

N

Intuition

Picture $k$ labeled boxes drawn as bins on a number line, and $n$ pigeons that must each land in exactly one bin. If you have strictly more pigeons than bins, the "average occupancy" per bin exceeds $1$ , and since occupancy counts are whole numbers, some bin must round that average up rather than down. This is the entire mechanism: averages of integers that are not themselves integers force some term above the average. The generalized principle sharpens this averaging idea. If $n$ pigeons fill $k$ boxes, the average number of pigeons per box is $n/k$ . It is impossible for every box to hold strictly fewer than $n/k$ objects on average without violating the total count — so some box must reach at least $\lceil n/k \rceil$ . The ceiling appears precisely because box occupancy must be an integer, and $n/k$ need not be.

Figure

13 pigeons distributed into 12 monthly boxes: one box must hold ≥ 2

Central theorem

n, k

P

f: N \to K

|N| > |K| \implies f

Worked examples

Example 1 (Non-uniform box sizes forcing a specific count). A librarian has $100$ books to shelve into $9$ labeled bins by Dewey category. Show that some bin receives at least $12$ books, and exhibit that $12$ is the best bound the principle can guarantee (i.e., it is achievable that no bin receives more than $12$ ). Solution. Here $n = 100$ , $k = 9$ . Compute

\left\lceil \frac{100}{9} \right\rceil = \left\lceil 11.111\ldots \right\rceil = 12.

By the Generalized Pigeonhole Principle, some bin holds at least $12$ books. To see this bound is tight, exhibit a distribution matching it: put $4$ books in one bin and $12$ in each of the other $8$ bins:

4 + 12 \times 8 = 4 + 96 = 100.

This uses exactly $100$ books, no bin exceeds $12$ , and one bin (in fact several) attains exactly $12$ . So the guaranteed bound $12$ cannot be improved to $13$ in general — the theorem's conclusion is sharp. (Note the theorem never claims every bin reaches $12$ ; it only asserts some bin does, and here the extremal example shows the guarantee cannot be strengthened.)

Example 2 (A number-theoretic collision via injectivity failure, asymmetric inputs). Show that among any $7$ distinct integers chosen from $\{1, 2, \dots, 12\}$ , two of them sum to $13$ . Solution. Partition $\{1, \dots, 12\}$ into $6$ unordered pairs each summing to $13$ :

\{1,12\}, \{2,11\}, \{3,10\}, \{4,9\}, \{5,8\}, \{6,7\}.

These $6$ pairs are pairwise disjoint and their union is $\{1,\dots,12\}$ — a genuine partition into $k = 6$ blocks. Define $f$ on the chosen set $N$ of $7$ integers by letting $f(x)$ be the pair (block) containing $x$ ; formally $f: N \to K$ where $K$ is the set of $6$ pairs and $f(x)$ is the unique pair containing $x$ . Since $|N| = 7 > 6 = |K|$ , the Pigeonhole Principle (basic form) guarantees $f$ is not injective: two distinct chosen integers $a \ne b$ land in the same pair, i.e. $f(a) = f(b)$ . But each pair $\{i, 13-i\}$ has only two elements, and if $a \ne b$ both lie in the same pair, they must be exactly the two elements of that pair (a set of size 2 cannot contain three distinct elements $a, b,$ and also the pair's own two members unless $a,b$ are those two members). Hence $\{a,b\} = \{i, 13-i\}$ for some $i$ , so $a + b = 13$ . To confirm sharpness: choosing only $6$ integers, e.g. $\{1,2,3,4,5,6\}$ , avoids any pair summing to $13$ (since $\{1,12\},\dots$ each contribute at most one element from $\{1,\dots,6\}$ ). This shows $7$ is the minimal number of integers that forces the conclusion — the bound in the problem is exactly the pigeonhole threshold $k+1 = 7$ .

K

Scope, edge cases & common traps

Situation	What holds	What fails / caution
$n \le k$	No collision is forced; an injection may or may not exist	Do not assume a collision — check $n>k$ first
$n > k$ , both finite	Collision guaranteed (basic form)	Principle gives existence, not which pigeons collide
Arbitrary $n,k \ge 1$ finite	Some box has $\ge \lceil n/k\rceil$ (generalized form)	$\lceil n/k \rceil$ , not $n/k$ rounded incorrectly — always take the ceiling, never floor
$K$ infinite	Principle does not apply	See counterexample above
Boxes defined by a partition not literally "boxes"	Still valid — any partition of $N$ into $k$ disjoint blocks works	Must verify the blocks are disjoint and cover $N$ (a genuine partition)
Multiple valid partitions of the same problem	Different partitions can give different (both correct) bounds	Choosing a coarser partition (fewer $k$ ) gives a weaker, still valid, bound; look for the finest useful partition

The mathematician behind it

Origins · 1 minPeter Gustav Lejeune Dirichlet and how this was discovered

Peter Gustav Lejeune Dirichlet

1805–1859 · 19th-century Prussia/Germany, analytic number theory

Dirichlet is credited with the first systematic use of the pigeonhole principle in serious mathematics, applying it in number theory — for instance in his proof related to rational approximation of irrational numbers, now known as Dirichlet's approximation theorem. The principle is still sometimes called the Dirichletscher Schubfachschluss ("Dirichlet's drawer/box principle") in German mathematical tradition, reflecting his central role in elevating an intuitive observation into a rigorous proof technique used throughout number theory.

History

- 1834: Dirichlet applies the drawer/box argument in a number-theoretic proof, giving the principle its first prominent rigorous use.

- 1842: Dirichlet's approximation theorem is published, showing every irrational number has infinitely many good rational approximations, proved via a pigeonhole argument on fractional parts.

- Late 1800s: The term "pigeonhole principle" enters English mathematical usage, referencing literal pigeonhole desk compartments.

- 20th century: The principle becomes a standard tool in combinatorics textbooks and a staple of olympiad and computer science curricula.

- Present: Generalized and probabilistic versions (e.g., the probabilistic method, Ramsey theory) trace their combinatorial ancestry directly to this principle.

Does the pigeonhole principle tell us which box has multiple items?

No. The principle is purely existential: it guarantees some box must be overcrowded but gives no information about which box or which specific objects collide. The proof works by contradiction — assuming no box is crowded leads to a numerical contradiction — so it never constructs the colliding pair explicitly. In applications, you often need a separate, sometimes clever, argument or search to actually locate the collision, even though its existence is already certain. This non-constructive character is common to many existence proofs in combinatorics and is not a weakness of the technique, but a defining feature of what it can and cannot claim.

Is the pigeonhole principle the same as saying

|N| > |K|

implies no bijection exists?

Closely related but not identical in emphasis. If $|N| > |K|$ , then indeed no bijection $N \to K$ can exist (bijections require equal cardinalities for finite sets), but the pigeonhole principle says something stronger and more specific: any function at all, injective or not, must have a repeated value somewhere. It is really a statement about the impossibility of injections in this cardinality regime, phrased in terms of forced collisions rather than merely the absence of a perfect one-to-one correspondence.

How is the ceiling function

\lceil n/k \rceil

justified rather than rounding normally?

The ceiling arises because box occupancy counts are non-negative integers, and the proof shows that assuming every box holds fewer than $n/k$ objects leads to a total strictly less than $n$ , a contradiction. The threshold "fewer than $n/k$ " translates precisely to "at most $\lceil n/k\rceil - 1$ " for integers, by the defining property $\lceil x\rceil - 1 < x \le \lceil x \rceil$ . Ordinary rounding (to nearest) would not give a valid guaranteed lower bound; only the ceiling correctly captures "smallest integer not below the average."

Can the pigeonhole principle be applied to infinite sets at all?

The classical finite-box version, as stated here, strictly requires both $N$ and $K$ finite; the counterexample block shows the argument breaks completely when $K$ is infinite. However, there are genuinely infinite analogues, such as: if $N$ is infinite and partitioned into finitely many blocks, some block must be infinite (this follows from finite additivity failing for an all-finite partition of an infinite set). That is a different, though related, statement, and should not be confused with the finite generalized principle proved here.

What is the difference between the "basic" and "generalized" pigeonhole principle?

The basic form only concludes that some box has at least $2$ objects, applicable whenever $n > k$ . The generalized form gives a quantitative lower bound, $\lceil n/k \rceil$ , on the most-crowded box's occupancy for any $n$ and $k$ , not just $n = k+1$ . The basic form is literally the special case of the generalized one when $n = k+1$ , since $\lceil (k+1)/k \rceil = 2$ . Most real applications, such as bounding shared birth months among large groups or forcing repeated remainders, use the generalized form to extract a specific numeric guarantee rather than just "a repeat exists."

Does choosing a different partition change the strength of the conclusion?

Yes, significantly. The pigeonhole principle's power depends entirely on how cleverly you choose the boxes (the partition of the codomain or an auxiliary set). A coarser partition (fewer, larger boxes) gives a weaker but still valid bound; a finer, well-chosen partition can extract a much sharper and more useful conclusion, as seen in Example 2 where pairing $\{i, 13-i\}$ was the crucial creative step. Much of the skill in applying this principle lies in designing the right boxes, not in the mechanical final step.

Where does the name "pigeonhole" come from?

The name references old writing-desk furniture with a grid of small open compartments, called "pigeonholes," originally used to sort mail or documents (and named by analogy to compartments in a dovecote used for pigeons). The mathematical metaphor imagines "pigeons" (objects) being placed into these "holes" (categories or boxes), so that too many pigeons and too few holes forces at least one hole to contain more than one pigeon. In German mathematical literature the same idea appears as the "Schubfachprinzip" (drawer principle), associated historically with Dirichlet's early rigorous use of the argument.