The Pigeonhole Principle
A simple idea, a surprisingly deep tool. If you put more items into containers than there are containers, at least one container must hold more than one item. This almost-obvious fact is the engine behind elegant proofs in combinatorics, number theory, and computer science — and it appears regularly in HSC Extension 1 exams. In this lesson you'll learn how to identify the pigeons, name the pigeonholes, and construct airtight existence proofs.
A drawer contains only red socks and blue socks. Without looking, what is the minimum number of socks you must pull out to guarantee a matching pair? Write your gut answer — and your reasoning — before reading on.
There are two forms of the Pigeonhole Principle you need. Lock the basic form and the generalised form into memory — every exam question is one of these two.
Basic form: If $n$ items are placed into $m$ containers and $n > m$, then at least one container holds at least 2 items.
Generalised form: If $n$ items go into $m$ containers, then at least one container holds at least $\left\lceil \dfrac{n}{m} \right\rceil$ items, where $\lceil x \rceil$ denotes the ceiling (round-up) function.
Key facts
- Basic form: $n > m \Rightarrow$ at least one container has $\geq 2$ items
- Generalised form: at least one container has $\geq \lceil n/m \rceil$ items
- The principle proves existence — it does not identify which container is full
Concepts
- Why $n > m$ is the trigger condition for the basic form
- How to apply the ceiling function to the generalised form
- The difference between "at least one" and "all" containers
Skills
- Identify the pigeons and pigeonholes in a written problem
- State and apply both forms of the principle
- Solve "worst-case" guarantee problems (how many to draw?)
The Pigeonhole Principle (also called the Dirichlet Drawer Principle) can be stated simply:
Proof by contradiction: Suppose every container holds at most 1 item. Then the total number of items is at most $1 \times m = m$. But we have $n > m$ items — contradiction. Therefore at least one container must hold $\geq 2$ items. $\square$
The name comes from the image of $n$ pigeons returning to a row of $m$ nesting holes: if there are more pigeons than holes, at least one hole must contain at least 2 pigeons.
Basic form: n items into m boxes, n > m at least one box contains 2 items; Proof sketch: If each box had 1 item, total items m < n — contradiction
Pause — copy the basic Pigeonhole statement and proof into your book: $n$ items into $m$ boxes with $n > m$ → at least one box has $\ge 2$ items; proof by contradiction: if every box had $\le 1$, total items $\le m < n$.
Quick check: Among any 13 people, the Pigeonhole Principle guarantees that at least two were born in the same month. Here, what are the "pigeonholes"?
We just saw the basic Pigeonhole Principle: $n$ items into $m$ boxes with $n > m$ guarantees at least one box contains $\ge 2$ items. That raises a question: when there are many more items than containers, can we guarantee more than 2 per box — and how many? This card answers it → the generalised form: at least one box contains $\lceil n/m \rceil$ items (ceiling division).
The basic form only guarantees 2 items in one box. The generalised form tells us the minimum guaranteed quantity when there are many more items than containers.
Why the ceiling? Suppose all containers hold at most $\left\lceil \frac{n}{m} \right\rceil - 1$ items. Then the total is at most $m \times \left(\left\lceil \frac{n}{m} \right\rceil - 1\right) < m \times \frac{n}{m} = n$ — contradiction. So at least one container must hold $\geq \left\lceil \frac{n}{m} \right\rceil$ items.
Example: 20 students are grouped into 6 tutorial groups. At least one group has $\lceil 20/6 \rceil = \lceil 3.33\ldots \rceil = 4$ students.
- If $n$ is divisible by $m$: $\lceil n/m \rceil = n/m$ (equal distribution is the worst case)
- If $n$ is not divisible by $m$: $\lceil n/m \rceil = \lfloor n/m \rfloor + 1$ (one extra goes somewhere)
Generalised form: n items into m boxes some box has n/m items; x = ceiling = round up to the next integer ( 3.1 = 4, 4.0 = 4)
Pause — copy the generalised Pigeonhole form into your book: $n$ items into $m$ boxes guarantees at least one box has $\lceil n/m \rceil$ items; $\lceil x \rceil$ is the ceiling — always round up (e.g. $\lceil 3.1 \rceil = 4$).
Did you get this? True or false: if 14 people are assigned to 4 groups, the generalised pigeonhole principle guarantees at least one group has 4 or more people.
Worked examples · 3 in a row, reveal as you go
Show that among any 13 people, at least two were born in the same month.
A bag contains red, blue, and green marbles. How many marbles must be drawn (without looking) to guarantee that at least 4 marbles of one colour have been drawn?
Show that among any 5 integers, at least two have the same remainder when divided by 4.
Fill the gap: To guarantee drawing at least 3 cards of the same suit from a standard 52-card deck (4 suits), you must draw at least cards.
Common misconceptions · the 3 traps that cost marks
Did you get this? True or false: the Pigeonhole Principle can be used to find out exactly which two people in a group of 13 share a birthday month.
Activities · practice with the ideas
A group of 25 students sit a test marked out of 20. Explain why at least two students must achieve the same score.
A drawer contains 6 red socks and 4 blue socks. What is the minimum number of socks you must draw (without looking) to guarantee a matching pair? Justify using the Pigeonhole Principle.
Use the generalised form to find the guaranteed minimum number of students in at least one group, if 50 students are divided into 7 groups.
Show that among any 10 integers, at least two must have the same remainder when divided by 9.
A bag contains 5 red, 5 blue, 5 green, and 5 yellow balls. What is the minimum number of balls you must draw to guarantee at least 3 balls of the same colour? Use the formula $t(k-1)+1$.
Odd one out: Which of the following is NOT a valid application of the Pigeonhole Principle?
Earlier you were asked: how many socks must you draw from a drawer of red and blue socks to guarantee a matching pair?
Answer: you need only 3 socks. The pigeons are the 3 socks drawn; the pigeonholes are the 2 colours. Since $3 > 2$, at least two socks must share the same colour — a matching pair. Notice the answer does not depend on how many red or blue socks are in the drawer, only on the number of types.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Show that among any 5 integers, at least two have the same remainder when divided by 4. (2 marks)
Q2. How many cards must be drawn from a standard 52-card deck (13 cards per suit, 4 suits) to guarantee at least 3 hearts? (2 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. Pigeons = 25 students; holes = 21 scores (0–20). Since 25 > 21, at least two students share a score. [2]
2. Pigeons = socks drawn; holes = 2 colours. Worst case: 1 red + 1 blue = 2 socks, no pair. Draw 3rd: must match one of the 2 colours. Answer: 3. [2]
3. $\lceil 50/7 \rceil = \lceil 7.14\ldots \rceil = 8$. At least one group has 8 students. [1]
4. When dividing by 9, the possible remainders are $\{0,1,2,\ldots,8\}$ — 9 pigeonholes. Since 10 > 9, at least two of the 10 integers share a remainder mod 9. [2]
5. $t = 4$, $k = 3$: $4(3-1)+1 = 9$ balls. [2]
Q1 (2 marks): Pigeons = 5 integers; holes = 4 possible remainders $\{0,1,2,3\}$ when dividing by 4 [1]. Since $5 > 4$, by the Pigeonhole Principle at least two integers share the same remainder mod 4 [1].
Q2 (2 marks): Worst case: draw all 39 non-heart cards, plus 2 hearts — 41 cards with no 3 hearts [1]. The 42nd card must be the 3rd heart. Answer: 42 cards [1].
Five timed questions. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering combinatorics questions. A lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.