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......

  • $\begingroup$ 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 $\endgroup$ – Archis Welankar Mar 7 '16 at 4:46
  • $\begingroup$ @ArchisWelankar: It is $3$ more than $2013$, so it indicates you need more than $1/3$ of the numbers available. $\endgroup$ – Ross Millikan Mar 7 '16 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.