1997 PMWC Problems/Problem T8

Problem

Among the integers 1, 2, ..., 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.

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

Page

Toolbox

Search

1997 PMWC Problems/Problem T8

Problem

Solution

See Also