Pigeonhole Principle

From ProofWiki
Jump to navigation Jump to search

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 $\ceiling {\dfrac n k}$ elements

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:

$n$ is divisible by $k$
$n$ is not divisible by $k$.


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

Retrieved from "https://proofwiki.org/w/index.php?title=Pigeonhole_Principle&oldid=465087"