Problem 9 · 1991 AJHSME
Hard
Number Theory
inclusion-exclusion
How many whole numbers from 1 through 46 are divisible by either 3 or 5 or both?
Show answer
Answer: B — 21.
Show hints
Hint 1 of 3
The word "or both" is the warning. If you just add (multiples of 3) + (multiples of 5), the numbers that are multiples of BOTH get counted twice. Which numbers are those?
Still stuck? Show hint 2 →
Hint 2 of 3
Count multiples of 3 and multiples of 5 separately, then subtract the ones counted twice — the multiples of 3 AND 5, i.e. multiples of 15. (Add, add, subtract the overlap.)
Still stuck? Show hint 3 →
Hint 3 of 3
How many multiples of 3 up to 46? Of 5? Of 15? Each count is just 46 divided by that number, rounded down.
Show solution
Approach: inclusion-exclusion — add the two groups, then subtract the double-counted overlap
- Counting multiples of 3 and of 5 separately double-counts any number that's a multiple of both. A number divisible by both 3 and 5 is exactly a multiple of 15, so those are the ones to remove once.
- Multiples of 3 up to 46: ⌊46 ÷ 3⌋ = 15. Of 5: ⌊46 ÷ 5⌋ = 9. Of 15: ⌊46 ÷ 15⌋ = 3.
- Add the two groups and subtract the overlap once: 15 + 9 − 3 = 21.
- Why this transfers: "how many do A or B" is always |A| + |B| − |both|. The subtraction fixes the overcount — and "multiple of a and b" means multiple of their least common multiple (here LCM(3,5) = 15, since 3 and 5 share no factors).
Mark:
· log in to save