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.