Problem 25 · 2014 Math Kangaroo
Stretch
Number Theory
divisibilitycareful-counting
Tom has written down a few different positive whole numbers, all smaller than 101. The product of the numbers is not divisible by 18. At most how many numbers could he have written down?
Show answer
Answer: C — 68
Show hints
Hint 1 of 2
18 = 2 × 3², so the product fails only if it lacks a 2 or lacks two 3s.
Still stuck? Show hint 2 →
Hint 2 of 2
Keep as many numbers as possible while keeping the power of 3 below 2.
Show solution
Approach: control the factors of 3 to dodge 18
- Keep all 67 numbers from 1–100 that are not multiples of 3.
- Add one multiple of 3 that is not a multiple of 9 (one factor of 3 only); the product then isn't divisible by 9, hence not by 18.
- That gives 67 + 1 = 68 numbers.
Mark:
· log in to save