Difference between revisions of "1997 PMWC Problems/Problem T8"
(New page: ==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? ==Solutio...) |
(→See also) |
||
| Line 6: | Line 6: | ||
==See also== | ==See also== | ||
| + | {{PMWC box|year=1997|num-b=T7|num-a=T9}} | ||
Revision as of 10:24, 3 May 2009
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 | ||
