Problem:
A subset of the natural numbers between 1 and 100 is such that the sum of any two of its elements is divisible by 6. How many elements can the subset have, at most?
Problem:
A subset of the natural numbers between 1 and 100 is such that the sum of any two of its elements is divisible by 6. How many elements can the subset have, at most?
Pick one
Solution:
The answer is (C). The numbers must be either all even or all odd, since the sums taken two at a time are all even.
Similarly, the numbers must all be divisible by 3, because if contained a number not divisible by 3 (with remainder , say), then there could be only one other such number (with remainder ) and hence , too few!
Now the even multiples of 3, that is, the multiples of 6 between 1 and 100, are 16, while the odd multiples of 3 are 17, so .