# Subsets and Divisibility

What is the size of the largest subset, S, of {1,2,...2013} such that no pair of distinct elements of S has a sum divisible by 3?

So...I know the very basic divisibility by 3 rule that any number whose digits add up to 3 is divisible by 3. A few numbers in this subset could be 1,3,4... Is there any trick for figuring this question out?

The answer is 672, but I don't know how to get it.

Have you multiplied $672 \cdot 3=2016$? That is a clue. If you take all the elements that are $\equiv 1 \pmod 3$ no pair will sum to a multiple of $3$. You are one short at that point......
• How is $2016$ any how related we can use this hint when we know the answer is $672$ sorry but can you please ellaborate more – Archis Welankar Mar 7 '16 at 4:46
• @ArchisWelankar: It is $3$ more than $2013$, so it indicates you need more than $1/3$ of the numbers available. – Ross Millikan Mar 7 '16 at 4:48