Difference between revisions of "1989 AIME Problems/Problem 13"
Brackie1331 (talk | contribs) (→Solution) |
Brackie1331 (talk | contribs) (→Solution) |
||
Line 9: | Line 9: | ||
Remarks | Remarks | ||
(*) Suppose that you choose the values 1, 2, 4, 7, and 10. Because <math>1989 = 180 \times 11 + 9</math>, 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 <math>\text{mod}(11)</math> btw). To include the final element, we have to rewrite 1989 as <math>179 \times 11 + 20</math>, which includes the final element and increases our set by 1 element. | (*) Suppose that you choose the values 1, 2, 4, 7, and 10. Because <math>1989 = 180 \times 11 + 9</math>, 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 <math>\text{mod}(11)</math> btw). To include the final element, we have to rewrite 1989 as <math>179 \times 11 + 20</math>, which includes the final element and increases our set by 1 element. | ||
+ | |||
+ | ~Brackie 1331 | ||
== See also == | == See also == |
Latest revision as of 04:07, 17 December 2023
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.