Difference between revisions of "1992 AHSME Problems/Problem 23"
(Created page with "Let <math>S</math> be a subset of <math>\{1,2,3,...,50\}</math> such that no pair of distinct elements in <math>S</math> has a sum divisible by <math>7</math>. What is the maximu...") |
|||
| Line 1: | Line 1: | ||
| + | ==Problem== | ||
| + | |||
Let <math>S</math> be a subset of <math>\{1,2,3,...,50\}</math> such that no pair of distinct elements in <math>S</math> has a sum divisible by <math>7</math>. What is the maximum number of elements in <math>S</math>? | Let <math>S</math> be a subset of <math>\{1,2,3,...,50\}</math> such that no pair of distinct elements in <math>S</math> has a sum divisible by <math>7</math>. What is the maximum number of elements in <math>S</math>? | ||
| + | |||
| + | ==Solution== | ||
| + | |||
| + | The fact that <math>x \equiv 0</math> mod <math>7 \Rightarrow 7 \mid x</math> is assumed as common knowledge in this answer. | ||
| + | |||
| + | First, note that there are 8 possible numbers that are equivalent to 1 mod 7, and there are 7 possible numbers equivalent to each of 2-6 mod 7. | ||
| + | |||
| + | Second, note that there can be no pairs of numbers a & b such that <math>a \equiv -b</math> mod <math>7</math>, because then a+b mod 7 = 0. These pairs are (0,0), (1,6), (2,5), and (3,4) mod 7. Because (0,0) is a pair, there can always be 1 number equivalent to 0 mod 7, and no more. | ||
| + | |||
| + | To maximize the amount of numbers in S, we will use 1 number equivalent to 0 mod 7, 8 numbers equivalent to 1, and 14 numbers equivalent to 2-5. This is obvious if you think for a moment. Therefore the answer is 1+8+14=23 numbers. | ||
Revision as of 12:36, 2 May 2012
Problem
Let 
be a subset of 
such that no pair of distinct elements in has a sum divisible by 
. What is the maximum number of elements in ?
Solution
The fact that 
mod 
is assumed as common knowledge in this answer.
First, note that there are 8 possible numbers that are equivalent to 1 mod 7, and there are 7 possible numbers equivalent to each of 2-6 mod 7.
Second, note that there can be no pairs of numbers a & b such that 
mod , because then a+b mod 7 = 0. These pairs are (0,0), (1,6), (2,5), and (3,4) mod 7. Because (0,0) is a pair, there can always be 1 number equivalent to 0 mod 7, and no more.
To maximize the amount of numbers in S, we will use 1 number equivalent to 0 mod 7, 8 numbers equivalent to 1, and 14 numbers equivalent to 2-5. This is obvious if you think for a moment. Therefore the answer is 1+8+14=23 numbers.
