Olympiad topic · P3–P6
Pigeonhole principle
Common in the Hua Xia Cup's P3 to P6 qualifying rounds and finals. The trick is to imagine the unluckiest case.
Try one
★★ MediumA teacher hands out all 17 books to a class, any number to each pupil, even none.
She says, "However they're shared, some pupil gets at least 3."
She is right.
What is the largest the class could be?
- Hint 1: If everyone gets fewer than 3 — at most one less than 3 — how many books can the class take at most?
- Hint 2: She is right, so "everyone gets fewer than 3" must be impossible: (3 − 1) × the class size must be less than 17.
- 1.With s pupils each getting at most 2, at most 2 × s books get handed out.
- 2.For that to fall short, 2 × s must be less than 17.
- 3.8 pupils: 8 × 2 = 16 is less than 17; the 1 left must go to someone, who then has 3 or more.
- 4.9 pupils: 9 × 2 = 18 exceeds 17, so 2 or fewer each could use them all up, nobody getting 3.
- 5.So the class has at most 8.
Answer: 8 pupils
Four levels, step by step
- ★EasyFree2 question types · unlimited questionsTwo the same, sharing evenly.
- ★★MediumFree2 question types · unlimited questionsSeveral the same, or the number of people worked back.
- ★★★HardFree2 question types · unlimited questionsUneven colours, pairs of numbers.
- ★★★★Expert (competition level)VIP4 question types · unlimited questionsOne colour with enough and another with enough too, numbers that differ by a set amount, one number at most so many times another, sums that are multiples.
Pigeonhole principle: what it is and how to solve it
Putting things into "boxes": at least how many end up in one box, or how many you must take to be sure.
For example: Sweets come in 4 colours. How many must you take to be sure of two the same? At worst the first 4 are all different; the next one must match: 4 + 1 = 5.
The key idea: Think of the unluckiest case: fill every box to just short, and one more makes it certain. n things in k boxes: some box has at least n ÷ k (rounded up).
Practise this topic free →Easy to Hard (★ to ★★★) all free, unlimited questions, no download