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.

The first progression is $3k + 1$ for $k = 0, 1, \dots, 2003$: the numbers $\equiv 1 \pmod 3$ from $1$ up to $3 \cdot 2003 + 1 = 6010$. The second is $7l + 9$ for $l = 0, \dots, 2003$: the numbers $\equiv 2 \pmod 7$ from $9$ up to $7 \cdot 2003 + 9 = 14030$.

The two lists contribute $2004 + 2004 = 4008$ terms, and $|S|$ is $4008$ minus the number of values appearing in both.

A common value must be $1 \pmod 3$ and $2 \pmod 7$. The smallest such number is $16$ ($16 = 15 + 1 = 14 + 2$), and the condition repeats with period $\operatorname{lcm}(3, 7) = 21$, so the common candidates are $16, 37, 58, \dots$, i.e. $16 + 21m$. They must also lie within both ranges: at least $9$ (automatic) and at most $6010$, the cap of the first progression, which is the binding one. From $16 + 21m \le 6010$ we get $m \le \frac{5994}{21} = 285.4\ldots$, so $m = 0, 1, \dots, 285$: $286$ common values.

Therefore
$$|S| = 4008 - 286 = 3722.$$

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