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, and 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 \pmod{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