Problem 28 · 2009 Math Kangaroo
Stretch
Number Theory
divisibilitycasework
The numbers 1, 2, 3, …, 99 are divided up into n groups. The following rules apply:
• Each number is in exactly one group.
• There are at least two numbers in each group.
• If two numbers are in the same group, then their sum is not divisible by 3.
Determine the smallest n which fulfils these rules.
Show answer
Answer: C — 33
Show hints
Hint 1 of 2
Sort the numbers 1–99 by their remainder when divided by 3—there are 33 of each remainder.
Still stuck? Show hint 2 →
Hint 2 of 2
Two numbers add to a multiple of 3 only in certain remainder pairs; that limits what can share a group.
Show solution
Approach: work with remainders mod 3
- There are 33 numbers each of remainder 0, 1 and 2. Two remainder-0 numbers, or a remainder-1 with a remainder-2, sum to a multiple of 3.
- So a group holds at most one remainder-0 number and never mixes remainder-1 with remainder-2.
- Each of the 33 remainder-0 numbers needs its own group (paired with allowed others), forcing at least 33 groups, which is achievable.
Mark:
· log in to save