The pigeonhole principle

Theorem

The pigeonhole principle

T-003Home MU-101Threads logic · structure

Statement

Let \(n \in \mathbb{N}\). Let \(A\) be a finite set with exactly \(n+1\) elements (the objects) and let \(B\) be a finite set with exactly \(n\) elements (the boxes). If \(f \colon A \to B\) is any function — that is, every object is assigned to exactly one box — then \(f\) is not injective: there exist distinct \(a, a' \in A\) with \(f(a) = f(a')\). Equivalently, some box \(b \in B\) satisfies \(\left|f^{-1}(b)\right| \ge 2\): at least one box holds at least two objects. All hypotheses are needed: the sets are finite, the objects are distinct, every object is placed, and the number of objects strictly exceeds the number of boxes.

Why it matters

The pigeonhole principle is the sharpest possible statement of an obvious fact, and it is the engine behind an astonishing range of non-obvious theorems: Dirichlet's approximation theorem in number theory, the Erdős–Szekeres monotone subsequence theorem, the existence of collisions in any hash function, the impossibility of lossless compression of all inputs, and the first step of every Ramsey-theoretic argument. It converts a purely quantitative comparison — more objects than boxes — into a purely existential conclusion — a collision exists — without giving any information about where the collision is.

Foundationally, the principle is equivalent to the assertion that there is no injection from \([n+1]\) into \([n]\), and this is exactly what makes the cardinality of a finite set well defined: without it, a set could consistently "have" both \(m\) and \(n\) elements for \(m \neq n\). It is therefore one of the load-bearing walls of finite combinatorics.

Hypotheses

Strictly more objects than boxes: \(|A| = n+1\), \(|B| = n\).Drop the "+1" and the conclusion fails outright: the identity map \([n] \to [n]\) places \(n\) objects into \(n\) boxes with every box holding exactly one. Equality of counts permits a bijection.

Every object is placed, and placed in exactly one box (\(f\) is a total function \(A \to B\)).If one object may be left unplaced, put objects \(a_1, \dots, a_n\) into boxes \(b_1, \dots, b_n\) bijectively and discard \(a_{n+1}\): no box holds two. If an object may occupy several boxes, "counting objects" no longer bounds fibre sizes.

The objects are distinct (\(A\) is a set of cardinality \(n+1\), not a list with repetitions).Listing the same object twice inflates the count: the "two objects" the theorem delivers must be genuinely distinct elements of \(A\), which fails if \(a_i = a_j\) for \(i \neq j\).

Finiteness of \(B\) (and the finite-cardinality reading of "more than").With infinitely many boxes \(b_1, b_2, \dots\) the \(n+1\) objects can each take a private box. Worse, for infinite sets "properly contains" no longer forbids injections into the smaller-looking set: \(\mathbb{Z} \supsetneq \mathbb{N}\), yet \(z \mapsto 2z\) for \(z \ge 0\) and \(z \mapsto -2z-1\) for \(z \lt 0\) is an injection \(\mathbb{Z} \to \mathbb{N}\). Only genuine cardinality inequalities, not superset relations, control injections in the infinite case.

Proof

Write \([m] = \{1, 2, \dots, m\}\) for \(m \in \mathbb{N}\), with \([0] = \emptyset\). "\(|A| = m\)" means, by definition, that there exists a bijection \([m] \to A\).

A placement of the objects into the boxes is a function \(f \colon A \to B\), and "some box holds at least two objects" is precisely the statement "\(f\) is not injective", i.e. \(\exists\, a \neq a'\) with \(f(a) = f(a')\).

