# Dirichlet's Box Principle/Corollary

< Dirichlet's Box Principle(Redirected from Pigeonhole Principle)

Jump to navigation
Jump to search
## Corollary to Dirichlet's Box Principle

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

A direct application of the Dirichlet's Box Principle.

$\blacksquare$

## Also known as

**Dirichlet's Box Principle**, in particular its corollary, is also commonly known as the **pigeonhole principle** or **pigeon-hole principle:**

- 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.

It is also known as **(Dirichlet's) drawer (or shelf) principle**.

Some sources give it as the **letterbox principle** or **letter-box principle**.

## Sources

- 1966: Richard A. Dean:
*Elements of Abstract Algebra*... (previous) ... (next): $\S 0.6$: Theorem $9$ - 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 10.18$ - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**pigeonhole principle** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**pigeonhole principle** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**Pigeonhole Principle**

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