Pigeonhole Principle
Theorem
Let $S$ be a finite set whose cardinality is $n$.
Let $S_1, S_2, \ldots, S_k$ be a partition of $S$ into $k$ subsets.
Then at least one subset $S_i$ of $S$ contains at least $\left \lceil {n/k} \right \rceil$ elements
where $\left \lceil {\cdot} \right \rceil$ denotes the ceiling function.
Corollary
If a set of $n$ distinct objects is partitioned into $k$ subsets, where $0 < k < n$, then at least one subset must contain at least two elements.
Proof
Suppose this were not the case, and no subset $S_i$ of $S$ has as many as $\left \lceil {n/k} \right \rceil$ elements.
Then the maximum number of elements of any $S_i$ would be $\left \lceil {n/k} \right \rceil - 1$.
So the total number of elements of $S$ would be no more than $k \left({\left \lceil {n/k} \right \rceil - 1}\right) = k \left \lceil {n/k} \right \rceil - k$.
There are two cases:
Suppose $k \mathop \backslash n$.
Then $\left \lceil {\dfrac n k} \right \rceil = \dfrac n k$ is an integer and $k \left \lceil {n/k} \right \rceil - k = n - k$.
Thus $\displaystyle \sum_{i \mathop = 1}^k \left \vert {S_i}\right \vert \le n-k < n$.
This contradicts our assumption that no subset $S_i$ of $S$ has as many as $\left \lceil {n/k} \right \rceil$ elements.
Next, suppose that $k \nmid n$.
Then:
- $k \left \lceil {n/k} \right \rceil - k < \dfrac {k \left({n+k}\right)} k - k = n$
and again this contradicts our assumption that no subset $S_i$ of $S$ has as many as $\left \lceil {n/k} \right \rceil$ elements.
Either way, there has to be at least $\left \lceil {n/k} \right \rceil$ elements in at least one $S_i \subseteq S$.
$\blacksquare$
Historical Note
This principle has been attributed to Johann Lejeune Dirichlet.
It is also known as Dirichlet's Box (or Drawer) Principle, or, as Dirichlet named it, Schubfachprinzip (drawer principle or shelf principle).
In Russian and some other languages, it is known as the Dirichlet principle, which name ambiguously also refers to the minimum principle for harmonic functions.
Source of Name
It is known as the Pigeonhole Principle because of the following.
Suppose you have $n + 1$ pigeons, but have only $n$ holes for them to stay in. By the Pigeonhole Principle at least one of the holes houses two pigeons.
Sources
- Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory (1971): $\S 10.18$
- Gary Chartrand: Introductory Graph Theory (1977)... (previous)... (next): $\S 2.2$: Isomorphic Graphs: Problem $23$
- Weisstein, Eric W. "Dirichlet's Box Principle." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DirichletsBoxPrinciple.html
