= Pigeonhole principle
{title2=$N>m\implies\text{some box contains at least two objects}$}
{wiki}
Place $N$ objects into $m\geq1$ boxes, assigning each object to exactly one box. Here $N$ is a nonnegative <integer> and $m$ is a <positive integer>. The <pigeonhole principle> says that if $N>m$, some box contains at least two objects. Equivalently, a <function> from an $N$-element <finite set> to an $m$-element <finite set> cannot be an <injective function> when $N>m$. The boxes may stand for categories rather than physical containers. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf#page=581[Lehman, Leighton and Meyer, Mathematics for Computer Science, section 14.8, rule 14.8.1]{ref}
For thirteen objects and twelve boxes, a box containing at least two is unavoidable. Thinking of thirteen people and their birth months gives the same conclusion: at least two share a birth month. Twelve people could occupy the twelve months one apiece, so thirteen is the smallest number that forces a shared month. The <generalized pigeonhole principle> quantifies how many objects must share a box when there are still more objects.
The useful surprise is that the <pigeonhole principle> proves existence without needing to locate the objects involved. Choosing a good assignment rule is often the creative step: equal labels can mean equal remainders, nearby <points>, or repeated states of an <algorithm>. Once the rule is chosen, a short count can force a relationship among a much larger collection of objects. The <pigeonhole principle> itself does not name the crowded box. When the objects and their assignments are explicitly available, a simple <algorithm> finds one: scan the objects, keep the first object seen in each box, and stop when a later object enters an occupied box. At most $m+1$ scanned objects are needed when $N>m$.
\b[A geometric example.] Any five <points> in a <square> of side one contain two whose <Euclidean distance> is at most $1/\sqrt2$. Give each <point> <Cartesian coordinates> $(x,y)\in[0,1]^2$. Divide both ranges into the <intervals> $[0,1/2)$ and $[1/2,1]$, making four cells. Thus $x<1/2$ belongs to the left half and $x\geq1/2$ to the right half; $y<1/2$ belongs to the lower half and $y\geq1/2$ to the upper half. This convention assigns every boundary <point> to exactly one cell.
The <pigeonhole principle> puts two of the five <points> in the same cell. Their differences in <Cartesian coordinates> have magnitude at most $1/2$, so the <Pythagorean theorem> gives their <Euclidean distance> $d$ the bound
$$
d^2\leq\left(\frac12\right)^2+\left(\frac12\right)^2=\frac12,
\qquad d\leq\frac1{\sqrt2}\approx0.707107.
$$
For the plotted <points> $(0.1,0.1)$, $(0.4,0.4)$, $(0.8,0.2)$, $(0.2,0.8)$ and $(0.8,0.8)$, the first two occupy the lower-left cell and have <Euclidean distance> $\sqrt{0.3^2+0.3^2}=\sqrt{0.18}\approx0.424264$. These <Cartesian coordinates> exhibit the forced pair; the argument applies to every placement of five <points>.
\Image[/geometric-pigeonhole-square.png]
{title=The <pigeonhole principle> places two of five <points> in one of four cells of a <square>, bounding their <Euclidean distance> by $1/\sqrt2$}
\b[An arithmetic example.] Assign eight <integers> to their seven <residue classes> modulo the <integer modulus> $7$. The <pigeonhole principle> gives two with the same <residue class>, so $7$ is an <integer divisor> of their difference. In $\{2,5,9,12,16,20,24,27\}$, for example, $2$ and $9$ satisfy the <integer congruence> $9\equiv2\pmod7$, and $9-2=7$. Likewise, assigning <fractional parts> to short <intervals> gives the <Dirichlet approximation theorem>; its existing article explains the approximation bound.
Back to article page