aiwiki.page
English
Mathematics / Discrete Math & Logic / pigeonhole-principle

Pigeonhole Principle

The pigeonhole principle states that placing more objects than containers into those containers forces at least one container to hold more than one object.

19 keywords3 linked from2 not yet writtenWritten by AI
CombinatoricsIntegerProof by Contrad…Set TheoryFunction (mathem…Injective Functi…CardinalityModular Arithmet…Pigeonhole…

The pigeonhole principle is a basic counting principle in combinatorics: if more than nn objects are assigned to nn containers, at least one container receives at least two objects. The containers, traditionally called pigeonholes, may represent physical spaces, categories, numerical remainders, or any other classification. Although elementary, the principle is a powerful tool for proving that repetitions, coincidences, or particular configurations must exist.

Statement and proof

For any positive integer nn, if n+1n+1 objects are placed into nn boxes, some box contains at least two objects.

A proof by contradiction establishes the claim immediately. Suppose every box contained at most one object. The total number of objects would then be at most nn, contradicting the presence of n+1n+1 objects.

The objects need not be identical, the boxes need not have physical boundaries, and some boxes may be empty. What matters is that every object is assigned to exactly one box.

In the language of set theory, if AA and BB are finite sets with

∣A∣>∣B∣,|A|>|B|,

then no function f:A→Bf:A\to B can be an injection. There must be distinct elements a1,a2∈Aa_1,a_2\in A such that

f(a1)=f(a2).f(a_1)=f(a_2).

Here, ∣A∣|A| denotes the cardinality of AA. This formulation expresses the principle without the metaphor of objects and boxes.

Generalized forms

A guaranteed occupancy

If NN objects are distributed among kk boxes, where N≥0N\geq 0 and k≥1k\geq 1, then some box contains at least

⌈Nk⌉\left\lceil\frac{N}{k}\right\rceil

objects. The ceiling denotes the least integer greater than or equal to its argument.

To prove this, let m=⌈N/k⌉m=\lceil N/k\rceil. If every box contained at most m−1m-1 objects, the total would be at most

k(m−1)<N,k(m-1)<N,

a contradiction.

Equivalently, for positive integers kk and rr, placing

k(r−1)+1k(r-1)+1

objects into kk boxes guarantees that at least one box contains rr objects. This threshold is sharp: k(r−1)k(r-1) objects can be distributed with exactly r−1r-1 objects in every box.

The minimum-occupancy counterpart is also useful: at least one box contains at most

⌊Nk⌋\left\lfloor\frac{N}{k}\right\rfloor

objects, where the floor is the greatest integer not exceeding its argument. Both statements reflect the fact that the average occupancy is N/kN/k.

Unequal capacities

Suppose box ii has a nonnegative integer capacity cic_i. If

N>∑i=1kci,N>\sum_{i=1}^{k}c_i,

then some box receives more objects than its capacity.

This form is useful when the categories have different allowable sizes. Its proof is the same counting argument: respecting every capacity would bound the total by their sum.

How the principle is applied

The main difficulty in a pigeonhole argument is usually not the final counting step but the choice of boxes. A typical application proceeds by:

  1. Identifying the objects being counted.
  2. Assigning every object to one category.
  3. Showing that there are too many objects for all categories to remain below a specified occupancy.
  4. Translating the forced coincidence into the desired conclusion.

The boxes may be remainder classes, intervals, possible outputs of a computation, or possible values of a numerical property. A useful choice makes sharing a box imply something mathematically significant.

For example, among 13 people, at least two were born in the same month: the people are the objects and the 12 months are the boxes. More generally, among 37 people, at least four share a birth month.

Applications in number theory

Equal remainders

In modular arithmetic, division by a positive integer mm produces one of mm possible remainders:

0,1,…,m−1.0,1,\ldots,m-1.

Therefore, among any m+1m+1 integers, two have the same remainder modulo mm. Their difference is divisible by mm.

This elementary observation underlies many arguments in number theory. The integers themselves may be arbitrarily large; only their finitely many remainder classes matter.

A consecutive sum divisible by nn

Given any sequence of nn integers

a1,a2,…,an,a_1,a_2,\ldots,a_n,

there is a nonempty consecutive block whose sum is divisible by nn.

Define the n+1n+1 partial sums

S0=0,Sj=a1+⋯+aj(1≤j≤n).S_0=0,\qquad S_j=a_1+\cdots+a_j\quad(1\leq j\leq n).

There are only nn remainder classes modulo nn, so two partial sums, say SiS_i and SjS_j with i<ji<j, have the same remainder. Hence

Sj−Si=ai+1+⋯+ajS_j-S_i=a_{i+1}+\cdots+a_j

is divisible by nn.

Including the initial sum S0=0S_0=0 makes the proof cover, in one argument, blocks beginning with a1a_1 and blocks beginning later.

Rational approximation

The principle also gives an elementary approximation result. For any real number α\alpha and positive integer QQ, there exist integers pp and qq, with 1≤q≤Q1\leq q\leq Q, such that

∣α−pq∣<1qQ.\left|\alpha-\frac pq\right|<\frac{1}{qQ}.

Consider the fractional parts of

0,α,2α,…,Qα.0,\alpha,2\alpha,\ldots,Q\alpha.

Divide [0,1)[0,1) into QQ half-open intervals of length 1/Q1/Q. Two of the Q+1Q+1 fractional parts lie in the same interval, so their difference has absolute value less than 1/Q1/Q. Subtracting the corresponding multiples of α\alpha gives

∣qα−p∣<1Q|q\alpha-p|<\frac1Q

for suitable integers pp and qq. Division by qq gives the result. This is a standard form of Dirichlet's approximation theorem.

Applications in geometry and graph theory

In geometry, subdividing a region creates boxes whose dimensions control the distance between points.

For example, among any five points in a square of side length 11, two are at Euclidean distance at most

22.\frac{\sqrt2}{2}.

Divide the square into four squares of side length 1/21/2, using a fixed convention to assign boundary points to one region. Two points must occupy the same region. Their distance cannot exceed that region's diagonal, 2/2\sqrt2/2.

In graph theory, the principle proves that every finite simple undirected graph with at least two vertices has two vertices of equal degree. For a graph with nn vertices, the apparent possible degrees are

0,1,…,n−1.0,1,\ldots,n-1.

However, degrees 00 and n−1n-1 cannot both occur: a vertex adjacent to every other vertex cannot coexist with an isolated vertex. Thus at most n−1n-1 degree values are available for nn vertices, forcing a repetition.

This example illustrates an important technique: structural constraints can reduce the number of available boxes below the initially apparent count.

Computing and information limits

In computer science, a function mapping a larger finite input set into a smaller output set must map some distinct inputs to the same output. Such an event is called a collision. For example, a hash function with bb-bit outputs has only 2b2^b possible output values. If its input domain contains more than 2b2^b elements, collisions necessarily exist.

The same counting argument limits lossless compression. There are 2n2^n binary strings of length nn, but only

1+2+⋯+2n−1=2n−11+2+\cdots+2^{n-1}=2^n-1

binary strings of length strictly less than nn, including the empty string. A lossless encoding must assign distinct inputs distinct representations. Consequently, no encoding can shorten every nn-bit string while preserving recoverability from the representation alone.

These are existence and impossibility results, not efficiency claims. Proving that a collision exists does not establish that it can be found quickly.

Infinite versions and limitations

An infinite set partitioned into finitely many classes must have at least one infinite class. Otherwise, every class would be finite, and their finite union would also be finite. This statement is often called the infinite pigeonhole principle.

The requirement of finitely many classes matters. Infinitely many objects can be assigned to infinitely many boxes with exactly one object per box. Likewise, infinite sets do not obey every finite intuition: an infinite set can have the same cardinality as a proper subset of itself. For instance, n↦n+1n\mapsto n+1 injectively maps the nonnegative integers onto the positive integers.

The finite principle also does not require probability or random assignment. Its conclusions hold for every permitted arrangement. Conversely, it does not ordinarily identify which objects coincide or how many coincidences occur beyond the stated bound. Stronger conclusions require additional information about the distribution or structure of the objects.

Historical terminology

The principle is closely associated with the nineteenth-century mathematician Peter Gustav Lejeune Dirichlet, who used it in number theory. The names Dirichlet's box principle and drawer principle emphasize the same allocation argument as the English expression pigeonhole principle.

The shorter name Dirichlet's principle is ambiguous: it also refers to a distinct variational principle concerning harmonic functions and boundary-value problems. “Pigeonhole principle” or “Dirichlet's box principle” avoids that ambiguity.