Pigeonhole Principle

Introduction

The pigeonhole principle is one of the simplest yet most powerful tools in combinatorics. Its statement is almost trivial: if you have more pigeons than pigeonholes and each pigeon must go into a hole, then at least one hole contains more than one pigeon. Yet this elementary observation leads to surprisingly deep results across mathematics.

The principle, also known as Dirichlet's box principle, was formalized by Peter Gustav Lejeune Dirichlet in 1834. It provides existence proofs—showing that certain configurations must exist—without constructing them explicitly. This makes it invaluable when direct construction is difficult or impossible.

Applications range from number theory and combinatorics to computer science and everyday reasoning. The principle appears in proofs about rational approximations, graph coloring, data compression, and countless other areas.

Statement of the Principle

Simple Form

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

If |A|>|B|, then no injection ƒ:A→B exists.

Equivalently: if ƒ:A→B and |A|>|B|, then ƒ is not injective (one-to-one), meaning some element of B is hit by at least two elements of A.

Generalized Form

If n objects are placed into k boxes, then at least one box contains at least ⌈n/k⌉ objects.

At least on box has ≥[n/k] objects.

This follows from the simple form: if every box had fewer than ⌈n/k⌉ objects, the total would be at most
k⋅([n/k]−1)<n, a contradiction.

Strong Form

If (n_1)+(n_2)+⋯+(n_k)−k+1 objects are placed into k boxes, then either box 1 contains at least (n_1) objects, or box 2 contains at least (n_2) objects, …, or box k contains at least (n_k) objects.

The simple form is the special case where all (n_i)=2.

Basic Examples

Example 1: Birthdays

In any group of 367 people, at least two share a birthday (ignoring leap years). Here the pigeons are people (367) and the holes are days of the year (366).

More strongly: in a group of 23 people, the probability that two share a birthday exceeds 50%. This is the famous birthday paradox.

Example 2: Hair Count

The average human head has about 150000 hairs, and no one has more than 500000. In a city of 1 million people, at least two people have exactly the same number of hairs on their head.

Pigeons: 1,000000 people. Holes: 500001 possible hair counts (0 to 500000). Since 1000000 > 500001, at least two people share a hair count.

Example 3: Socks in the Dark

A drawer contains red and blue socks. What is the minimum number of socks you must draw (without looking) to guarantee a matching pair?

Answer: 3 socks. With 2 colors and 3 socks, at least two must be the same color. By the pigeonhole principle with k=2 holes and n=3 objects, [3/2]=2 socks must share a color.

Applications in Number Theory

Divisibility Result

Among any n+1 integers, at least two have the same remainder when divided by n.

There are only n possible remainders: 0,1,2,…,n−1. With n+1 integers and n remainders, two integers must share a remainder, so their difference is divisible by n.

Subsequence Sum Divisibility

Given any n integers, some nonempty subset has a sum divisible by n.

Consider the partial sums (S_0)=0,(S_1)=(a_1), (S_2)=(a_1)+(a_2),…, (S_n)=(a_1)+⋯+(a_n).
These n+1 sums have remainders modulo n from the set {0,1,…,n−1}.

If any (S_i) has remainder 0, we are done. Otherwise, by pigeonhole, two partial sums (S_i) and (S_j) (with i<j) have the same remainder. Then (S_j)−(S_i)=(a_i+1)+⋯+(a_j) is divisible by n.

Dirichlet's Approximation Theorem

For any real number α and positive integer n, there exist integers p and q with 1≤q≤n such that:

|α−p/q|<1/(q*n)

The proof uses the pigeonhole principle on the fractional parts of
0,α,2*α,…,n*α. These n+1 numbers lie in [0,1), which we divide into n intervals of length 1/n. Two must fall in the same interval.

Applications in Combinatorics

Monotone Subsequences

Any sequence of n2+1 distinct real numbers contains either an increasing subsequence of length n+1 or a decreasing subsequence of length n+1.

Label each element with the length of the longest increasing subsequence starting from it. If all labels are at most n, there are only n possible labels for n2+1 elements. By pigeonhole, at least n+1 elements share the same label.

If these elements with the same label form an increasing subsequence, we get a contradiction. So they must form a decreasing subsequence of length n+1.

Ramsey-Type Results

In any 2-coloring of the edges of (K_6) (complete graph on 6 vertices), there exists a monochromatic triangle.

Consider any vertex v. It has 5 edges, colored red or blue. By pigeonhole, at least 3 edges have the same color, say red. Let these connect v to vertices a,b,c.

If any edge among a,b,c is red, we have a red triangle. If all edges among a,b,c are blue, we have a blue triangle. Either way, a monochromatic triangle exists.

Applications in Computer Science

Hash Collisions

If a hash function maps n items to m buckets where n>m, at least one bucket must contain multiple items (a collision). This is why hash tables must handle collisions.

Data Compression Limits

No lossless compression algorithm can compress all files of length n bits. There are 2 possible inputs but only 2−1 possible outputs shorter than n bits. By pigeonhole, two inputs must map to the same output, making decompression ambiguous.

Load Balancing

If n tasks are distributed among k servers, at least one server handles at least
⌈n/k⌉ tasks. This lower bound on maximum load is unavoidable regardless of the distribution strategy.

The Probabilistic Pigeonhole

The principle has a probabilistic analog: if n items are randomly placed into k boxes, the expected number of items in a box is n/k. By linearity of expectation, at least one box must have at least the average ⌈n/k⌉ items.

This connects to the probabilistic method in combinatorics, which uses expected value arguments to prove existence results.

Connection to Other Concepts

The pigeonhole principle is a special case of cardinality arguments about finite sets. It formalizes the intuition that injections can only exist between sets of appropriate sizes.

In combinatorics, it underlies Ramsey theory, which studies conditions guaranteeing the existence of order in large structures. The friendship theorem and the Happy Ending Problem are examples.

In number theory, it provides approximation theorems (Dirichlet) and results about quadratic residues. In analysis, it appears in proofs about measure and cardinality.

In computer science, it explains fundamental limits on hashing, compression, and resource allocation. It also underlies the birthday attack in cryptography.

Summary

The pigeonhole principle states that if n+1 objects are placed into n boxes, at least one box contains at least two objects. More generally, n objects in k boxes means some box has at least ⌈n/k⌉ objects.

Though simple, the principle has far-reaching applications. In number theory, it proves results about remainders, rational approximations (Dirichlet), and divisibility. In combinatorics, it establishes the existence of monotone subsequences and monochromatic subgraphs.

In computer science, it explains hash collisions, compression limits, and load balancing lower bounds. The principle provides existence proofs without explicit construction.

The power of the pigeonhole principle lies not in its statement but in identifying the right pigeons and holes for a given problem. Finding clever applications requires insight into the structure of the problem at hand.

The principle extends to infinite sets via cardinality comparisons. If there is no injection from A to B, then |A|>|B|. Cantor's diagonal argument, which proves the uncountability of the reals, is a sophisticated application of this idea.

Many competition mathematics problems rely on the pigeonhole principle. The key challenge is always the same: identify what the pigeons are, what the pigeonholes are, and why the count guarantees the desired conclusion.

Despite its elementary nature, the pigeonhole principle remains indispensable in modern mathematics and computer science. It reminds us that sometimes the simplest observations lead to the most profound results.