BTT Mathematics / Primary Mathematics Learning Hub / Guaranteed Repetition
The pigeonhole principle turns a distribution problem into a guarantee. If more objects are placed into fewer categories than one-per-category can accommodate, at least one category must receive more than one object. The value of the idea is not its unusual name; it is the proof habit behind it: imagine the arrangement that delays repetition for as long as possible, then show that the next object forces the conclusion.
With five socks placed into four labelled drawers, the first four socks could occupy different drawers. The fifth cannot create a fifth drawer, so some drawer must contain at least two socks. We do not need to know which drawer. The conclusion is guaranteed by capacity.
This guide is Primary Mathematics enrichment. It develops worst-case reasoning, division with remainders, ceilings, category counting and constructive counterexamples. It connects directly to Bounds, Extremes and Guaranteed Conclusions, Systematic Listing and Logic, Deduction and Truth Conditions.
The formal theorem name is optional enrichment. Use the MOE Primary curriculum page and the learner’s school programme for required content.
Basic guarantee · Worst-case construction · Guaranteed minimum occupancy · Choosing categories correctly · Possibility versus guarantee · 24 questions · Worked answers · Teaching and transfer
1. More objects than categories force a repetition
Suppose there are n categories and n+1 objects. If every category held at most one object, the total number of objects could be at most n. But there are n+1 objects. Therefore at least one category contains two or more.
Worked example A: Months
There are twelve calendar months. Among thirteen people, at least two must have birthdays in the same month. The statement does not guarantee the same date, only the same month, because month is the chosen category.
Worked example B: Remainders
Every whole number leaves remainder 0,1,2,3 or 4 when divided by five. These are five remainder categories. Among six whole numbers, at least two have the same remainder modulo five.
Worked example C: Last digits
There are ten possible last digits, 0 through 9. Among eleven whole numbers, at least two share a last digit. Again, we do not know which digit in advance.
Worked example D: Colours
If twenty-one counters are coloured using at most four colours, then at least one colour appears at least six times. Why six rather than merely two? That requires the stronger occupancy version developed below.
2. Build the arrangement that delays the guarantee
To prove that a pair of matching colours is guaranteed among five counters chosen from four colours, imagine the most unfavourable arrangement for getting a pair: choose one counter of each colour first. Four counters can still all be different. The fifth forces a repeated colour.
Worked example E: Socks of three colours
There are red, blue and green socks, with enough of each colour available. In the worst case, the first three chosen socks are one of each colour. The fourth must match one of them. Therefore 4 socks guarantee a matching-colour pair.
Worked example F: Guarantee three of one colour
With three colours, how many socks guarantee three of one colour? To delay a triple, we can take at most two of each colour: 2+2+2=6 socks. The seventh forces some colour to appear at least three times. Therefore 7 is the guarantee threshold.
Worked example G: Guarantee four in one box
If objects are distributed among five boxes, we can place at most three in each box while avoiding a box of four: 5×3=15. Object sixteen forces a box with at least four.
This “fill every category to just below the target” construction is the most useful practical form of pigeonhole reasoning.
3. The guaranteed minimum is controlled by division and rounding upward
If N objects are distributed among k categories, some category must contain at least the smallest whole number not below N÷k. In later notation this is the ceiling of N/k. At Primary enrichment level, the same idea can be explained by balanced distribution.
Worked example H: Twenty-one counters, four colours
21÷4=5 remainder 1. If every colour appeared at most five times, there could be at most twenty counters. Therefore at least one colour appears 6 times.
Worked example I: Thirty pupils, seven tables
30÷7=4 remainder 2. If every table held at most four pupils, only twenty-eight pupils could be seated. Therefore at least one table must hold 5 or more.
Worked example J: Fifty cards, eight boxes
50÷8=6 remainder 2. At least one box contains 7 or more cards.
Worked example K: Exact division
Forty objects distributed among five boxes guarantee at least eight in some box because 40÷5=8 exactly. The bound eight is achievable by an even distribution of eight in every box, so nine is not guaranteed.
Sharpness matters
A guarantee is strongest when we can show both sides: every arrangement forces at least m in some category, and there exists an arrangement where no category has more than m. This proves m is the exact guaranteed minimum.
4. The hard part is often choosing the right categories
Pigeonhole reasoning works only after the objects and categories are defined correctly.
Worked example L: Same parity
Every integer is either even or odd: two categories. Among three integers, at least two share parity. Choosing “positive / negative” would not prove the same claim because zero creates another issue and the categories do not target parity.
Worked example M: Same remainder when divided by 4
The categories are remainders 0,1,2,3. Five integers force two with the same remainder.
Worked example N: Same weekday
Seven weekdays give seven categories. Eight events, each assigned to a weekday, guarantee two on the same weekday.
Worked example O: Difference divisible by 5
If two integers have the same remainder when divided by five, their difference is divisible by five. Thus among six integers, there are always two whose difference is divisible by five. The categories are remainder classes, while the desired conclusion is about the difference.
Worked example P: Consecutive intervals
Choose eleven whole numbers from the set 1 through 20. Pair the numbers as {1,2},{3,4},…,{19,20}: ten categories. With eleven chosen numbers, some pair contributes both members. Therefore the chosen set contains two consecutive numbers.
This works because each category was deliberately constructed to make “same category” imply the target property.
5. A possibility is not a guarantee
To show that four socks are necessary to guarantee a matching-colour pair from three colours, we need two parts. Four socks always force a match. But three socks do not: one red, one blue and one green is a counterexample. Therefore the threshold is exactly four.
Worked example Q: Is ten enough to guarantee three of one colour among five colours?
No. Distribution 2,2,2,2,2 uses ten counters and has no colour appearing three times. Eleven is the first guaranteed number because avoiding three allows at most two per colour.
Worked example R: Guarantee at least four students with same birth month
With twelve months, at most three people per month avoids four in any month: 12×3=36. Therefore thirty-seven people guarantee four sharing a birth month. Thirty-six does not, because a 3-per-month arrangement is possible.
Worked example S: Lower guarantees can coexist
Twenty objects in six boxes guarantee at least four in some box because 20÷6=3 remainder 2. They also guarantee at least three, but “at least four” is the sharper conclusion.
Worked example T: Not every attractive claim follows
Six numbers force two with the same remainder modulo five, but they do not necessarily force two equal numbers. The same-category property is “same remainder,” not “same value.” Proof language must preserve exactly what the categories guarantee.
6. Practice: 24 original questions
Questions 1–8: Direct repetition guarantees
1. Five balls are placed into four boxes. What is guaranteed?
2. Thirteen people are grouped by birth month. What repetition is guaranteed?
3. Eleven whole numbers are grouped by last digit. What is guaranteed?
4. Three integers are grouped as even or odd. What is guaranteed?
5. Six integers are grouped by remainder on division by five. What is guaranteed?
6. Eight appointments are each assigned to one weekday. What is guaranteed?
7. Five integers are grouped by remainder on division by four. What is guaranteed?
8. Eleven numbers are chosen from 1 through 20. Using pairs {1,2},{3,4},…,{19,20}, what is guaranteed?
Questions 9–16: Guaranteed occupancy
9. Twenty-one counters use at most four colours. What is the minimum number guaranteed to have one colour?
10. Thirty pupils sit at seven tables. What is the minimum number guaranteed at one table?
11. Fifty cards are placed in eight boxes. What is the minimum guaranteed in one box?
12. Forty objects are placed in five boxes. What minimum is guaranteed in one box?
13. Twenty objects are placed in six boxes. What minimum is guaranteed in one box?
14. One hundred books are placed on nine shelves. What minimum is guaranteed on one shelf?
15. Thirty-seven people are grouped by birth month. What minimum is guaranteed in one month?
16. Sixty-one tokens are placed into ten jars. What minimum is guaranteed in one jar?
Questions 17–24: Exact thresholds and counterexamples
17. Socks come in three colours. How many socks guarantee two of one colour?
18. Socks come in three colours. How many guarantee three of one colour?
19. Counters come in five colours. How many guarantee three of one colour?
20. Objects go into five boxes. How many objects guarantee four in one box?
21. How many people guarantee at least four sharing a birth month?
22. Explain why ten counters using five colours do not guarantee three of one colour.
23. Among six integers, prove there are two whose difference is divisible by five.
24. Does six integers guarantee two equal integers? Explain why the pigeonhole argument modulo five does or does not prove that.
7. Worked answers
Answers 1–8
1. Some box contains at least two balls. Four boxes can hold at most four balls if each has at most one.
2. At least two people share a birth month. Thirteen objects, twelve month categories.
3. At least two numbers share a last digit. There are ten last-digit categories.
4. At least two integers have the same parity. There are only two categories: even and odd.
5. At least two have the same remainder modulo five. There are five possible remainders.
6. At least two appointments are on the same weekday. Eight appointments, seven weekdays.
7. At least two have the same remainder modulo four. Four remainder categories.
8. At least two chosen numbers are consecutive. Eleven selected numbers occupy ten consecutive-pair categories, so one pair contributes both members.
Answers 9–16
9. 6. 21÷4=5 remainder 1; five per colour would cover only twenty.
10. 5. 30÷7=4 remainder 2.
11. 7. 50÷8=6 remainder 2.
12. 8. 40÷5=8 exactly.
13. 4. 20÷6=3 remainder 2.
14. 12. 100÷9=11 remainder 1, so some shelf has at least twelve.
15. 4. Thirty-six could be three per month; the thirty-seventh forces a fourth.
16. 7. 61÷10=6 remainder 1.
Answers 17–24
17. 4 socks. Three could be one of each colour; the fourth forces a pair.
18. 7 socks. Six could be two of each colour; the seventh forces a triple.
19. 11 counters. Ten can be 2,2,2,2,2; the eleventh forces three of one colour.
20. 16 objects. Fifteen can be three in each of five boxes; the sixteenth forces four.
21. 37 people. Thirty-six can be three per month; the next person forces four in some month.
22. Counterexample 2,2,2,2,2. No colour appears three times, so ten is insufficient.
23. Divide the six integers into the five remainder classes modulo five. Two share a remainder. Their difference is therefore a multiple of five.
24. No. Six distinct numbers can still occupy only five remainder classes, so same remainder does not mean equal value. The argument guarantees a divisible-by-five difference, not equality.
8. Teaching and transfer
If a learner tries to identify the exact repeated category, ask a different question: “Can every category stay below the target?” The principle proves existence without naming where it occurs.
When the learner divides and rounds down
Use twenty-one objects and four boxes. Five per box accounts for only twenty; one object remains. The remainder is precisely why the guarantee must round upward.
When a threshold is guessed but not shown minimal
Ask for a counterexample one below the claimed threshold. For three colours and a matching pair, the one-each arrangement proves three is not enough. This separates “sufficient” from “smallest sufficient.”
When categories are chosen badly
Work backwards from the desired conclusion. If the goal is a difference divisible by five, classify by remainder modulo five because matching categories create that divisibility relation.
When “possible” and “guaranteed” are confused
Two red socks may appear among the first two choices, but a matching pair is not guaranteed until four socks are taken from three colours. A guarantee survives the most unfavourable arrangement.
Connect to bounds
The method is a worst-case bound: fill every category as much as possible without triggering the target, then add one. This is the same structural habit developed in Bounds, Extremes and Guaranteed Conclusions.
Continue through this enrichment collection
For layered counting structures, use Pascal’s Triangle, Combinations and Path Counting. For fraction decomposition, use Egyptian Fractions, Unit Fractions and Decomposition. For cut-and-rearrange proofs, use Geometric Dissections, Rearrangement and Area Proofs.
Return to the BTT Primary Mathematics Learning Hub.
Original enrichment guide with 24 original practice questions and separate worked answers. The named principle is presented as optional enrichment; category definitions control each guarantee.