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.

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