Problem:
What is the size of the largest subset, S, of {1,2,3,…,50} such that no pair of distinct elements of S has a sum divisible by 7?
Answer Choices:
A. 6
B. 7
C. 14
D. 22
E. 23
Solution:
Partition F={1,2,3,…,50} into seven subsets, F0​,F1​,…,F8​, so that all the elements of Fi​ leave a remainder of i when divided by 7:
​F0​={7,14,21,28,35,42,49},F1​={1,8,15,22,29,36,43,50},F2​={2,9,16,23,30,37,44},F3​={3,10,17,24,31,38,45},F4​={4,11,18,25,32,39,46},F5​={5,12,19,26,33,40,47},F6​={6,13,20,27,34,41,48}.​
Note that S can contain at most one member of F0​, but that if S contains some member of any of the other subsets, then it can contain all of the members of that subset. Also, S cannot contain members of both F1​ and F6​, or both F2​ and F5​, or both F3​ and F4​. Since F1​ contains 8 members and each of the other subsets contains 7 members, the largest subset, S, can be constructed by selecting one member of F0​, all the members of F1​, all the members of either F2​ or F5​, and all of the members of either F3​ or F4​. Thus the largest subset, S, contains 1+8+7+7=23 elements.