The Pigeonhole Principle
The pigeonhole principle and its generalisation, a proof by contradiction, and how to choose pigeonholes to prove results about numbers, points and people.
35 min · Combinatorics
The full teaching. Start here.
The short version
- Pigeonhole principle: pigeons in holes means some hole has at least .
- Generalised: pigeons in holes means some hole has at least , so at least the next whole number up.
- Proof: by contradiction. If every hole had fewer, the total would be too small.
- Minimum number to guarantee something: imagine the worst case, then add one.
- Proofs: state clearly what the pigeons are and what the holes are. Choose holes so that two pigeons in one hole gives the result you want.
The principle
If people are in a room, two share a birth month: there are only months to go round. This obvious-sounding fact is surprisingly powerful.
- Pigeonhole principle
If or more objects (pigeons) are placed into boxes (pigeonholes), then at least one box contains at least objects.
It is an existence result. It says some hole is crowded, not which one.
CheckpointAnswer before reading on.
Why must two people in any group of 13 have birthdays in the same month?
Hint 1Months are pigeonholes.
Hint 213 people, 12 months.
Hint 3n + 1 into n.
CheckpointAnswer before reading on.
Twelve people are in a room. Can you guarantee that two share a birth month?
Hint 1Count pigeons and holes.
Hint 212 into 12.
Hint 3One each is possible.
CheckpointAnswer before reading on.
What does the pigeonhole principle tell you?
Hint 1Existence.
Hint 2Not which hole.
Hint 3Some hole.
CheckpointAnswer before reading on.
How many integers must be chosen to guarantee that two leave the same remainder when divided by 7?
Hint 1Remainders 0 to 6.
Hint 27 holes.
Hint 38.
CheckpointAnswer before reading on.
How many people are needed to guarantee that two have the same first and last initials (26 letters)?
Hint 1 pairs.
Hint 2676 holes.
Hint 3677.
Proving it
Worked example3 marks
Proof of the pigeonhole principle
Prove that if pigeons are placed in pigeonholes, some pigeonhole contains at least pigeons. Deduce the case of pigeons in holes.
Assume the opposite
Proof by contradiction.
Suppose every pigeonhole contains fewer than pigeons.
Add up
Count all the pigeons.
Adding over all holes, the total number of pigeons is less than .
Contradiction
There are exactly n pigeons.
This contradicts there being pigeons. So some hole contains at least .
Special case
n + 1 pigeons, n holes.
Some hole contains at least pigeons. Since the count is a whole number, that is at least .
Answer
Some hole holds at least pigeons, and so at least the smallest integer . With pigeons in holes, that means at least .
Is that answer sensible?
pigeons in holes: the principle says some hole has at least , so at least . The most even split, , confirms that is achieved and cannot be avoided.
Exam question
Standard · about 3 min
2 marks
Prove that if pigeons are placed into pigeonholes, some pigeonhole contains at least pigeons. (2 marks)
Hint 1Contradiction.
Hint 2Suppose each hole has at most 1.
Hint 3Total at most .
Where students lose marks on this one
Giving an example.
Why it happens: Illustrating instead of proving.
Prove for general n.
Written for this site.
Exam question
Harder · about 3 min
2 marks
Prove that if pigeons are placed in pigeonholes, then some pigeonhole contains at least pigeons. (2 marks)
Hint 1Contradiction.
Hint 2Each hole fewer than .
Hint 3Total fewer than .
Where students lose marks on this one
Assuming each hole has at most n/k.
Why it happens: Negating wrongly.
The negation of "at least n/k" is "fewer than n/k".
Written for this site.
Using the generalised form
Because pigeon counts are whole numbers, "at least " means at least rounded up. To find the fewest pigeons that guarantee in some hole, imagine the worst case of in every hole, which uses pigeons, and add one: .
CheckpointAnswer before reading on.
Fifty pigeons sit in 7 pigeonholes. What is the largest number that some pigeonhole is guaranteed to hold at least?
Hint 1At least .
Hint 2.
Hint 3Round up to an integer.
CheckpointAnswer before reading on.
In a school of 100 students, at least how many must share a birth month?
Hint 1.
Hint 2.
Hint 3Round up.
CheckpointAnswer before reading on.
Twenty-five pigeons are placed into 6 holes. Some hole must contain at least:
Hint 1.
Hint 2.
Hint 35.
CheckpointAnswer before reading on.
What is the smallest number of people needed to guarantee that three share a birth month?
Hint 1Worst case: two per month.
Hint 2.
Hint 3Add one.
CheckpointAnswer before reading on.
Thirty students each score a whole number from 0 to 10 on a quiz. At least how many students must have the same score?
Hint 111 possible scores.
Hint 2.
Hint 3Round up.
Worst-case reasoning
"How many must you take to be sure?" questions are pigeonhole arguments in disguise. Picture an unlucky draw that avoids the goal for as long as possible, then take one more.
CheckpointAnswer before reading on.
A drawer holds red, blue and black socks (many of each). In the dark, how many socks must you take to be sure of a matching pair?
Hint 1Colours are holes.
Hint 23 holes.
Hint 33 + 1.
CheckpointAnswer before reading on.
A drawer holds 10 red and 10 blue socks. How many must you take (in the dark) to be sure of getting two red socks?
Hint 1Worst case: all the blues first.
Hint 210 blue + 2 red.
Hint 312.
CheckpointAnswer before reading on.
How many cards must be drawn from a standard deck to guarantee three of the same suit?
Hint 14 suits.
Hint 2Worst case: 2 of each.
Hint 38 + 1.
CheckpointAnswer before reading on.
How many cards must be drawn from a standard deck to guarantee four hearts?
Hint 1Worst case: all non-hearts first.
Hint 239 non-hearts.
Hint 339 + 4.
Common mistake
To be sure of three cards of the same suit, draw 3 × 4 = 12.
Why it happens: Counting a full set in every suit instead of the worst case.
The worst case avoids three of a suit for as long as possible: two of each suit, cards. The next card must make three: . The pattern is , not .
Choosing the pigeonholes
In a proof, the skill is in the choice of holes. Design them so that two pigeons in the same hole gives exactly what you are asked to prove.
Worked example3 marks
Choosing pigeonholes in a proof
Prove that if any numbers are chosen from , two of the chosen numbers are consecutive.
Choose the holes
Sharing a hole must mean consecutive.
Split into the pairs .
Count
Pigeons are the chosen numbers.
There are chosen numbers and pairs.
Apply the principle
n + 1 into n.
Some pair contains two chosen numbers. The two numbers in a pair are consecutive.
Answer
Two of the chosen numbers lie in the same pair , so they are consecutive.
Is that answer sensible?
The bound is sharp: choosing the odd numbers gives no consecutive pair. So is the least number that works.
CheckpointAnswer before reading on.
To show that any numbers chosen from include two that add to , what should the pigeonholes be?
Hint 1Pairs that add to 11.
Hint 2
Hint 35 holes.
Exam question
Standard · about 3 min
2 marks
Prove that any numbers chosen from include two whose sum is . (2 marks)
Hint 1Pair up numbers adding to 11.
Hint 25 pairs.
Hint 36 into 5.
Where students lose marks on this one
Not stating the holes.
Why it happens: Using the principle without naming holes.
Always state pigeons and holes.
Written for this site.
Exam question
Standard · about 3 min
2 marks
Prove that any numbers chosen from include two consecutive numbers. (2 marks)
Hint 1Pairs {1, 2}, {3, 4}, …
Hint 250 pairs.
Hint 351 into 50.
Where students lose marks on this one
Using 100 holes.
Why it happens: Wrong holes.
Holes must force the conclusion.
Written for this site.
Exam question
Straightforward · about 2 min
2 marks
Prove that among any integers, two have an even sum. (2 marks)
Hint 1Odd and even.
Hint 22 holes, 3 integers.
Hint 3Same parity sum is even.
Where students lose marks on this one
Only considering odd + odd.
Why it happens: Missing a case.
Both same-parity cases give even sums.
Written for this site.
Exam question
Standard · about 3 min
2 marks
Prove that among any integers, two have a difference divisible by . (2 marks)
Hint 1Remainders on division by 4.
Hint 24 holes.
Hint 3Same remainder: difference divisible by 4.
Where students lose marks on this one
Stopping at "two share a remainder".
Why it happens: Not finishing the argument.
Show why the difference is divisible.
Written for this site.
Exam question
Harder · about 4 min
3 marks
Five points are placed inside a square of side . Prove that two of them are at most apart. (3 marks)
Hint 1Split into four squares of side .
Hint 2Five points, four squares.
Hint 3Diagonal of a small square.
Where students lose marks on this one
Dividing into 5 regions.
Why it happens: Choosing too many holes.
You need fewer holes than points.
Written for this site.
Exam question
Harder · about 3 min
2 marks
Five points are placed inside an equilateral triangle of side . Prove that two of them are at most unit apart. (2 marks)
Hint 1Join the midpoints of the sides.
Hint 2Four triangles of side 1.
Hint 3Largest distance in a small triangle is 1.
Where students lose marks on this one
Using three regions.
Why it happens: Poor choice of holes.
Midpoints give four congruent triangles.
Written for this site.
Exam question
Hardest asked · about 5 min
3 marks
At a party of people, some pairs shake hands. Prove that two people shook the same number of hands. (3 marks)
Hint 1Possible counts .
Hint 2 and cannot both occur.
Hint 3So only values.
Where students lose marks on this one
Using n holes.
Why it happens: Missing the key observation.
0 and n − 1 are mutually exclusive.
Written for this site.
What lifts this to a Band 6
Write the words "pigeons" and "pigeonholes" in your answer: "The pigeons are the integers; the pigeonholes are the possible remainders on division by ." Markers look for exactly this. Then finish the argument: explain why two pigeons in the same hole give the result, rather than stopping at "so two share a hole".
Friends and strangers
Among any people, there are always who all know each other or who are all strangers. Pick one person, . Of the other , by the pigeonhole principle at least are in the same category relative to : say knows , and . If any two of know each other, they form a trio of friends with . If not, are three mutual strangers. With people this can fail, so is the smallest number that works. This is the first case of Ramsey theory, which studies how complete disorder is impossible in large enough structures.