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
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.