Maths Olympiad Prep

Library / /7 of 75

Number theory Difficulty 3.8 AMC 10/12 Find the answer Italy

Problem:

A subset AA 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 AA have, at most?

Pick one

Solution

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 AA contained a number not divisible by 3 (with remainder rr, say), then there could be only one other such number (with remainder 3r3 - r) and hence A=2|A| = 2, 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 A={3(2k+1)k=0,1,,16}A = \{3(2k+1) \mid k = 0, 1, \ldots, 16\}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.