Discrete Math › Section D · Counting › Topic D.9
The pigeonhole principle
Put more objects than boxes and some box must hold two. That almost obvious fact proves that collisions are unavoidable in hash tables, that no compression program can shrink every file, and many other results that feel surprising.
Guaranteed collisions
Most counting asks how many ways something can happen. The pigeonhole principle asks a different question: what must happen, however the choices fall? A drawer holds black and grey socks mixed together, and you pull socks out in the dark. You cannot know which colours you will get, yet three socks are certain to include a matching pair, because three socks cannot all have different colours when only two colours exist. The principle is named after pigeons crowding into nesting holes, and it is a tool for existence proofs: it shows that something must occur without saying where or how to find it.
The basic principle
If more than \(k\) objects are placed into \(k\) boxes, then at least one box contains at least two objects. The proof is by contradiction. Suppose every box held at most one object. Then there would be at most \(k\) objects in total, contradicting the fact that there are more than \(k\). In the language of functions, from "Combinations and permutations": if \(|A| > |B|\), no function \(f: A \to B\) is injective, because two elements of \(A\) must share an image. The real skill is choosing what the objects and the boxes are. Once they are named well, the argument usually takes one line.
The generalised principle
If \(N\) objects are placed into \(k\) boxes, some box contains at least \(\lceil N/k \rceil\) objects. Here \(\lceil x \rceil\), the ceiling of \(x\), is the smallest integer greater than or equal to \(x\), so \(\lceil 4.1 \rceil = 5\) and \(\lceil 4 \rceil = 4\). The proof again uses contradiction: if every box held at most \(\lceil N/k \rceil - 1\) objects, which is less than \(N/k\), the total would be less than \(k \cdot \frac{N}{k} = N\). Among 200 students, some birth month is shared by at least \(\lceil 200/12 \rceil = 17\) students, since 12 months with at most 16 each would hold only 192.
How many objects force a pile?
Turned around, the principle answers "how many must I take?". To guarantee \(m\) objects in one of \(k\) boxes, you need \(k(m - 1) + 1\) objects. Fewer is not enough: \(k(m - 1)\) objects can sit exactly \(m - 1\) in each box. A drawer holds socks in 4 colours. To be sure of 3 socks of one colour, take \(4 \cdot 2 + 1 = 9\). Eight could be two of each colour, so 9 is the smallest number that works. Every pigeonhole answer has these two halves: a proof that the number suffices, and an example showing that one fewer does not.
Worked example: a pair that sums to 13
Show that any 7 numbers chosen from 1 to 12 include two that add up to 13. 1. Boxes: group the numbers into pairs with sum 13: \(\{1, 12\}\), \(\{2, 11\}\), \(\{3, 10\}\), \(\{4, 9\}\), \(\{5, 8\}\) and \(\{6, 7\}\). 2. These 6 boxes contain every number from 1 to 12 exactly once. 3. Objects: the 7 chosen numbers. With 7 objects in 6 boxes, some box receives two, and the two numbers in any box sum to 13. 4. Sharpness: the 6 numbers 1 to 6 contain no such pair, so 7 is the smallest number that guarantees one. A computer check of all \(\binom{12}{7} = 792\) choices agrees.
Worked example: points in a square
Five points are placed anywhere inside a square of side 2. Show that two of them are at most \(\sqrt{2}\) apart. 1. Boxes: cut the square into four squares of side 1, using the lines through its centre. 2. Five points in four small squares put at least two points in one small square, counting points on a dividing line as belonging to either neighbour. 3. Two points in a square of side 1 are at most a diagonal apart, and the diagonal has length \(\sqrt{1^2 + 1^2} = \sqrt{2}\). 4. So two points lie within \(\sqrt{2}\) of each other. Notice that the proof says nothing about which two points they are.
Remainders and friendships
Remainders make natural boxes. Among any 8 integers, two differ by a multiple of 7: division by 7 leaves only 7 possible remainders, 0 to 6, so two of the integers share a remainder, and their difference is divisible by 7. A subtler example: in any group of \(n \ge 2\) people, two have the same number of friends within the group, assuming friendship goes both ways. Each person has between 0 and \(n - 1\) friends, which looks like \(n\) boxes. But 0 and \(n - 1\) cannot both occur, since someone friends with everyone leaves nobody friendless. So only \(n - 1\) boxes are really available for \(n\) people.
Pigeonholes in computing
A hash function maps a huge set of possible keys, such as all strings, to a small set of table slots. Since there are more keys than slots, collisions are unavoidable, and a good table must handle them rather than hope they never happen. Storing 500 keys in 64 slots puts at least \(\lceil 500/64 \rceil = 8\) keys in some slot. Compression is another case. A lossless compressor must turn different files into different outputs, or decompression could not recover them. There are \(2^8 = 256\) files of exactly 8 bits, but only \(1 + 2 + 4 + \cdots + 128 = 255\) bit strings shorter than 8 bits. So no lossless compressor can shorten every 8-bit file, and the same argument works for every length.
Common mistakes to avoid
First, mislabelling the roles: the boxes must be the categories and the objects the things sorted into them. Second, choosing boxes that do not force the conclusion; in the sum-to-13 example, boxes by parity would prove nothing. Third, using \(N/k\) without rounding up: 75 people and 7 weekdays guarantee \(\lceil 75/7 \rceil = 11\), not 10.7. Fourth, claiming a minimum without showing one fewer can fail. Fifth, expecting the principle to say which box is crowded or how many boxes are: it guarantees only that at least one box is.
Key takeaways
If more than \(k\) objects go into \(k\) boxes, some box holds at least two; with \(N\) objects, some box holds at least \(\lceil N/k \rceil\). Forcing \(m\) in one box takes \(k(m - 1) + 1\) objects, and one fewer can fail. The principle proves existence without construction, and its power lies in choosing clever boxes: pairs with a fixed sum, regions of a square, remainders, or numbers of friends. In computing it explains why hash collisions are unavoidable and why no lossless compressor shrinks every file.
Flashcards
Flashcard
More than k objects in k boxes put two in some box
Test your understanding
Question 1 of 5
A club has 100 members. What is the largest number that must share a birthday weekday this year, whatever the birthdays are?
Question 2 of 5
A box holds marbles of 3 colours. How many must you draw, without looking, to be sure of 4 of the same colour?
Question 3 of 5
How many numbers must be chosen from 1 to 20 to guarantee that two of them add up to 21?
Question 4 of 5
A hash table has 128 slots and 1,000 keys are stored in it. However the keys fall, some slot must hold at least how many keys?
Question 5 of 5
Why can no lossless compression program make every 8-bit file shorter?
