Solution
Avoiding Multiples of Seven
Show the problem again
What is the largest possible size of a subset $S$ of {1, 2, ..., 50} such that no two distinct elements of $S$ have a sum divisible by 7? Give an integer.
Worked solution
The answer is 23. Only residues mod 7 matter. Among 1 to 50, residue 1 occurs 8 times (1, 8, ..., 50) and every other residue 7 times. Two elements clash exactly when their residues are $r$ and $7 - r$, or both are 0. So from each pair of classes {1, 6}, {2, 5}, {3, 4} we may use only one class, and from class 0 at most one element. The best choice takes class 1 (8 elements), class 2 or 5 (7), class 3 or 4 (7), plus a single multiple of 7: 8 + 7 + 7 + 1 = 23. Any valid set is bounded the same way class by class, so 23 is optimal.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.