Maths olympiad question · P5–P6★★★★ Expert
Inclusion–exclusion: olympiad question 9
An expert question on inclusion–exclusion for P5–P6, with a step-by-step solution and the answer. Common in the Hua Xia Cup's P3 to P6 qualifying rounds and finals; harder ones have three overlapping groups, or ask who is in exactly two.
The question
The whole numbers 1, 2, 3, … are written out up to N.
Among them, exactly 222 are multiples of neither 3 nor 5.
What is the smallest N can be?
Show the hints (3)
- Hint 1: The LCM of 3 and 5 is 15. How many of 1 to 15 are multiples of neither? Every later run of 15 numbers is the same.
- Hint 2: By inclusion–exclusion: 15 − 15 ÷ 3 − 15 ÷ 5 + 15 ÷ 15. How many whole runs of 15 does 222 take, and where does the rest fall in the next run?
- Hint 3: 8 in every 15; 222 = 8 × 27 + 6. In 1 to 15 they are 1, 2, 4, 7, 8, 11, 13, 14.
Worked solution
Have a go first, then read the solution step by step.
- 1.The LCM of 3 and 5 is 15, so the pattern of multiples repeats every 15 numbers.
- 2.In 1 to 15: 5 multiples of 3, 3 of 5, 1 of both (multiples of 15). Multiples of neither: 15 − 5 − 3 + 1 = 8, namely 1, 2, 4, 7, 8, 11, 13, 14.
- 3.222 = 8 × 27 + 6: up to 27 × 15 = 405 there are exactly 216, 6 short, to be found in the next run (406 to 420).
- 4.In the next run the 6th such number is 405 + 11 = 416; writing up to it gives exactly 222, so the smallest N is 416.
- 5.Check: in 1 to 416, 138 multiples of 3, 83 of 5, 27 of 15: 416 − 138 − 83 + 27 = 222 ✓
- ⚠️Common mistake: estimating N = 222 × 15 ÷ 8 straight off; or giving the largest N.
Answer: 416
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