1997 PMWC Problems/Problem T8
Problem
Among the integers , 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 ?
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 |