3.3Pigeonhole principle
The idea
The pigeonhole principle: if n objects go into k boxes, some box holds at least ⌈n/k⌉. To be sure some box holds m objects you need k(m−1)+1 objects.
Think of it like this: Spreading as evenly as possible is the best you can do to avoid a crowded box, and even then the fullest box has ⌈n/k⌉.
Why it exists
Existence questions ("must two people share…", "minimum number to guarantee…") are solved by naming the boxes and dividing.
How it works
- Decide what the pigeons and the holes are.
- Worst case: every hole holds m − 1.
- So the minimum that forces m in a hole is k(m − 1) + 1.
- Some hole holds at least ⌈n/k⌉.
Worked example: How many cards from a 52-card deck guarantee 3 of the same suit?
4 suits, worst case 2 of each = 8 cards, so 9 cards force 3 of a suit.
Now play with it
- →Set 10 pigeons and 4 holes: the fullest hole has 3.
- →Find the least number of pigeons that forces 4 in a hole for k = 5.
The evenest spread is the worst case for you: it makes the fullest hole as small as possible. That fullest hole always holds ⌈n/k⌉.
| Claim | Boxes | Why it is true |
|---|---|---|
| 13 people: two share a birth month | 12 months | ⌈13/12⌉ = 2 |
| 5 integers: two have the same remainder mod 4 | 4 remainders | ⌈5/4⌉ = 2 |
| To be sure of 3 cards of one suit | 4 suits | 4(3−1)+1 = 9 cards |
| Among n+1 numbers from 1..2n, two are consecutive | n pairs {1,2},{3,4},… | pairs are the boxes |
| In a graph, two vertices have the same degree | degrees 0..n−1 | 0 and n−1 cannot both occur |
Find the boxes first, then divide.
Check yourself
Among 50 people, at least how many share a birth month?
Exam notes (the dense version)
If n objects go into k boxes, some box has at least ⌈n/k⌉ objects. To guarantee m in one box you need k(m−1)+1 objects. Typical uses: among 13 people two share a birth month; among any n+1 numbers two have the same remainder mod n; any set of n+1 integers from 1..2n contains two where one divides the other.
Previous year questions: Combinatorics & Recurrences (17)
PYQs are grouped by topic, so this is the full set for Combinatorics & Recurrences; try the ones that match this subtopic. Open all 17 on the topic page.