2004 AMC 10B Problems/Problem 21

Problem

Let $1$ ; $4$ ; $\ldots$ and $9$ ; $16$ ; $\ldots$ be two arithmetic progressions. The set $S$ is the union of the first $2004$ terms of each sequence. How many distinct numbers are in $S$ ?

$\mathrm{(A) \ } 3722 \qquad \mathrm{(B) \ } 3732 \qquad \mathrm{(C) \ } 3914 \qquad \mathrm{(D) \ } 3924 \qquad \mathrm{(E) \ } 4007$

Solution

The two sets of terms are $A=\{ 3k+1 : 0\leq k < 2004 \}$ and $B=\{ 7l+9 : 0\leq l<2004\}$ .

Now $S=A\cup B$ . We can compute $|S|=|A\cup B|=|A|+|B|-|A\cap B|=4008-|A\cap B|$ . We will now find $|A\cap B|$ .

Consider the numbers in $B$ . We want to find out how many of them lie in $A$ . In other words, we need to find out the number of valid values of $l$ for which $7l+9\in A$ .

The fact " $7l+9\in A$ " can be rewritten as " $1\leq 7l+9 \leq 3\cdot 2003 + 1$ , and $7l+9\equiv 1\pmod 3$ ".

The first condition gives $0\leq l\leq 857$ , the second one gives $l\equiv 1\pmod 3$ .

Thus the good values of $l$ are $\{1,4,7,\dots,856\}$ , and their count is $858/3 = 286$ .

Therefore $|A\cap B|=286$ , and thus $|S|=4008-|A\cap B|=\boxed{3722}$ .

2004 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 20	Followed by Problem 22
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 10 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

2004 AMC 10B Problems/Problem 21

Problem

Solution

See also