1989 AIME Problems/Problem 13
Problem
Let be a subset of such that no two members of differ by or . What is the largest number of elements can have?
Solution
We first show that we can choose at most 5 numbers from such that no two numbers have a difference of or . We take the smallest number to be , which rules out . Now we can take at most one from each of the pairs: , , , . Now, . Because this isn't an exact multiple of , we need to consider some numbers separately.
Notice that (*). Therefore we can put the last numbers into groups of 11. Now let's examine . If we pick from the first numbers, then we're allowed to pick , , , , . This means we get 10 members from the 20 numbers. Our answer is thus .
Remarks (*) Suppose that you choose the values 1, 2, 4, 7, and 10. Because , this is not maximized. It is only maximized if we include the last element of the final set of 11, which is 10 (this is btw). To include the final element, we have to rewrite 1989 as , which includes the final element and increases our set by 1 element.
~Brackie 1331
See also
1989 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.