1997 PMWC Problems/Problem T8

Problem

Among the integers $1, 2,\dots , 1997$, what is the maximum number of integers that can be selected such that the sum of any two selected numbers is not a multiple of $7$?

Solution

In this list, there are 286 numbers that are $1\bmod{7}$, 286 numbers that are $2\bmod{7}$, and 285 numbers for each of the other residues. From the Greedy Algorithm, we can take all the numbers that are $1\bmod{7}$, then take all the numbers that are $2\bmod{7}$, then all the numbers that are $3\bmod{7}$. The inverses of these are 6, 5, and 4 modulo 7, respectively. Now we can take exactly one number that is $0\bmod{7}$, but no more, because the inverse of 0 is 0. Therefore we can take a maximum of $286+286+285+1=\boxed{858}$ numbers.

See Also

1997 PMWC (Problems)
Preceded by
Problem T7
Followed by
Problem T9
I: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T: 1 2 3 4 5 6 7 8 9 10