Difference between revisions of "1997 PMWC Problems/Problem T8"
(→Problem) |
|||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Among the integers 1, 2, | + | Among the integers <math>1, 2,\dots , 1997</math>, 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 <math>7</math>? |
==Solution== | ==Solution== |
Latest revision as of 14:42, 20 April 2014
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 |