# 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