2004 AMC 10B Problems/Problem 21

Problem

Let ; ; ; and ; ; ; be two arithmetic progressions. The set is the union of the first terms of each sequence. How many distinct numbers are in ?

Solution 1

The terms in the first sequence are defined by , while the terms in the second sequence are defined by We seek to find the solutions to this system of modular congruences.

Letting for nonnegative integers we solve the congruence \begin{align*} 3a+1 &\equiv 7b+2 \pmod 3, \\ 1 &\equiv b + 2 \pmod 3, \\ b &\equiv 2 \pmod 3.\end{align*}

For nonnegative integer we have that . Substituting back into our original equation, we have or

Now we have to find the largest term in the smaller sequence (first sequence), which is Dividing gives that there are terms in common between the sequences.

By PIE, the answer is just

Solution 2

The two sets of terms are and .

Now . We can compute . We will now find .

Consider the numbers in . We want to find out how many of them lie in . In other words, we need to find out the number of valid values of for which .

The fact "" can be rewritten as ", and ".

The first condition gives , the second one gives .

Thus the good values of are , and their count is .

Therefore , and thus .

Solution 3

We can start by finding the first non-distinct term from both sequences. We find that that number is . Now, to find every

other non-distinct terms, we can just keep adding . We know that the last terms of both sequences are and

. Clearly, is smaller and that is the last possible common term of both sequences. Now, we can

create the inequality . Using the inequality, we find that there are common terms. There are 4008

terms in total.

~kempwood

See also

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