Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2004 AMC 10B Problems/Problem 21"

m (→‎Solution 2)
(→‎Solution: solution 2 isn't really correct as the positions of the terms which appear in both sequences change after shifting.)
Line 5: Line 5:
 
<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==
−
===Solution 1===
 
 
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 19: Line 18:
  
 
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{3722}</math>.
−
===Solution 2===
 
−
Shift down the first sequence by <math>1</math> and the second by <math>9</math> so that the two sequences become <math>0,3,6,\cdots,6009</math> and <math>0,7,14,\cdots,14028</math>. The first becomes multiples of <math>3</math> and the second becomes multiples of <math>7</math>. Their intersection is the multiples of <math>21</math> up to <math>6009</math>. There are <math>\lfloor \frac{6009}{21} \rfloor=286</math> multiples of <math>21</math>. There are <math>4008-286=\boxed{\textbf{(A)}\ 3722}</math> distinct numbers in <math>S</math>.
 
  
 
== See also ==
 
== See also ==

Revision as of 23:04, 23 January 2020

Problem

Let $1$; $4$; $\ldots$ and $9$; $16$; $\ldots$ be two arithmetic progressions. The set $S$ is the union of the first $2004$ terms of each sequence. How many distinct numbers are in $S$?

$\mathrm{(A) \ } 3722 \qquad \mathrm{(B) \ } 3732 \qquad \mathrm{(C) \ } 3914 \qquad \mathrm{(D) \ } 3924 \qquad \mathrm{(E) \ } 4007$

Solution

The two sets of terms are $A=\{ 3k+1 : 0\leq k < 2004 \}$ and $B=\{ 7l+9 : 0\leq l<2004\}$.

Now $S=A\cup B$. We can compute $|S|=|A\cup B|=|A|+|B|-|A\cap B|=4008-|A\cap B|$. We will now find $|A\cap B|$.

Consider the numbers in $B$. We want to find out how many of them lie in $A$. In other words, we need to find out the number of valid values of $l$ for which $7l+9\in A$.

The fact "$7l+9\in A$" can be rewritten as "$1\leq 7l+9 \leq 3\cdot 2003 + 1$, and $7l+9\equiv 1\pmod 3$".

The first condition gives $0\leq l\leq 857$, the second one gives $l\equiv 1\pmod 3$.

Thus the good values of $l$ are $\{1,4,7,\dots,856\}$, and their count is $858/3 = 286$.

Therefore $|A\cap B|=286$, and thus $|S|=4008-|A\cap B|=\boxed{3722}$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_AMC_10B_Problems/Problem_21&oldid=115361"