Difference between revisions of "2004 AMC 10B Problems/Problem 21"
(→Solution 1) |
|||
(11 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Let <math>1</math>; <math>4</math>; <math>\ldots</math> and <math>9</math>; <math>16</math>; <math>\ldots</math> be two arithmetic progressions. The set <math>S</math> is the union of the first <math>2004</math> terms of each sequence. How many distinct numbers are in <math>S</math>? | + | Let <math>1</math>; <math>4</math>; <math>7</math>; <math>\ldots</math> and <math>9</math>; <math>16</math>; <math>23</math>; <math>\ldots</math> be two arithmetic progressions. The set <math>S</math> is the union of the first <math>2004</math> terms of each sequence. How many distinct numbers are in <math>S</math>? |
<math> \mathrm{(A) \ } 3722 \qquad \mathrm{(B) \ } 3732 \qquad \mathrm{(C) \ } 3914 \qquad \mathrm{(D) \ } 3924 \qquad \mathrm{(E) \ } 4007 </math> | <math> \mathrm{(A) \ } 3722 \qquad \mathrm{(B) \ } 3732 \qquad \mathrm{(C) \ } 3914 \qquad \mathrm{(D) \ } 3924 \qquad \mathrm{(E) \ } 4007 </math> | ||
− | ==Solution== | + | |
− | === | + | ==Solution 1== |
+ | |||
+ | The terms in the first sequence are defined by <math>n \equiv 1 \pmod3</math>, while the terms in the second sequence are defined by <math>n \equiv 2 \pmod 7.</math> We seek to find the solutions to this system of modular congruences. | ||
+ | |||
+ | Letting <math>n = 3a + 1 = 7b + 2</math> for nonnegative integers <math>a,b</math> 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 <math>c,</math> we have that <math>b = 3c+2</math>. Substituting back into our original equation, we have <math>n = 21c + 16,</math> or <math>n \equiv 16 \pmod {21}.</math> | ||
+ | |||
+ | Now we have to find the largest term in the smaller sequence (first sequence), which is <math>2003 \cdot 3 + 1 = 6010.</math> Dividing <math>\frac{6010}{21}</math> gives that there are <math>286</math> terms in common between the sequences. | ||
+ | |||
+ | By PIE, the answer is just <math>2004 + 2004 - 286 = \boxed{(A) 3722}.</math> | ||
+ | |||
+ | ==Solution 2== | ||
The two sets of terms are <math>A=\{ 3k+1 : 0\leq k < 2004 \}</math> and <math>B=\{ 7l+9 : 0\leq l<2004\}</math>. | The two sets of terms are <math>A=\{ 3k+1 : 0\leq k < 2004 \}</math> and <math>B=\{ 7l+9 : 0\leq l<2004\}</math>. | ||
Line 18: | Line 30: | ||
Thus the good values of <math>l</math> are <math>\{1,4,7,\dots,856\}</math>, and their count is <math>858/3 = 286</math>. | Thus the good values of <math>l</math> are <math>\{1,4,7,\dots,856\}</math>, and their count is <math>858/3 = 286</math>. | ||
− | Therefore <math>|A\cap B|=286</math>, and thus <math>|S|=4008-|A\cap B|=\boxed{3722}</math>. | + | Therefore <math>|A\cap B|=286</math>, and thus <math>|S|=4008-|A\cap B|=\boxed{(A) 3722}</math>. |
− | + | ||
− | + | ==Solution 3== | |
+ | We can start by finding the first non-distinct term from both sequences. We find that that number is <math>16</math>. Now, to find every | ||
+ | |||
+ | other non-distinct terms, we can just keep adding <math>21</math>. We know that the last terms of both sequences are <math>1+3\cdot 2003</math> and | ||
+ | |||
+ | <math>9+7\cdot 2003</math>. Clearly, <math>1+3\cdot 2003</math> is smaller and that is the last possible common term of both sequences. Now, we can | ||
+ | |||
+ | create the inequality <math>16+21k \leq 1+3\cdot 2003</math>. Using the inequality, we find that there are <math>286</math> common terms. There are 4008 | ||
+ | |||
+ | terms in total. <math>4008-286=\boxed{(A) 3722}</math> | ||
+ | |||
+ | ~kempwood | ||
== See also == | == See also == |
Latest revision as of 09:39, 5 July 2024
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.