The Generalized Pigeonhole Principle

Recall from The Pigeonhole Principle page that we saw that if $A$ is a finite set with $m$ elements and $A_1, A_2, ..., A_n$ are subsets of $A$ that form a partition of $A$ and if $n < m$ then there exists at least one subset $A_i$ where $i \in \{1, 2, ..., n \}$ such that $\lvert A_i \rvert > 1$.

We will now generalize the pigeonhole principle in terms of sets.

Theorem 1 (The Generalized Pigeonhole Principle): Let $p_1, p_2, ..., p_n$ be positive integers and let $A$ be a finite set with $p_1 + p_2 + ... + p_n - n + 1 = \left ( \sum_{i=1}^{n} p_i \right ) - n + 1$ elements and $A_1, A_2, ..., A_n$ are subsets of $A$ that form a partition of $A$ then for some $i \in \{1, 2, ..., n \}$ we have that $\lvert A_i \rvert \geq p_i$.

Note that the basic pigeonhole principle arises when $p_1 = p_2 = ... = p_n = 2$.

• Proof: We will prove Theorem 1 by contradiction. Let $p_1, p_2, ..., p_n$ be positive integers and let $A$ be a finite set such that:

(1)

\begin{align} \quad \lvert A \rvert = p_1 + p_2 + ... + p_n - n + 1 \end{align}

• Furthermore, let $A_1, A_2, ..., A_n$ be subsets of $A$ that form a partition of $A$. Suppose that for each $\in \{ 1, 2, ..., n \}$ we instead have that $\lvert A_i \rvert < p_i$. Then for each $i$ that $\lvert A_i \rvert \leq p_i - 1$. By the addition principle this implies that:

(2)

\begin{align} \quad \lvert A \rvert = \lvert A_1 \rvert + \lvert A_2 \rvert + ... + \lvert A_n \rvert \\ \quad \lvert A \rvert \leq (p_1 - 1) + (p_2 - 1) + ... + (p_n - 1) \\ \quad \lvert A \rvert \leq p_1 + p_2 + ... + p_n - n \\ \end{align}

• The inequality above implies that $1 \leq 0$ which is a contradiction. Therefore assumption that $\lvert A_i \rvert < p_i$ for each $i = 1, 2, ..., n$ was false and so there exists some $i \in \{1, 2, ..., n \}$ such that $\lvert A_i \rvert \geq p_i$. $\blacksquare$

For an example of Theorem 1 above, consider the $n = 3$ positive integers $p_1 = 2$, $p_2 = 4$, and $p_3 = 5$. Let $A$ be a set containing $p_1 + p_2 + p_3 - n + 1 = 2 + 4 + 5 -3 + 1 = 9$ elements. Then $A$ is of the form:

(3)

\begin{align} \quad A = \{r, s, t, u, v, w, x, y, z \} \end{align}

Now let $A_1$, $A_2$, and $A_3$ be subsets of $A$ that form a partition of $A$, and suppose that $\lvert A_1 \rvert < p_1 = 2$, $\lvert A_2 \rvert < p_2 = 4$, and $\lvert A_3 \rvert < p_3 = 5$. Then $A_1$ has at most $1$ element, $A_2$ has at most $3$ elements, and $A_3$ has at most $4$ elements, and so by the principle of addition:

(4)

\begin{align} \quad \lvert A \rvert = \biggr \lvert \bigcup_{i=1}^{3} A_i \biggr \rvert = \lvert A_1 \cup A_2 \cup A_3 \rvert \leq 8 \end{align}

However, we know that $\lvert A \rvert = 9$ and so as we can see, a contradiction arises.

The following corollary is an important case of the generalized pigeonhole principle.

Corollary 1: If $n(r - 1) + 1$ objects are placed in $n$ groups then there exists a group with at least $r$ objects.

• Proof: We will prove Corollary 1 in terms of sets. Let $p_1, p_2, ..., p_n$ be $n$ positive integers such that $p_1 = p_2 = ... = p_n = r$. Consider a set $A$ with $p_1 + p_2 + ... + p_n - n + 1 = nr - n + 1 = n(r - 1) + 1$ elements in it, and consider a collection of subsets $A_1, A_2, ..., A_n$ that form a partition of $A$. Then by the Generalized Pigeonhole Principle we have that for some $i \in \{1, 2, ..., k \}$ that $\lvert A_i \rvert \geq r$. $\blacksquare$