# 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 \sum_{i \mathop = 1}^k \card {S_i} \le n - k < n$

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

Next, suppose that $k \nmid n$.

Then:

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

and again this contradicts our assumption that no subset $S_i$ of $S$ has as many as $\ceiling {\dfrac n k}$ elements.

Either way, 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** has been attributed to Johann Peter Gustav 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** or **Dirichlet's principle**, which name ambiguously also refers to the minimum principle for harmonic functions.

## 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): $\S 2.2$: Isomorphic Graphs: Problem $23$ - 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