Definition of function (each object lands in exactly one box) and definition of injectivity; if \(f(a) = f(a') = b\) with \(a \neq a'\) then \(a, a' \in f^{-1}(b)\), so \(\left|f^{-1}(b)\right| \ge 2\), and conversely. A

It suffices to prove: for every \(n \in \mathbb{N}\), there is no injection \([n+1] \to [n]\). \(\quad(\star)\)

By hypothesis there are bijections \(\alpha \colon [n+1] \to A\) and \(\beta \colon B \to [n]\). If \(f\) were injective, then \(\beta \circ f \circ \alpha \colon [n+1] \to [n]\) would be a composition of injections, hence injective: if \((\beta \circ f \circ \alpha)(x) = (\beta \circ f \circ \alpha)(y)\), injectivity of \(\beta\) gives \(f(\alpha(x)) = f(\alpha(y))\), injectivity of \(f\) gives \(\alpha(x) = \alpha(y)\), and injectivity of \(\alpha\) gives \(x = y\). So \((\star)\) forbids \(f\) from being injective. C

We prove \((\star)\) by induction on \(n\). Base case \(n = 0\): there is no function at all from \([1] = \{1\}\) to \([0] = \emptyset\), injective or otherwise.

Induction principle for \(\mathbb{N}\) (Peano axiom). For the base case: a function \(g \colon [1] \to \emptyset\) would have a value \(g(1) \in \emptyset\), contradicting the definition of the empty set. A

Inductive step. Assume \((\star)\) holds for \(n\): no injection \([n+1] \to [n]\). Suppose, for contradiction, that \(g \colon [n+2] \to [n+1]\) is injective.

Proof by contradiction inside the inductive step; the induction hypothesis is the case-\(n\) instance of \((\star)\). A

Let \(\tau \colon [n+1] \to [n+1]\) be the transposition exchanging \(g(n+2)\) and \(n+1\) (and the identity if \(g(n+2) = n+1\)). Set \(h = \tau \circ g\). Then \(h \colon [n+2] \to [n+1]\) is injective and \(h(n+2) = n+1\).

A transposition is its own inverse, hence a bijection; a composition of injections is injective (as verified in Step 2); and \(h(n+2) = \tau(g(n+2)) = n+1\) by the definition of \(\tau\). This normalisation is the key idea: it lets us peel off the top element. B

For every \(i \in [n+1]\) we have \(h(i) \neq n+1\), hence \(h(i) \in [n]\). Therefore the restriction \(h' = h\restriction_{[n+1]} \) is a function \([n+1] \to [n]\), and \(h'\) is injective.

If \(h(i) = n+1 = h(n+2)\) with \(i \le n+1 \lt n+2\), injectivity of \(h\) forces \(i = n+2\), a contradiction; so \(h(i) \in [n+1] \setminus \{n+1\} = [n]\). A restriction of an injective function is injective: distinct points of the subdomain are distinct points of the domain. C

\(h' \colon [n+1] \to [n]\) is an injection, contradicting the induction hypothesis. Hence no injective \(g \colon [n+2] \to [n+1]\) exists, which is \((\star)\) for \(n+1\). By induction, \((\star)\) holds for all \(n \in \mathbb{N}\).

The contradiction discharges the supposition of Step 4; the induction principle then yields \((\star)\) universally. B

By Steps 1–2, \(f \colon A \to B\) is not injective; choose \(a \neq a'\) in \(A\) with \(f(a) = f(a')\). The box \(b = f(a)\) then satisfies \(\left|f^{-1}(b)\right| \ge 2\).

Instantiation of the existential statement produced in Step 1. Note the proof is nonconstructive as a matter of use: it certifies existence of the crowded box without identifying it. \(\blacksquare\) A

Result

\[ |A| = n+1,\quad |B| = n,\quad f \colon A \to B \;\Longrightarrow\; \exists\, a \neq a' \in A:\; f(a) = f(a') \]

Reading. If you distribute strictly more objects than you have boxes — even just one more — some box must receive at least two. You learn that a collision exists, never where it is.

Scope. Applies to any finite sets \(A\), \(B\) with \(|A| \gt |B|\) and any total single-valued assignment \(f \colon A \to B\). It says nothing when \(|A| \le |B|\), nothing when \(B\) is infinite, and nothing about which box is crowded or by how much beyond the guaranteed bound.

Corollaries & converses

Generalised pigeonhole. If \(m\) objects are placed in \(n \ge 1\) boxes, some box holds at least \(\left\lceil m/n \right\rceil\) objects. (If every box held at most \(\left\lceil m/n \right\rceil - 1\), the total would be at most \(n\left(\left\lceil m/n \right\rceil - 1\right) \lt m\), using \(\left\lceil m/n \right\rceil - 1 \lt m/n\).) The basic principle is the case \(m = n+1\).
Monotonicity of finite cardinality. If an injection \([m] \to [n]\) exists then \(m \le n\); hence if \([m]\) and \([n]\) are in bijection then \(m = n\). This is exactly what makes "the number of elements" of a finite set well defined.
Contrapositive (packing form). If every box holds at most one object, then the number of objects is at most the number of boxes — the form used in extremal arguments.
Infinite pigeonhole. If infinitely many objects are placed in finitely many boxes, some box holds infinitely many objects. (Otherwise the object set would be a finite union of finite sets, hence finite.) This is the seed of Ramsey theory.
Converse fails. "Some box holds two" does not imply "more objects than boxes": place \(2\) objects into the same one of \(100\) boxes. A collision certifies nothing about global counts.

Fails without

Only \(n\) objects. The identity map \([n] \to [n]\) places \(n\) objects in \(n\) boxes with every fibre a singleton. The "+1" is not a convenience; it is the entire content.
Infinitely many boxes. With boxes \(b_1, b_2, b_3, \dots\) indexed by \(\mathbb{N}\), send object \(a_i\) to \(b_i\): the \(n+1\) objects occupy \(n+1\) distinct boxes and no collision occurs, however large \(n\) is.
Infinite "more than" read as superset. \(\mathbb{Z}\) properly contains \(\mathbb{N}\), yet \(z \mapsto 2z\) (for \(z \ge 0\)), \(z \mapsto -2z - 1\) (for \(z \lt 0\)) injects \(\mathbb{Z}\) into \(\mathbb{N}\) with no collision. For infinite sets only cardinality, not inclusion, governs injections.
Partial placement. If \(f\) is only defined on a subset of \(A\), place \(a_1, \dots, a_n\) bijectively and leave \(a_{n+1}\) out: no box holds two. Totality of \(f\) is essential.

Common errors

Off-by-one. Arguing "there are \(n\) objects and \(n\) boxes, so two share" — equality of counts guarantees nothing; you need strictly more objects.
Reversing the generalised bound. The generalised principle gives a box with at least \(\left\lceil m/n \right\rceil\) objects; students often claim a box with at most \(\left\lfloor m/n \right\rfloor\), which is the (also true, but different) dual statement, or mix the two.
Bad box design. In applications the boxes must (i) cover every object, (ii) be pairwise disjoint (or at least assign each object one box), and (iii) number at most \(n\). A typical slip: partitioning a square into four open subsquares, so boundary points belong to no box and the "placement" is not a function.
Expecting constructivity. The principle asserts a collision exists; it never identifies the crowded box. Proofs that go on to "the box containing two objects is box \(k\)" are importing information the theorem does not supply.
"Exactly two." The conclusion is "at least two"; a single box may hold all \(n+1\) objects, and other boxes may be empty. Nothing forces every box to be occupied.
Swapping pigeons and holes. In problems, misidentifying which quantity plays "objects" and which plays "boxes" (e.g. treating residue classes as objects rather than boxes) silently reverses the required inequality.

Discussion

The principle is traditionally credited to Dirichlet, who in 1834 used it — under the name Schubfachprinzip, "drawer principle" — to prove his approximation theorem: for every real \(\alpha\) and every \(N \in \mathbb{N}\) there exist integers \(p, q\) with \(1 \le q \le N\) and \(\left|\alpha - p/q\right| \lt \frac{1}{qN}\) (Problem 4 below proves the core estimate). The idea itself is older and appears informally in seventeenth-century writings, but Dirichlet's use marks its debut as a serious research tool: a trivial-looking counting fact powering a genuinely deep theorem about the rational approximability of every real number.

Conceptually, the theorem is the finite half of a fundamental dichotomy. For finite sets, inclusion-style size comparisons and injection-style comparisons agree: \([m]\) injects into \([n]\) exactly when \(m \le n\). For infinite sets this collapses — Dedekind in fact defined a set to be infinite precisely when it admits an injection into a proper subset of itself. Thus the pigeonhole principle is equivalent to the assertion that no \([n]\) is Dedekind-infinite, and it is the reason finite cardinal arithmetic is well founded at all.

The principle also sits at the root of Ramsey theory. Its infinite form — any finite colouring of an infinite set has an infinite monochromatic class — is the base case of Ramsey's theorem, and the finite form drives the counting in Erdős–Szekeres (Problem 5), van der Waerden-type arguments, and the standard proofs that hash collisions, birthday coincidences, and repeated remainders are unavoidable. In computer science it yields impossibility results: no lossless compressor shortens every input, because the \(2^{n+1} - 1\) nonempty strings of length at most \(n\) cannot receive injectively the \(2^{n+1}\) strings of length exactly \(n+1\) plus anything else — more precisely, there is no injection from the \(2^n\) strings of length \(n\) into the \(2^n - 1\) strings of length less than \(n\).

In proof complexity the principle plays a starring role as a hard tautology. Encode "there is no injection \([n+1] \to [n]\)" as a propositional formula \(\mathrm{PHP}^{n+1}_n\) with variables \(x_{ij}\) ("object \(i\) goes to box \(j\)"). Haken proved (1985) that every resolution refutation of \(\neg\mathrm{PHP}^{n+1}_n\) has size \(2^{\Omega(n)}\): resolution, the engine of SAT solvers, cannot count. Bounded-depth Frege systems are also exponentially weak on it (Ajtai; Beame–Impagliazzo–Krajíček–Pitassi–Pudlák–Woods), while unrestricted Frege systems admit polynomial-size proofs (Buss). So a statement whose semantic content is trivial calibrates, with surprising precision, the counting power of proof systems — and correspondingly the strength of fragments of bounded arithmetic in which it is or is not provable.

Common misconceptions. The principle does not tell you which box is crowded, does not give "exactly two", does not force any other box to be nonempty, and does not survive the passage to infinitely many boxes. And in applications the creative act is never the principle itself but the choice of boxes: a pigeonhole proof is exactly as strong as the partition it is built on.

Worked examples

Example 1 (consecutive, hence coprime, elements). Claim: every subset \(S \subseteq \{1, 2, \dots, 2n\}\) with \(|S| = n+1\) contains two consecutive integers; in particular two coprime elements.

Define boxes \(P_k = \{2k-1,\, 2k\}\) for \(k = 1, \dots, n\). These are pairwise disjoint and \(\bigcup_{k=1}^{n} P_k = \{1, \dots, 2n\}\), so every element of \(S\) lies in exactly one box.

Each \(s \in \{1,\dots,2n\}\) lies in \(P_k\) for the unique \(k = \left\lceil s/2 \right\rceil\); this defines the placement function \(f \colon S \to [n]\), \(f(s) = \left\lceil s/2 \right\rceil\). A

\(|S| = n+1\) objects, \(n\) boxes: by the pigeonhole principle there exist distinct \(s, t \in S\) with \(f(s) = f(t) = k\), i.e. \(\{s, t\} = \{2k-1,\, 2k\}\).

Direct application of T-003 with \(A = S\), \(B = [n]\); the fibre \(P_k \cap S\) has at least two elements, and \(P_k\) has only the two listed elements. B

\(s\) and \(t\) are consecutive, so \(\gcd(s, t) = 1\): any common divisor \(d\) divides \(t - s = 1\).

Divisibility is linear: \(d \mid s\) and \(d \mid t\) imply \(d \mid (t - s)\); the only positive divisor of \(1\) is \(1\). A

\[ S \subseteq \{1, \dots, 2n\},\; |S| = n+1 \;\Longrightarrow\; \exists\, s, t \in S:\; t = s+1,\ \gcd(s,t) = 1 \]

Reading. Choosing more than half of \(\{1, \dots, 2n\}\) forces a consecutive pair, hence a coprime pair. The bound is sharp: the \(n\) even numbers \(\{2, 4, \dots, 2n\}\) contain no consecutive pair.

Scope. Any \(n \ge 1\) and any \((n+1)\)-element subset; the boxes are the \(n\) blocks \(\{2k-1, 2k\}\).

Example 2 (lattice midpoints). Claim: among any \(5\) points of \(\mathbb{Z}^2\), two have a midpoint that again lies in \(\mathbb{Z}^2\).

Define the parity map \(f \colon \mathbb{Z}^2 \to \{0,1\}^2\), \(\quad f(x, y) = \left(x \bmod 2,\; y \bmod 2\right)\). The codomain has exactly \(4\) elements: the parity classes (even, even), (even, odd), (odd, even), (odd, odd).

Every integer is congruent to exactly one of \(0, 1\) modulo \(2\) (division algorithm), so \(f\) is a well-defined total function; the four classes are the boxes. A

Five points, four boxes: by the pigeonhole principle two distinct points \(p = (x_1, y_1)\) and \(q = (x_2, y_2)\) satisfy \(f(p) = f(q)\), i.e. \(x_1 \equiv x_2\) and \(y_1 \equiv y_2 \pmod 2\).

T-003 with \(|A| = 5 = 4 + 1\) objects and \(|B| = 4\) boxes. B

Then \(x_1 + x_2\) and \(y_1 + y_2\) are both even, so \[ \frac{p + q}{2} = \left( \frac{x_1 + x_2}{2},\; \frac{y_1 + y_2}{2} \right) \in \mathbb{Z}^2 . \]

The sum of two integers of equal parity is even, and an even integer halves to an integer. A

\[ p_1, \dots, p_5 \in \mathbb{Z}^2 \text{ distinct} \;\Longrightarrow\; \exists\, i \neq j:\; \tfrac{1}{2}(p_i + p_j) \in \mathbb{Z}^2 \]

Reading. Five lattice points always contain a pair whose midpoint is a lattice point. Four points can fail: \((0,0), (1,0), (0,1), (1,1)\) occupy all four parity classes and every midpoint is non-integral.

Scope. Exactly \(5 = 2^2 + 1\) points in dimension \(2\); in \(\mathbb{Z}^d\) the same argument needs \(2^d + 1\) points, one more than the number of parity classes.

Problems

(Routine.) Show that among any \(13\) people, at least two were born in the same calendar month; and that among \(100\) people, at least \(\left\lceil 100/12 \right\rceil = 9\) share a birth month.
Solution
Boxes: the \(12\) months; objects: the people; placement: each person's birth month (a total function — everyone has exactly one birth month). With \(13 = 12 + 1\) people, T-003 gives two in one box. For \(100\) people use the generalised pigeonhole: if every month held at most \(8\) people, the total would be at most \(12 \cdot 8 = 96 \lt 100\), a contradiction; so some month holds at least \(9\).
Show that among any \(5\) points in the closed unit square \([0,1]^2\), two are at distance at most \(\frac{\sqrt{2}}{2}\).
Solution
Partition the square into four boxes \(Q_{ij} = I_i \times I_j\) where \(I_0 = \left[0, \tfrac12\right]\), \(I_1 = \left(\tfrac12, 1\right]\), for \(i, j \in \{0, 1\}\). These four sets are pairwise disjoint and cover \([0,1]^2\) (each coordinate lies in exactly one \(I_k\)), so assignment to a box is a total function — note the half-open design avoids the classic boundary error. Five points, four boxes: by T-003 two distinct points \(p, q\) lie in one \(Q_{ij}\). Each \(Q_{ij}\) is contained in a closed square of side \(\tfrac12\), whose diameter is its diagonal: \[ \lVert p - q \rVert \le \sqrt{\left(\tfrac12\right)^2 + \left(\tfrac12\right)^2} = \frac{\sqrt{2}}{2}. \] The constant is optimal: the four corners and the centre have pairwise distances at least \(\frac{\sqrt2}{2}\), realising equality.
Show that any \(S \subseteq \{1, 2, \dots, 2n\}\) with \(|S| = n+1\) contains distinct elements \(a, b\) with \(a \mid b\).
Solution
Every positive integer factors uniquely as \(s = 2^{e} m\) with \(e \ge 0\) and \(m\) odd (extract the full power of \(2\); uniqueness follows from unique factorisation). Define the placement \(f(s) = m\), the odd part of \(s\). For \(s \le 2n\) the odd part lies in \(\{1, 3, 5, \dots, 2n-1\}\), a set of exactly \(n\) odd numbers: these are the boxes. With \(|S| = n+1\), T-003 yields distinct \(a = 2^{e_1} m\), \(b = 2^{e_2} m\) with the same odd part \(m\) and \(e_1 \neq e_2\) (equal exponents would force \(a = b\)). If \(e_1 \lt e_2\) then \(a \mid b\), since \(b = 2^{e_2 - e_1} a\); otherwise \(b \mid a\). Sharpness: \(S = \{n+1, n+2, \dots, 2n\}\) has \(n\) elements and no divisibility pair, since \(2(n+1) \gt 2n\).
(Dirichlet approximation.) Let \(\alpha \in \mathbb{R}\) and \(N \in \mathbb{N}\), \(N \ge 1\). Show there exist integers \(p\) and \(q\) with \(1 \le q \le N\) and \(\left| q\alpha - p \right| \lt \frac{1}{N}\).
Solution
Write \(\{x\} = x - \lfloor x \rfloor \in [0, 1)\) for the fractional part. Consider the \(N+1\) objects \(\{0 \cdot \alpha\}, \{1 \cdot \alpha\}, \dots, \{N\alpha\}\) and the \(N\) boxes \[ I_j = \left[ \tfrac{j}{N},\, \tfrac{j+1}{N} \right), \qquad j = 0, 1, \dots, N-1, \] which partition \([0,1)\), so each object lies in exactly one box. (If two of the listed objects coincide as real numbers they are still distinct objects, indexed by distinct \(k\) — the placement is a function of the index \(k \in \{0, \dots, N\}\), sending \(k\) to the box containing \(\{k\alpha\}\).) By T-003 there are indices \(0 \le k_1 \lt k_2 \le N\) with \(\{k_1\alpha\}\) and \(\{k_2\alpha\}\) in the same \(I_j\), hence \[ \left| \{k_2\alpha\} - \{k_1\alpha\} \right| \lt \tfrac{1}{N}, \] since \(I_j\) has length \(\frac{1}{N}\) (and is half-open, so the difference is strictly below \(\frac1N\)). Set \(q = k_2 - k_1\) and \(p = \lfloor k_2\alpha \rfloor - \lfloor k_1\alpha \rfloor\). Then \(1 \le q \le N\), \(p \in \mathbb{Z}\), and \[ q\alpha - p = \left(k_2\alpha - \lfloor k_2\alpha \rfloor\right) - \left(k_1\alpha - \lfloor k_1\alpha \rfloor\right) = \{k_2\alpha\} - \{k_1\alpha\}, \] so \(\left| q\alpha - p \right| \lt \frac{1}{N}\). Dividing by \(q\) gives \(\left| \alpha - \frac{p}{q} \right| \lt \frac{1}{qN} \le \frac{1}{q^2}\), Dirichlet's theorem on rational approximation.
(Erdős–Szekeres.) Show that every sequence \(x_1, x_2, \dots, x_{n^2 + 1}\) of distinct real numbers contains a monotone (increasing or decreasing) subsequence of length \(n + 1\).
Solution
For each index \(k\) let \(i_k\) be the length of the longest strictly increasing subsequence ending at \(x_k\), and \(d_k\) the length of the longest strictly decreasing subsequence ending at \(x_k\); both are at least \(1\). Suppose, for contradiction, that every monotone subsequence has length at most \(n\); then \(i_k \le n\) and \(d_k \le n\) for all \(k\), so the label map \(k \mapsto (i_k, d_k)\) places the \(n^2 + 1\) indices into the \(n^2\) boxes \([n] \times [n]\). By T-003 there are indices \(j \lt k\) with \((i_j, d_j) = (i_k, d_k)\). Since the \(x\)'s are distinct, either \(x_j \lt x_k\) or \(x_j \gt x_k\). If \(x_j \lt x_k\): append \(x_k\) to a longest increasing subsequence ending at \(x_j\) to get an increasing subsequence of length \(i_j + 1\) ending at \(x_k\), so \(i_k \ge i_j + 1 \gt i_j = i_k\), a contradiction. If \(x_j \gt x_k\): the same appending argument on decreasing subsequences gives \(d_k \ge d_j + 1 \gt d_j = d_k\), again a contradiction. Hence some monotone subsequence has length at least \(n + 1\). Sharpness: the sequence \[ n, \, n-1, \dots, 1,\; 2n, \, 2n-1, \dots, n+1,\; \dots,\; n^2, \dots, n^2 - n + 1 \] (\(n\) descending blocks of length \(n\), each block higher than the last) has \(n^2\) terms and no monotone subsequence longer than \(n\).