2004 AMC 10B Problem 21

Question

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?

3722

3732

3914

3924

4007

The first sequence has common difference

3

and last term

1 + 3 \cdot 2003 = 6010

Common terms start at

16

and are spaced by

\mathrm{lcm}(3, 7) = 21;

count the terms not exceeding

6010

The first sequence is

1 + 3k

with largest term

6010,

and the second is

9 + 7j

with a much larger last term, so the binding limit is

6010.

A common value has the form

16 + 21m

(the first shared term is

16,

spaced by

\mathrm{lcm}(3, 7) = 21

). Requiring

16 + 21m \le 6010

gives

0 \le m \le 285,

that is

286

common numbers.

The number of distinct values is

2004 + 2004 - 286 = 3722.

Thus, the correct answer is A.

Problem 21 in other years