Pigeonhole Principle

The Pigeonhole Principle (also known as Dirichlet's box principle) is a deceptively simple yet incredibly powerful tool in combinatorics. It states that if you have more objects than containers, at least one container must hold more than one object.

Basic Statement

Theorem: If $n+1$ or more objects are placed into $n$ boxes, then at least one box contains two or more objects.

More generally: If $kn+1$ objects are placed into $n$ boxes, then at least one box contains $k+1$ or more objects.

The Generalized Pigeonhole Principle

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

(Here $\lceil x\rceil$ denotes the ceiling function—the smallest integer $\ge x$.)

Classic Examples

1. Birthday Problem (Weak Form)

In any group of 367 people, at least two share a birthday.

Why? There are only 366 possible birthdays (including Feb 29), so by pigeonhole, with 367 people, at least two share the same birthday.

2. Handshake Problem

At a party of $n\ge 2$ people, at least two people have the same number of friends at the party.

Proof: Each person can have $0,1,2,\dots ,n-1$ friends (n possibilities). But if someone has 0 friends, then no one has $n-1$ friends (and vice versa). So there are really only $n-1$ possible values for $n$ people. By pigeonhole, two people have the same count.

3. Subset Sum Problem

Among any 10 distinct integers from 1 to 100, there exist two disjoint non-empty subsets with equal sums.

Proof: There are $2^{10}-1=1023$ non-empty subsets. The maximum possible sum is at most $91+92+\cdots +100=955$. So the possible sums range from 1 to 955 (at most 955 values). Since $1023>955$, two subsets have the same sum. If they share elements, remove common elements to get disjoint subsets with equal sums.

Olympiad Techniques

1. Residue Classes

Many pigeonhole problems involve modular arithmetic.

Example: Prove that among any $n+1$ integers, two of them are congruent modulo $n$.

Solution: There are only $n$ residue classes modulo $n$: $\{0,1,2,\dots ,n-1\}$. With $n+1$ integers, by pigeonhole, two fall in the same class.

2. Continuous Pigeonhole

For problems on the real line or plane:

Example: Given 5 points inside a unit square, prove that some two are at distance $\le \frac{\sqrt{2}}{2}$.

Solution: Divide the unit square into 4 smaller squares of side $\frac{1}{2}$. By pigeonhole, at least 2 of the 5 points lie in the same small square. The maximum distance within a small square is its diagonal: $\frac{\sqrt{2}}{2}$.

3. Covering Arguments

Example: Color each integer from 1 to 2n with one of n colors. Prove some two consecutive integers have the same color.

Solution: Consider the $n$ pairs $(1,2),(3,4),\dots ,(2n-1,2n)$. If no two consecutive integers share a color, then each pair uses two different colors. But we only have $n$ colors for $2n$ numbers... wait, this needs a different approach.

Actually: There are $2n-1$ consecutive pairs: $(1,2),(2,3),\dots ,(2n-1,2n)$. If no pair has the same color, consider alternating colors along $1,2,3,\dots ,2n$. With only $n$ colors and $2n$ numbers, by pigeonhole, some two numbers share a color. If they're at positions $i$ and $j$ with same color $c$, and $j-i$ is odd, then there must be two adjacent numbers with the same color between them.

Practice Problems

1. Prove that among any 52 integers, there exist two whose difference is divisible by 51.

1. Given 5 lattice points in the plane, prove that some pair has midpoint that is also a lattice point.

1. (IMO 1972) Prove that from any 10 distinct two-digit numbers, one can select two disjoint subsets with equal sums.

1. Among 51 points inside a $10\times 10$ square, prove that some 3 can be covered by a unit circle.