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, ..., 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?
+
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 $1, 2,\dots , 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 $1\bmod{7}$, 286 numbers that are $2\bmod{7}$, and 285 numbers for each of the other residues. From the Greedy Algorithm, we can take all the numbers that are $1\bmod{7}$, then take all the numbers that are $2\bmod{7}$, then all the numbers that are $3\bmod{7}$. The inverses of these are 6, 5, and 4 modulo 7, respectively. Now we can take exactly one number that is $0\bmod{7}$, but no more, because the inverse of 0 is 0. Therefore we can take a maximum of $286+286+285+1=\boxed{858}$ 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