Pigeonhole and Inclusion-Exclusion - Applications

The Pigeonhole Principle, despite its elementary statement, has profound applications across mathematics. We present a formal statement and proof of one of its most powerful forms.

DefinitionGeneralized Pigeonhole Principle

If $n$ objects are distributed into $k$ boxes, then at least one box contains at least $\lceil n/k \rceil$ objects.

Proof by Contradiction:

Assume, for contradiction, that every box contains fewer than $\lceil n/k \rceil$ objects. Then each box contains at most $\lceil n/k \rceil - 1$ objects.

Since $\lceil n/k \rceil$ is the smallest integer greater than or equal to $n/k$ , we have $\lceil n/k \rceil - 1 < n/k$ .

Therefore, the total number of objects is at most: $k \cdot (\lceil n/k \rceil - 1) < k \cdot (n/k) = n$

This contradicts the assumption that there are $n$ objects. Therefore, at least one box must contain at least $\lceil n/k \rceil$ objects. $\square$

ExampleDirichlet's Approximation Theorem

For any irrational number $\alpha$ and any positive integer $N$ , there exist integers $p$ and $q$ with $1 \leq q \leq N$ such that: $\left|\alpha - \frac{p}{q}\right| < \frac{1}{qN}$

Proof: Consider the $N+1$ numbers $0, \{\alpha\}, \{2\alpha\}, \ldots, \{N\alpha\}$ , where $\{x\}$ denotes the fractional part of $x$ (i.e., $\{x\} = x - \lfloor x \rfloor$ ).

Divide the interval $[0,1]$ into $N$ subintervals: $[0, 1/N), [1/N, 2/N), \ldots, [(N-1)/N, 1)$ .

By the pigeonhole principle, at least two of these $N+1$ fractional parts must lie in the same subinterval. Say $\{j\alpha\}$ and $\{k\alpha\}$ lie in the same subinterval, where $0 \leq k < j \leq N$ .

Then $|\{j\alpha\} - \{k\alpha\}| < 1/N$ , which means $|j\alpha - k\alpha - (m - n)| < 1/N$ for some integers $m$ and $n$ .

Let $q = j - k$ (so $1 \leq q \leq N$ ) and $p = m - n$ . Then: $|q\alpha - p| < \frac{1}{N}$

Dividing by $q$ : $\left|\alpha - \frac{p}{q}\right| < \frac{1}{qN}$

This proves the theorem. $\square$

This application shows how the pigeonhole principle provides existence proofs for good rational approximations to irrational numbers, a fundamental result in number theory.

DefinitionRamsey's Theorem (Finite Version)

For any positive integers $r$ and $s$ , there exists a least positive integer $R(r,s)$ such that any graph on $R(r,s)$ vertices contains either a clique of size $r$ or an independent set of size $s$ .

The pigeonhole principle proves the base case: $R(2,s) = s$ .

Proof of $R(2,s) = s$ :

Consider any graph $G$ on $s$ vertices. For any vertex $v$ :

If $v$ has at least one neighbor, then $v$ and that neighbor form a clique of size 2 (an edge).
If $v$ has no neighbors, then $v$ alone forms an independent set of size 1.

By the pigeonhole principle, either there exists an edge (clique of size 2), or all $s$ vertices are isolated (independent set of size $s$ ).

For the general case $R(r,s) \leq R(r-1,s) + R(r,s-1)$ , we also use pigeonhole reasoning on the neighborhood of a vertex. $\square$

Remark

The pigeonhole principle is the foundation for Ramsey theory, which studies unavoidable patterns in large structures. The famous result that $R(3,3) = 6$ means that in any group of 6 people, there are either 3 mutual acquaintances or 3 mutual strangers. Computing exact Ramsey numbers remains one of the great challenges in combinatorics, with $R(5,5)$ still unknown (though bounded between 43 and 48).