Pigeonhole Principle

Basic Pigeonhole Principle

If $n + 1$ or more pigeons are placed in $n$ pigeonholes, then at least one pigeonhole contains two or more pigeons.

More generally: If $n$ objects are placed into $k$ boxes where $n > k$, then at least one box contains more than one object.

Generalized Pigeonhole Principle

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

$\text{At least one box has } \geq \left\lceil \frac{N}{k} \right\rceil \text{ objects}$

Example: Among 100 people, at least $\lceil 100/12 \rceil = 9$ were born in the same month.

Classic Examples

Birthday Problem Setup

Among any 367 people, at least 2 share a birthday. (366 possible birthdays + 1 extra person)

Handshake Problem

At any party, at least two people have shaken the same number of hands.

Proof: With $n$ people, possible handshakes per person: $0, 1, 2, \ldots, n-1$ (that's $n$ values). But 0 and $n-1$ can't both occur (someone shook everyone vs. someone shook no one). So only $n-1$ distinct values are possible for $n$ people. By pigeonhole, two people have the same count.

Subset Sum Problem

Among any $n+1$ integers, two have the same remainder mod $n$.

Proof: Only $n$ possible remainders: $0, 1, \ldots, n-1$. With $n+1$ integers, by pigeonhole, two share a remainder.

Existence Proofs

Rational Approximation

For any irrational $x$ and positive integer $n$, there exists a rational $p/q$ with $1 \leq q \leq n$ such that: $\left| x - \frac{p}{q} \right| < \frac{1}{nq}$

Proof Idea: Consider $\{kx\}$ (fractional parts) for $k = 0, 1, \ldots, n$. Divide $[0, 1)$ into $n$ intervals of length $1/n$. By pigeonhole, two fractional parts are in the same interval.

Sequence Problems

In any sequence of $n^2 + 1$ distinct real numbers, there's an increasing or decreasing subsequence of length $n + 1$.

Proof (Erdős–Szekeres Theorem): For each element $a_i$, let $L_i$ = length of longest increasing subsequence ending at $a_i$. If no $L_i > n$, then $L_i \in \{1, 2, \ldots, n\}$. With $n^2 + 1$ elements and $n$ possible values, by pigeonhole, $n + 1$ elements share the same $L_i$ value. These must form a decreasing subsequence.

Arithmetic Progressions

Three-Term AP

Among any $n + 1$ integers in $\{1, 2, \ldots, 2n\}$, there exist two whose sum is $2n + 1$.

Proof: Pair up: $(1, 2n), (2, 2n-1), \ldots, (n, n+1)$. With $n + 1$ numbers and $n$ pairs, by pigeonhole, two numbers are from the same pair.

Graph Theory Applications

Friendship Theorem

In any group of 6 people, either 3 mutually know each other or 3 mutually don't know each other.

Proof: Consider one person A. They either know ≥ 3 or don't know ≥ 3 others.

Case 1: A knows B, C, D.

• If any two of B, C, D know each other, we have 3 mutual friends.
• If none of B, C, D know each other, they're 3 mutual strangers.

Case 2: Similar analysis for A not knowing 3 people.

This is a special case of Ramsey's Theorem: $R(3,3) = 6$.

Tips for Applying Pigeonhole

1. Identify the pigeons: What objects are being distributed?
2. Identify the pigeonholes: What categories/boxes are they going into?
3. Count carefully: Ensure pigeons > pigeonholes (or use generalized version).
4. Consider remainders: Modular arithmetic often creates pigeonholes.
5. Fractional parts: $\{x\} = x - \lfloor x \rfloor$ often helps for real numbers.

Common Pitfalls

Wrong direction: The principle guarantees at least one pigeonhole has many pigeons, not that all do.

Constructive vs. Existence: Pigeonhole proves existence but doesn't always tell you which pigeonhole.

Related Concepts

Strong Pigeonhole

Average number of objects per box is $N/k$. At least one box must meet or exceed this average.

Probabilistic Method

Extension: If average is $\mu$, then:

• Something is $\geq \mu$
• Something is $\leq \mu$