2004 AMC 10B Problems/Problem 21
Contents
[hide]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
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.