2012 AMC 12A Problems/Problem 17
Problem
Let 
be a subset of 
with the property that no pair of distinct elements in has a sum divisible by 
. What is the largest possible size of ?
Solution
Of the integers from 
to 
, there are six each of 
. We can create several rules to follow for the elements in subset . No element can be 
if there is an element that is 
. No element can be 
if there is an element that is 
. Thus we can pick 6 elements from either or and 6 elements from either or for a total of 
elements. Considering 
, there can be one element that is so because it will only be divisible by if paired with another element that is . The final answer is 
.
== Solution 2 == ( Similar to solution 1 but more detailed)
[Errors to correct below: We don't totally discard 0 (mod 5), since we can still have one of those. The 
and 
values are largest values, not quantities. So there are 
numbers in each category. We take 2 complete categories plus one from the 
category for a total of 
]
Since we are taking the sum of distinct numbers mod(5), the only values that can be the remainder is ,,
,
,
. We dismiss the case of remainder because this would make the sum a multiple of 5, which is not allowed. In addition, since we can't have 0 or 5 mod(5), we make some restraints. There are four different cases for the "allowed" mods in the sequence, or the remainders that the sum of distinct elements are allowed to be in the sequence. They are:
1) 1mod(5), and 3mod(5)
2) 1mod(5), and 2mod(5)
3) 2mod(5), and 4mod(5),
4) 2mod(5), and 1mod(5)
Now, we can calculate the number of elements in each of these cases. For the first case, we rewrite 1mod(5) in the form 5k+1. Because 5k+1 < 30, which is the largest element in the sequence possible, we obtain k=5. In addition, for 3mod(5), we have 3x+5<30, x=5. This gives us 5+5=10 solutions. The reason why we can add these elements is because all of these elements, no matter which two you add, can never be a multiple of 5. The only possible remainders for the sum are 1+1, 1+3, or 3+3.
In a similar manner, we calculate the element using the same logic. We find that 2mod(5) has 5 elements, and 1mod(5) has 8 elements, meaning that there are a total of 13 elements, which is the answer. ~CharmaineMa07292010
Video Solution by OmegaLearn
https://youtu.be/orrw4VydBTk?t=483
~ pi_is_3.14
See Also
| 2012 AMC 12A (Problems • Answer Key • Resources) | |
| Preceded by Problem 16 |
Followed by Problem 18 |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
| All AMC 12 Problems and Solutions | |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
