If there are more pigeons than pigeonholes, at least one pigeonhole contains more than one pigeon.
1. The fundamental idea
The pigeonhole principle, also called the box principle or Dirichlet’s principle, comes from a very simple observation: if we distribute more objects than containers, at least one container receives more than one object. Its power appears when the “pigeons” and “pigeonholes” are hidden: people and months, numbers and remainders, points and geometric regions, subsets and sums, numbers and odd parts.
- Pigeons = the objects we distribute.
- Pigeonholes = the categories into which we classify them.
2. General form
If N objects are distributed among k containers, at least one container holds at least ⌈N / k⌉, where ⌈x⌉ is the smallest integer greater than or equal to x. For example, if 25 people are distributed among the 12 months of the year, at least one month contains at least 3 people, because 25/12 is greater than 2.
3. Inverse formula
How many objects are needed to guarantee that at least one pigeonhole contains r objects? We can put at most r − 1 objects in each of the k pigeonholes without reaching r. The maximum is k(r − 1); the next object forces the result: k(r − 1) + 1.
4. The worst-case method
Many problems are solved by imagining the most unfavorable distribution: avoid the desired outcome for as long as possible, then add one final object. In short: largest possible number without reaching the goal + 1.
5. Twenty-five worked problems
Problem 1 - The months
There are 13 students in a class. Prove that at least two were born in the same month.
Solution
The 13 people are the pigeons and the 12 months are the pigeonholes. Since 13 > 12, at least one month contains at least two birthdays.
Problem 2 - Three people in the same month
How many people are needed to guarantee that at least 3 were born in the same month?
Solution
We can put at most 2 people in each of the 12 months: 12 × 2 = 24. The twenty-fifth forces at least one month to contain 3 people. Answer: 25.
Problem 3 - Socks in the dark
A drawer contains socks in 5 different colors. How many must you take in the dark to be sure of having at least two of the same color?
Solution
In the worst case, the first 5 socks all have different colors. The sixth must repeat one of those 5 colors. Answer: 6.
Problem 4 - Four socks of one color
There are socks in 6 colors. How many must you take to be sure of having at least 4 of the same color?
Solution
We may take 3 of each color without reaching 4 alike: 6 × 3 = 18. The next sock forces a fourth of some color. Answer: 19.
Problem 5 - Remainders modulo 5
Choose any 6 integers. Prove that at least two leave the same remainder when divided by 5.
Solution
The possible remainders are 0, 1, 2, 3, 4: only 5 pigeonholes. Among 6 integers, two must have the same remainder.
Problem 6 - A difference divisible by 5
Prove that among 6 integers there are always two whose difference is divisible by 5.
Solution
By the previous problem, two numbers have the same remainder modulo 5. If a = 5q + r and b = 5p + r, then a − b = 5(q − p); their difference is a multiple of 5.
Problem 7 - Days of the week
In a group of 15 people, prove that at least 3 were born on the same day of the week.
Solution
If each of the 7 days contained at most 2 people, there would be at most 7 × 2 = 14. The fifteenth person forces one day to contain at least 3.
Problem 8 - Final digit
Choose 11 natural numbers. Prove that at least two end in the same digit.
Solution
The possible final digits are 0, 1, 2, …, 9: ten possibilities. With 11 numbers, at least two share a final digit.
Problem 9 - A difference divisible by 10
Choose 11 integers. Prove that two have a difference divisible by 10.
Solution
Classify the numbers by their remainder modulo 10. There are 10 classes; with 11 numbers, two lie in the same class, so their difference is divisible by 10.
Problem 10 - At least five
A school has 101 students distributed among 25 classes. Prove that at least one class contains at least 5 students.
Solution
If each class had at most 4 students, the total would be at most 25 × 4 = 100. Since there are 101 students, some class has at least 5.
Problem 11 - Two consecutive numbers
Choose 6 distinct numbers from {1,2,…,10}. Prove that at least two are consecutive.
Solution
Group the numbers into the 5 pairs (1,2), (3,4), (5,6), (7,8), (9,10). Choosing 6 numbers puts at least two in the same pair, so they are consecutive.
Problem 12 - Why are 5 not enough?
In the previous problem, would 5 numbers suffice?
Solution
No. The counterexample {1,3,5,7,9} has 5 numbers but no consecutive pair. Thus 6 is the minimum threshold.
Problem 13 - Two numbers summing to 11
Choose 6 distinct numbers from 1 to 10. Prove that two sum to 11.
Solution
Form the 5 pairs (1,10), (2,9), (3,8), (4,7), (5,6). Each pair sums to 11. Choosing 6 numbers means that at least one whole pair is selected. Sum = 11.
Problem 14 - A small difference
Choose 6 distinct numbers from 1 to 10. Prove that at least two differ by no more than 1.
Solution
Use the pairs (1,2), (3,4), (5,6), (7,8), (9,10). Among 6 numbers, two belong to the same pair; since they are distinct, they differ by exactly 1.
Problem 15 - Numbers from 1 to 100
Choose 51 distinct numbers from 1 to 100. Prove that at least two are consecutive.
Solution
Divide the 100 numbers into 50 pairs (1,2), (3,4), …, (99,100). With 51 choices, at least one complete pair is selected.
Problem 16 - A difference divisible by 7
Choose any 8 integers. Prove that two differ by a multiple of 7.
Solution
Every integer has one of the 7 remainders 0,1,2,3,4,5,6 modulo 7. Among 8 integers, two have the same remainder, so their difference is divisible by 7.
Problem 17 - One hundred and one numbers from 1 to 200
Take 101 distinct integers from 1 to 200. Prove that at least two differ by less than 2.
Solution
Since they are distinct integers, differing by less than 2 means differing by exactly 1. Form the 100 pairs (1,2), (3,4), …, (199,200). Among 101 numbers, at least one complete pair is chosen.
Problem 18 - Points in a square
Choose 5 points in a square of side 2. Prove that at least two are at distance no greater than √2.
Solution
Divide the square into 4 unit squares. Two of the 5 points lie in the same small square. Their greatest possible distance is its diagonal: d ≤ √2.
Problem 19 - Ten points in a square
Choose 10 points in a square of side 3. Prove that at least two are at distance no greater than √2.
Solution
Divide the square into 9 unit squares. Among 10 points, two lie in the same small square, so their distance is at most its diagonal, √2.
Problem 20 - People and acquaintances
There are 6 people at a party. Each pair either knows each other or does not. Prove that there are always three mutual acquaintances or three people none of whom knows either of the other two.
Solution
Choose a person A. Of the other 5, at least 3 all know A or at least 3 all do not know A. In the first case, if two of the 3 know each other, they and A form a trio of mutual acquaintances; if no pair knows each other, the 3 form a trio of strangers. The second case is symmetric. This is a small example of Ramsey theory.
Problem 21 - The same number of friends
There are n ≥ 2 people at a party. Prove that at least two have the same number of friends at the party.
Solution
Each person might have from 0 to n − 1 friends, but 0 and n − 1 cannot both occur: if somebody knows everybody, nobody has 0 friends. Thus at most n − 1 friend counts actually occur among n people. At least two share a count.
Problem 22 - Two subsets with the same sum
Choose 10 positive integers not exceeding 100. Prove that two different subsets have the same sum.
Solution
Distinguish the ten selected positions even if values coincide. They generate 2¹⁰ = 1024 subsets of positions, including the empty subset. The total sum is at most 1000, so there are at most 1001 possible sums, from 0 to 1000. As 1024 > 1001, two distinct subsets have the same sum.
Problem 23 - Partial sums
Let a₁,a₂,…,aₙ be arbitrary integers. Prove that there is a block of consecutive terms whose sum is divisible by n.
Solution
Consider the n partial sums S₁=a₁, S₂=a₁+a₂, …, Sₙ=a₁+…+aₙ. If one is divisible by n, we are done. Otherwise their remainders belong to 1,…,n − 1: n sums in n − 1 classes. Two sums Sᵢ and Sⱼ have the same remainder. Their difference Sⱼ − Sᵢ = aᵢ₊₁+…+aⱼ is therefore divisible by n.
Problem 24 - Hidden divisibility
Choose 51 distinct numbers from {1,2,…,100}. Prove that one of two selected numbers divides the other.
Solution
Every positive integer has a unique expression 2^k·m with m odd. Classify numbers by their odd part m. From 1 to 100 there are 50 possible odd parts. Among 51 numbers, two have the same odd part: 2^a·m and 2^b·m. If a<b, the second equals the first multiplied by 2^(b−a), so the first divides the second.
Problem 25 - Increasing or decreasing subsequence
Choose 10 distinct numbers and write them in some order. Prove that there is always an increasing subsequence of at least 4 or a decreasing subsequence of at least 4.
Solution
For each term xᵢ, let Cᵢ be the length of the longest increasing subsequence ending at xᵢ and Dᵢ the corresponding decreasing length. If neither type reached length 4, then Cᵢ,Dᵢ ∈ {1,2,3}: only 9 possible pairs (Cᵢ,Dᵢ) for 10 terms. Two terms would share a pair. But for positions i<j, xⱼ>xᵢ increases the possible increasing length, while xⱼ<xᵢ increases the decreasing length. Equal pairs are impossible: contradiction. 3 × 3 = 9 < 10.
6. What makes these problems difficult?
In the first exercises the pigeonholes are obvious: months, colors, classes, days. In the more interesting problems they must be invented. They may be division remainders, pairs of numbers, intervals, geometric regions, odd parts, possible sums, or pairs of properties. The mathematical principle remains elementary; the real difficulty is choosing the right classification.
7. General strategy
- What are the pigeons?
- What could the pigeonholes be?
- How many pigeonholes are there?
- What is the most I can place without obtaining the desired result?
- What happens when I add one object?
Key question: how can I classify the objects so that the pigeonhole principle becomes unavoidable?