Problem 25 · 2014 Math Kangaroo
Stretch
Number Theory
divisibilitycasework
Thomas wants to write down pairwise different positive whole numbers, none of which is bigger than 100. Their product should not be divisible by 54. At most how many numbers can he write down?
Show answer
Answer: D — 69
Show hints
Hint 1 of 2
54 = 2 · 3³. The product fails to be divisible by 54 if it is short on 2's OR short on 3's.
Still stuck? Show hint 2 →
Hint 2 of 2
Keeping the total power of 3 below three is the cheaper restriction — how many numbers does that allow?
Show solution
Approach: avoid 3³ in the product to keep the most numbers
- Since 54 = 2·3³, the product avoids 54 if its total power of 3 stays under 3.
- All 67 numbers from 1 to 100 that are NOT multiples of 3 contribute no 3's at all.
- We may still add two multiples of 3 (each contributing one 3), keeping the total power of 3 at 2.
- That gives 67 + 2 = 69 numbers.
Mark:
· log in to save