2004 AMC 10B Problem 21

The set $S$ takes both lists together, but a number that appears on both lists is counted only once. So: total terms, minus the numbers on both lists.

1. The two lists. The first list is $1, 4, 7, \ldots$ (add $3$ each time). Its $2004$th term is $1 + 3 \times 2003 = 6010$. The second list is $9, 16, 23, \ldots$ (add $7$ each time). Its $2004$th term is $9 + 7 \times 2003 = 14030$.
2. Together they have $2004 + 2004 = 4008$ terms. Now count the numbers that appear on both.
3. Which numbers are on both lists? The first list is the numbers that leave remainder $1$ when divided by $3$. Walk down the second list and check: $9$ (remainder $0$), $16$ (remainder $1$, yes!), $23$ (remainder $2$), $30$ (remainder $0$), $37$ (remainder $1$, yes!). So the shared numbers are $16, 37, 58, \ldots$, going up by $21$. That makes sense: $21$ is the first jump that is a whole number of $3$s and of $7$s.
4. How far do they go? A shared number must be on both lists, so it can be no bigger than $6010$, where the first list stops.
5. Count them. The shared numbers are $16 + 21m$ for $m = 0, 1, 2, \ldots$. We need $16 + 21m \le 6010$, so $21m \le 5994$, and $m \le 285.4\ldots$. So $m$ runs from $0$ to $285$: that is $286$ shared numbers.
6. Finish.
$$4008 - 286 = 3722.$$

The answer is $\boxed{\textbf{(A)}\ 3722}$.

To count two lists put together, add their sizes and subtract the overlap, because overlap numbers were counted twice. Numbers common to two "add $3$" and "add $7$" lists form their own list that adds $3 \times 7 = 21$ each time; find its first term by trying a few values. The overlap can only go as far as the shorter list reaches.

Count inside the second list. Its terms are $9 + 7l$ for $l = 0, 1, 2, \ldots$. A term is also on the first list when it is at most $6010$ and leaves remainder $1$ when divided by $3$. Trying $l = 0, 1, 2, 3, 4$ gives $9, 16, 23, 30, 37$, and the good ones are $l = 1, 4, 7, \ldots$, every third $l$. The size limit $9 + 7l \le 6010$ gives $l \le 857$. The good values $1, 4, 7, \ldots, 856$ number $\frac{856 - 1}{3} + 1 = 286$, the same as before.