An expert question on pigeonhole principle for P5–P6, with a step-by-step solution, diagrams and the answer. Common in the Hua Xia Cup's P3 to P6 qualifying rounds and finals. The trick is to imagine the unluckiest case.
The question
A lucky-draw box holds 445 balls numbered 1, 7, 13, 19, … up to 2665, each 6 more than the one before.
Lok draws them one at a time without looking.
What is the fewest he must draw to be sure that two of the numbers add up to a multiple of 11?
Show the hints (3)
💡Hint 1: Look at each number's remainder on division by 11. If two numbers add up to a multiple of 11, how are their remainders related?
💡Hint 2: Their remainders on division by 11 run 1, 7, 2, 8, 3, …, repeating every 11 numbers. 445 ÷ 11 = 40 remainder 5: which remainders get one more number?
💡Hint 3: Two classes whose remainders add to 11 can't both be drawn: take the bigger of each pair; at most one with remainder 0.
Worked solution
Have a go first, then read the solution step by step.
1.Two numbers add to a multiple of 11 when their remainders add to 11, or both are 0.
2.The numbers go up by 6, so their remainders go up by 6 too (less 11 when they pass it): the first 11 have remainders 1, 7, 2, 8, 3, 9, 4, 10, 5, 0, 6, each once, and then repeat every 11.
3.445 ÷ 11 = 40 remainder 5: each remainder has 40 numbers, and the first 5 of the cycle (1, 7, 2, 8, 3) one more, 41.
4.The remainders make 5 pairs: 1 and 10, 2 and 9, 3 and 8, 4 and 7, …. Take one class of each pair, the bigger: 1 of 1/10 (41), 2 of 2/9 (41), 7 of 4/7 (41); 204 in all. At most one with remainder 0.
5.Worst luck: 204 + 1 = 205, still no two adding to a multiple of 11; one more makes sure: 205 + 1 = 206.
⚠️Common mistake: copying the 1, 2, 3, … case and giving the extra numbers to remainders 1 to 5, answering 207; these numbers' remainders run 1, 7, 2, 8, …, so count by their own cycle.
Play more like this in Numsprite (unlimited questions, instant marking) →A free maths game: every level free from Easy to Expert (★ to ★★★★), unlimited questions, no download