What is the maximum size of a subset, P, of {1,2,3,...,50} with the property that no pair distinct elements of P has a sum divisible by 7?

Question

anonymous · Answer

Are you familiar with modular arithmetic?

anonymous · Answer

not really

anonymous · Answer

hmm...well...that makes this a little more difficult then =/

anonymous · Answer

THe best way to look at this is to first establish what conditions must happen for the sum of two numbers to be divisible by 7.

anonymous · Answer

It turns out that if you check the remainders of the numbers after division by 7, and the remainders of two numbers add up to 7, then their sum will be divisible by 7.  For example:

Is the sum of 18 and 17 divisible by 7?  well, the remainder when you divide 18 by 7 is 4, and the remainder when you divide 17 by 7 is 3.  4+3 = 7, so yes, their sum will be divisible by 7 (which we can check because 18+17= 35 which is divisible by 7).

anonymous · Answer

the answers are one of these, (A) 21, (B) 22, (C) 23, (D) 24, (E) 25

anonymous · Answer

To finish the problem, basically group all the numbers with the same remainder together, and collect as many groups as you can without picking two groups whos remainders add up to 7.