Combinatorial Problems and the Pigeonhole Principle
The pigeonhole principle states that if more than n objects are placed into n boxes, at least one box contains two or more objects; more generally, if N objects go into n boxes, some box has at least ⌈N/n⌉ objects. In brief: among any 13 people, at least two were born in the same month (13 people, 12 months). Among 25 people, at least 3 share a birth month, since ⌈25/12⌉ = 3. The principle proves that something exists without finding it.
The pigeonhole principle is simple to state but surprisingly powerful: it proves existence results in number theory, geometry and computer science. Combined with the counting methods, it solves many competition-style problems. This guide states the principle and its generalised form, shows how to choose the “boxes” in a problem, includes classic applications and then gives a collection of mixed combinatorial problems that use inclusion–exclusion, the multiplication principle and combinations.
What is the pigeonhole principle?
Basic form: if n + 1 (or more) objects are distributed among n boxes, some box contains at least 2 objects. Proof by contradiction: if every box had at most 1 object, there would be at most n objects in total, contradicting n + 1.
Generalised form: if N objects are distributed among n boxes, some box contains at least ⌈N/n⌉ objects, where ⌈x⌉ is the smallest integer not less than x. Proof: if every box had at most ⌈N/n⌉ − 1 objects, the total would be at most n(⌈N/n⌉ − 1) < N.
Example 1
Among 100 people, at least ⌈100/12⌉ = 9 share the same birth month. Among 367 people, at least two share a birthday (366 possible dates, including 29 February). With 8 people, at least 2 were born on the same day of the week, since 8 > 7.
Example 2: socks
A drawer has socks of 4 colours. How many must you take without looking to be sure of a matching pair? 5 socks (boxes = colours). To be sure of 3 of the same colour, you need 4 · 2 + 1 = 9 socks.
What are classic applications?
Example 3: sums and differences
Among any 6 integers there are two whose difference is divisible by 5. The boxes are the 5 remainders modulo 5, so among 6 integers, two have the same remainder, and their difference is a multiple of 5.
Example 4: a multiple of n
For any n integers a1, …, an, some consecutive block ai+1 + … + aj has a sum divisible by n. Consider the n partial sums S1, …, Sn and their remainders modulo n. If one is 0, we are done. Otherwise the n sums have n − 1 possible nonzero remainders, so two coincide, Si ≡ Sj, and the block between them has a sum divisible by n.
Example 5: a repunit divisible by 7
Among the numbers 1, 11, 111, … (repunits) there is one divisible by 7. Take the first 8 of them. There are only 7 possible remainders modulo 7, so two of the 8 numbers have the same remainder. Their difference is divisible by 7. The difference of two repunits has the form (a shorter repunit) · 10m, and since 7 and 10 have no common factor, 7 divides the shorter repunit. Indeed 111,111 = 7 · 15,873.
Example 6: geometry
Place 5 points in a square of side 2. Divide the square into 4 unit squares. Two of the points lie in the same small square, so their distance is at most √2 (the diagonal of a unit square). So among 5 points in a square of side 2, some two are within √2 ≈ 1.414 of each other.
Example 7: handshakes
At a party of n ≥ 2 people, two people have shaken hands with the same number of other people. The number of handshakes of each person is between 0 and n − 1, but 0 and n − 1 cannot both occur (if someone shook hands with everybody, nobody shook hands with 0 people). So there are at most n − 1 possible values for n people, and two coincide.
Example 8: from 1 to 2n
Choose n + 1 numbers from {1, 2, …, 2n}. Then two of them are consecutive. Boxes: {1, 2}, {3, 4}, …, {2n − 1, 2n}: n boxes, n + 1 numbers, so two numbers share a box and differ by 1.
How do you choose the boxes?
- Identify the objects (“pigeons”) and the claim to prove.
- Decide what property should make two pigeons “collide”: same remainder, same colour, same region.
- Define the boxes so that two objects in the same box give the conclusion.
- Count the boxes: the number of objects must exceed the number of boxes.
Remainders (modular arithmetic), colours, regions of a figure and digit patterns are the usual choices of boxes.
Mixed combinatorial problems
Problem 1: inclusion–exclusion with three sets
How many integers from 1 to 100 are divisible by 2, 3 or 5? |A2| = 50, |A3| = 33, |A5| = 20, |A6| = 16, |A10| = 10, |A15| = 6, |A30| = 3. The union is 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74. So 26 numbers are not divisible by any of them (the number 1 and the primes above 5 and their products, such as 49).
Problem 2: arrangements with restrictions
In how many ways can 3 boys and 3 girls sit in a row so that boys and girls alternate? Either BGBGBG or GBGBGB: 2 · 3! · 3! = 72.
Problem 3: distributing objects
Distribute 10 identical sweets among 4 children with each child getting at least 1: C(9, 3) = 84 (stars and bars: place 3 bars in the 9 gaps). If a child may get none: C(13, 3) = 286.
Problem 4: paths
The number of shortest paths from (0, 0) to (5, 3) on a grid is C(8, 3) = 56. Through the point (2, 1): C(3, 1) · C(5, 2) = 3 · 10 = 30. So 56 − 30 = 26 paths avoid the point (2, 1).
Problem 5: committee and subsets
A set with 6 elements has 26 = 64 subsets, of which C(6, 3) = 20 have exactly 3 elements and 32 have an even number of elements (1 + 15 + 15 + 1).
Problem 6: a pigeonhole and a counting
Are 1,000 people enough to guarantee that two have the same initials (first and last name)? The number of possible initial pairs is 26 · 26 = 676 < 1,000, so yes, by the pigeonhole principle, at least ⌈1000/676⌉ = 2 people share initials.
Table of pigeonhole bounds
| Objects N | Boxes n | Guaranteed ⌈N/n⌉ | Example |
|---|---|---|---|
| 13 | 12 | 2 | birth months |
| 25 | 12 | 3 | birth months |
| 367 | 366 | 2 | birthdays |
| 5 | 4 | 2 | sock colours |
| 6 | 5 | 2 | remainders mod 5 |
| 100 | 7 | 15 | weekdays |
Where does the principle come from?
The principle is named after the image of pigeons and pigeonholes, and was first stated explicitly by Peter Gustav Lejeune Dirichlet in 1834 (he called it the “drawer principle”, Schubfachprinzip), which is why it is also called Dirichlet’s principle in some countries. Dirichlet used it to prove results on the approximation of irrational numbers by fractions. Earlier uses can be found in the work of Jean Leurechon in the seventeenth century.
Where is it used today?
The pigeonhole principle explains why lossless compression cannot shrink all files (there are more files of a given length than shorter files), why hash functions must have collisions and why two people in a large city have the same number of hairs on their heads. In Ramsey theory, it is the starting point for results on the unavoidable order in large structures. It also appears in the design of error-correcting codes.
Which mistakes are common?
Choosing boxes that do not give the conclusion
The boxes must be defined so that two objects in one box give the desired property. Think about the final claim first.
Confusing “at least” with “exactly”
The principle guarantees a minimum, not an exact number. With 25 people, some month has at least 3 birthdays, but possibly more.
Forgetting the ceiling
With 13 objects in 4 boxes the guarantee is ⌈13/4⌉ = 4, not 3.
Expecting a construction
The principle shows that a collision exists but not which objects collide.