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...) |
(→Problem) |
||
| (3 intermediate revisions 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== | ||
In this list, there are 286 numbers that are <math>1\bmod{7}</math>, 286 numbers that are <math>2\bmod{7}</math>, and 285 numbers for each of the other residues. From the [[Greedy Algorithm]], we can take all the numbers that are <math>1\bmod{7}</math>, then take all the numbers that are <math>2\bmod{7}</math>, then all the numbers that are <math>3\bmod{7}</math>. The inverses of these are 6, 5, and 4 modulo 7, respectively. Now we can take exactly one number that is <math>0\bmod{7}</math>, but no more, because the inverse of 0 is 0. Therefore we can take a maximum of <math>286+286+285+1=\boxed{858}</math> numbers. | In this list, there are 286 numbers that are <math>1\bmod{7}</math>, 286 numbers that are <math>2\bmod{7}</math>, and 285 numbers for each of the other residues. From the [[Greedy Algorithm]], we can take all the numbers that are <math>1\bmod{7}</math>, then take all the numbers that are <math>2\bmod{7}</math>, then all the numbers that are <math>3\bmod{7}</math>. The inverses of these are 6, 5, and 4 modulo 7, respectively. Now we can take exactly one number that is <math>0\bmod{7}</math>, but no more, because the inverse of 0 is 0. Therefore we can take a maximum of <math>286+286+285+1=\boxed{858}</math> numbers. | ||
| − | ==See | + | ==See Also== |
| + | {{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 | ||
