# 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:

where $\ceiling {\, \cdot \,}$ 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

Aiming for a contradiction, suppose no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements.

Then the maximum number of elements of any $S_i$ would be $\ceiling {\dfrac n k} - 1$.

So the total number of elements of $S$ would be no more than $k \paren {\ceiling {\dfrac n k} - 1} = k \ceiling {\dfrac n k} - k$.

There are two cases:

Suppose $k \divides n$.

Then $\ceiling {\dfrac n k} = \dfrac n k$ is an integer and:

- $k \ceiling {\dfrac n k} - k = n - k$

Thus:

- $\displaystyle \card S = \sum_{i \mathop = 1}^k \card {S_i} \le n - k < n$

This contradicts the fact that $\card S = n$.

Hence our assumption that no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements was false.

Next, suppose that $k \nmid n$.

Then:

- $\card S = k \ceiling {\dfrac n k} - k < \dfrac {k \paren {n + k} } k - k = n$

and again this contradicts the fact that $\card S = n$.

In the same way, our assumption that no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements was false.

Hence, by Proof by Contradiction, there has to be at least $\ceiling {\dfrac n k}$ elements in at least one $S_i \subseteq S$.

$\blacksquare$

## 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 $2$ pigeons.

## Historical Note

The **Pigeonhole Principle** appeared in print as early as $1622$ in *Selectæ Propositiones in Tota Sparsim Mathematica Pulcherrimæ* by Jean Leurechon.

It also appears, in greater detail, in the $1624$ work *Récréations Mathématiques* by "H. van Etten", also commonly attributed to Jean Leurechon.

However, it is commonly called **Dirichlet's Box (or Drawer) Principle**, after an $1834$ treatment by Johann Peter Gustav Lejeune Dirichlet, who called it the **Schubfachprinzip** (**drawer principle** or **shelf principle**).

In Russian and some other languages, it is known as the **Dirichlet principle** or **Dirichlet's principle**, which name ambiguously also refers to the minimum principle for harmonic functions.

It is usually seen in its simplest form: if you have $N + 1$ objects to put into $N$ pigeonholes, at least one pigeonhole contains $2$ objects.

## Also see

## Sources

- 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 10.18$ - 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.2$: Isomorphic Graphs - 1992: David Wells:
*Curious and Interesting Puzzles*... (previous) ... (next): Henry van Etten: $124$ - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next): Entry:**Dirichlet's principle** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**Dirichlet's principle** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**Pigeonhole Principle**

- Weisstein, Eric W. "Dirichlet's Box Principle." From
*MathWorld*--A Wolfram Web Resource. http://mathworld.wolfram.com/DirichletsBoxPrinciple.html