The Pigeonhole Principle: Simple Statement, Surprising Proofs

The pigeonhole principle says that if 10 pigeons fly into 9 holes, some hole gets at least two pigeons. Applied Discrete Structures calls it an obvious, common-sense statement with numerous applications, and adds a warning that applies to the rest of this guide: never underestimate the importance of simple ideas. Used with the right choice of "holes", it proves results that look nothing like pigeons.

The statement and its proof

Pigeonhole principle. If more than n objects are placed into n boxes, at least one box contains at least two objects.

Levin's Discrete Mathematics: An Open Introduction proves it by contradiction in two lines. Suppose every box contained at most one object. Then there would be at most n objects, but there are more than n. So some box holds at least two.

Generalised version. If N objects go into n boxes, some box contains at least ⌈N/n⌉ objects (N/n rounded up). If every box had fewer, the total would be at most n(⌈N/n⌉ − 1), which is less than N. Applied Discrete Structures states it for functions: if f maps a finite set X to a finite set Y and |X| > k|Y|, some element of Y is the image of at least k + 1 elements of X.

That function version gives a useful translation: no function from a larger finite set to a smaller one can be one-to-one. The injective, surjective and bijective guide uses it.

Seven examples, from easy to clever

1. Birth months. Among 13 people, two share a birth month: 13 people, 12 months. Among 25 people, at least ⌈25/12⌉ = 3 share one. Note what is not claimed: nothing says which month, or that any month is empty.

2. Socks in the dark. A drawer holds black and white socks. How many must you take to be sure of a matching pair? Three. The boxes are the two colours; three socks in two colours force a pair. Two socks are not enough, since one could be each colour.

3. Pairs that sum to 11. Choose any 6 numbers from 1 to 10. Then two of them add up to 11. The trick is the boxes: {1, 10}, {2, 9}, {3, 8}, {4, 7}, {5, 6}. Each number lies in exactly one box, and 6 numbers in 5 boxes put two in the same box, which sum to 11. With only 5 numbers it can fail: 1, 2, 3, 4, 5.

4. Differences divisible by 7. Among any 8 integers, two have a difference divisible by 7. Boxes: the remainders 0 to 6 on division by 7. Eight integers, seven remainders, so two share a remainder, and integers with the same remainder differ by a multiple of 7. This remainder trick is everywhere in number theory; modular arithmetic explains why equal remainders mean the difference is divisible.

5. Points in a square. Place 5 points anywhere in a 1-by-1 square. Then two of them are at most √2/2 ≈ 0.707 apart. Boxes: cut the square into four 1/2-by-1/2 squares. Five points in four small squares put two in the same one, and two points in a square of side 1/2 are at most its diagonal, √2/2, apart.

6. Handshakes at a party. At any party of n ≥ 2 people, two people shook the same number of hands. Each person shook between 0 and n − 1 hands, n possible values. But 0 and n − 1 cannot both occur: someone who shook everyone's hand rules out someone who shook nobody's. So the n people have at most n − 1 possible values, and two share one. In graph terms, every simple graph with at least two vertices has two vertices of equal degree.

7. Compression. No lossless compression program can make every file shorter. There are 2ⁿ files of exactly n bits, but only 2ⁿ − 1 files shorter than n bits (2⁰ + 2¹ + ⋯ + 2ⁿ⁻¹). If every n-bit file were mapped to a shorter one, two different files would share a compressed form and could not both be recovered. So any lossless compressor that shortens some files must leave others the same length or make them longer.