Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1997 PMWC Problems/Problem T8

Revision as of 10:21, 3 May 2009 by 1=2 (talk | contribs) (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...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 $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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1997_PMWC_Problems/Problem_T8&oldid=31527"