Difference between revisions of "2004 AMC 10B Problems/Problem 21"
Scrabbler94 (talk | contribs) (→Solution: solution 2 isn't really correct as the positions of the terms which appear in both sequences change after shifting.) |
(→Solution 1) |
||
| (8 intermediate revisions by 5 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 17: | 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 08: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. 
