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

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

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