Dirichlet's Box Principle/Corollary

From ProofWiki
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