Pigeonhole principle ($N>m⟹\text{some box contains at least two objects}$)

Place $N$ objects into $m\ge 1$ 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. ^[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$.

A geometric example. Any five points in a square of side one contain two whose Euclidean distance is at most $1/\sqrt{2}$. 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\ge 1/2$ to the right half; $y<1/2$ belongs to the lower half and $y\ge 1/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 boundFor 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}\approx 0.424264$. These Cartesian coordinates exhibit the forced pair; the argument applies to every placement of five points.

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\equiv 2(\mathrm{mod}7)$, and $9-2=7$. Likewise, assigning fractional parts to short intervals gives the Dirichlet approximation theorem; its existing article explains the approximation bound.

For any sequence of $n\ge 1$ integers, some nonempty consecutive block has sum divisible by $n$. Form the $n+1$ prefix sums $s_0=0,s_j={\sum }_{k=1}^j{a}_k$. There are only $n$ residue classes modulo $n$, so the pigeonhole principle gives $s_i\equiv s_j(\mathrm{mod}n)$ for some $i<j$. Subtraction proves that $s_j-s_i$ is the required block sum. Negative entries and repeated entries cause no difficulty. Applied after any ordering of a finite set, it also gives a nonempty subset whose sum is divisible by the size of the set.

Suppose a subset of a metric space is covered by $m$ sets, each of diameter at most $D$. Assign each point to one covering set containing it, choosing a single set at shared boundaries. Among $m+1$ points, the pigeonhole principle puts two in a common set, and their distance is at most $D$. The pieces need not be equal or congruent. This freedom permits better distance bounds than dividing a region only into equal rectangles.

For $N$ objects assigned to $m\ge 1$ boxes, let $n_i$ be the number in box $i$. The generalized pigeonhole principle statesThe ceiling function rounds up because box counts are integers. An equivalent threshold formulation says: for a positive integer $k$, if $N>m(k-1)$, some box contains at least $k$ objects. For $N=m(k-1)$, putting $k-1$ objects in each box shows why the strict inequality matters. ^[ref]

Computed examples. For $N=13$ and $m=12$, $\lceil 13/12\rceil =2$. Counts $(2,1,1,1,1,1,1,1,1,1,1,1)$ attain this bound. For $N=23$ and $m=7$, $\lceil 23/7\rceil =4$, and the balanced counts $(4,4,3,3,3,3,3)$ sum to $23$ and have largest count exactly $4$. The threshold version agrees: $23>7(4-1)=21$. In contrast, seven boxes each containing three hold only $21$ objects.

The bound is sharp for every $N$ and $m$. Use Euclidean division to write $N=qm+r$ with integers $q\ge 0$ and $0\le r<m$. Place $q+1$ objects in each of $r$ boxes and $q$ objects in each remaining box. The largest count is $q+1$ if $r>0$, and $q$ if $r=0$, exactly $\lceil N/m\rceil$. This balanced arrangement makes the guarantee best possible even though other arrangements can be much more crowded.

Proof outline. If every count were at most $k-1$, the total would be at most $m(k-1)$. This contradicts $N>m(k-1)$. Taking $k=\lceil N/m\rceil$ proves the displayed bound for $N>0$; for $N=0$ every count is zero.

The infinite pigeonhole principle says that if an infinite set has a partition of a set into finitely many parts, at least one part is an infinite set. Equivalently, assigning infinitely many objects to a finite number of boxes forces some box to contain infinitely many objects. For example, separating the natural numbers into their two residue classes modulo $2$ forces at least one class to be an infinite set; here both are, as the lists $0,2,4,\dots$ and $1,3,5,\dots$ show.

Proof outline. A union of finitely many finite sets is a finite set. If all the parts were finite sets, their union could not be the original infinite set.

The assumption of finitely many parts is essential. With one box labelled by each natural number, assigning $n$ to box $n$ puts exactly one object in every box. Infinitely many objects and infinitely many boxes therefore need not produce even a shared box. The infinite pigeonhole principle is useful whenever finitely many labels organize an endless collection: one label must keep occurring infinitely often, providing an infinite set on which that label is constant.