Problem 19 · 2012 Math Kangaroo
Medium
Number Theory
careful-countingcasework
The lazy tomcat Garfield observes some mice stealing cheese. Each mouse carries away at least one piece of cheese but less than ten pieces. Each mouse steals a different amount of cheese pieces. No mouse steals exactly twice as many pieces as another mouse. What is the maximum number of mice Garfield can have observed?
Show answer
Answer: C — 6
Show hints
Hint 1 of 2
The amounts are different whole numbers from 1 to 9, and no amount may be exactly double another.
Still stuck? Show hint 2 →
Hint 2 of 2
Group the numbers into doubling chains and pick the most from each chain.
Show solution
Approach: avoid doubling pairs
- Allowed amounts are distinct numbers 1–9 with no pair a and 2a.
- The doubling chain 1–2–4–8 lets you keep at most 2 numbers; the chain 3–6 lets you keep 1; and 5, 7, 9 are free (3 numbers).
- Maximum = 2 + 1 + 3 = 6 mice.
Mark:
· log in to save