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 613 cards numbered 1 to 613, one of each.
Lok draws them one at a time without looking.
What is the fewest he must draw to be sure of two cards where the larger number is at most twice the smaller?
Show the hints (3)
💡Hint 1: Think of the worst luck: many cards, but in every pair the larger is more than twice the smaller. Starting from 1, what is the smallest the next card can be?
💡Hint 2: Each card must be more than twice the one before: start from 1, take the smallest possible each time, and stop when you pass 613. How many can be drawn this way at most?
💡Hint 3: Use that run to split 1 to 613 into groups: each group starts at a number of the run and stops just before the next. Within a group, the larger of any two is at most twice the smaller.
Worked solution
Have a go first, then read the solution step by step.
1.First the worst luck: from 1, each card more than twice the one before. The smallest choices are 1, 3, 7, 15, 31, 63, 127, 255, 511: 9 cards; the next would have to be more than twice 511, past 613. In these 9, the larger of any two is more than twice the smaller.
2.On the other hand, split 1 to 613 into 9 groups, each starting at one of those numbers and ending just before the next: {1…2}, {3…6}, {7…14}, {15…30}, …. In each group the largest is at most twice the smallest, so any two cards from one group will do.
3.9 cards might be one per group, not enough; 9 + 1 = 10 must put two in one group.
⚠️Common mistake: multiplying by 2 each time (1, 2, 4, …) and answering 11. "At most twice" includes exactly twice: 2 and 1 already qualify.
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