Difference between revisions of "1997 PMWC Problems/Problem T8"
m |
(→Problem) |
||
(One intermediate revision by one other user not shown) | |||
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== | ||
Line 7: | Line 7: | ||
==See Also== | ==See Also== | ||
{{PMWC box|year=1997|num-b=T7|num-a=T9}} | {{PMWC box|year=1997|num-b=T7|num-a=T9}} | ||
+ | |||
+ | [[Category:Introductory Number Theory Problems]] |
Latest revision as of 13: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 |