1989 AIME Problems/Problem 13

Problem

Let $S^{}_{}$ be a subset of $\{1,2,3^{}_{},\ldots,1989\}$ such that no two members of $S^{}_{}$ differ by $4^{}_{}$ or $7^{}_{}$ . What is the largest number of elements $S^{}_{}$ can have?

Solution

S can have the numbers 1 through 4, but it can't have numbers 5 through 11, because no two numbers can have a difference of 4 or 7. so 12 through 15 work, but 16 through 22 don't work. So on. Now notice that this list contains only numbers 1 through 4 mod 11. 1989 is 9 mod 11, so 1984 is 4 mod 11. We now have the sequence

{4,15,26,...,1984}

we add 7 to each term to get

{11,22,33,...,1991}

We divide by 11 to get

{1,2,3,...,181}

So there are 181 numbers 4 mod 11 in S. We multiply by 4 to account for 1, 2, and 3 mod 11:

$181*4=\boxed{724}$

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

Page

Toolbox

Search

1989 AIME Problems/Problem 13

Problem

Solution

See also