1997 PMWC Problems/Problem T8
From AoPSWiki
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 
, 286 numbers that are 
, and 285 numbers for each of the other residues. From the Greedy Algorithm, we can take all the numbers that are , then take all the numbers that are , then all the numbers that are 
. The inverses of these are 6, 5, and 4 modulo 7, respectively. Now we can take exactly one number that is 
, but no more, because the inverse of 0 is 0. Therefore we can take a maximum of 
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 | ||
