AMC 10 · 2004 · #21
Grade 6 arithmeticLet 1; 4; 7; … and 9; 16; 23; … 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?
Pick an answer.
AMC 10 2004 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Two lists of numbers are built by always adding the same step. The first list is $1,4,7,\ldots$ (start at $1$, add $3$ each time). The second is $9,16,23,\ldots$ (start at $9$, add $7$ each time). Take the first $2004$ numbers from each list and pool them into one set $S$. Because some numbers might land on both lists, count how many $\textit{different}$ numbers end up in $S$.
Givens: First sequence: starts at $1$, common difference $3$, so its terms are $1,4,7,\ldots$; Second sequence: starts at $9$, common difference $7$, so its terms are $9,16,23,\ldots$; We take exactly the first $2004$ terms of each sequence.; $S$ is the union (pool) of those $2004+2004$ numbers.; Answer choices: (A) $3722$, (B) $3732$, (C) $3914$, (D) $3924$, (E) $4007$.
Unknowns: The count of distinct values in $S$, that is $|S|$.
Understand
Restated: Two lists of numbers are built by always adding the same step. The first list is $1,4,7,\ldots$ (start at $1$, add $3$ each time). The second is $9,16,23,\ldots$ (start at $9$, add $7$ each time). Take the first $2004$ numbers from each list and pool them into one set $S$. Because some numbers might land on both lists, count how many $\textit{different}$ numbers end up in $S$.
Givens: First sequence: starts at $1$, common difference $3$, so its terms are $1,4,7,\ldots$; Second sequence: starts at $9$, common difference $7$, so its terms are $9,16,23,\ldots$; We take exactly the first $2004$ terms of each sequence.; $S$ is the union (pool) of those $2004+2004$ numbers.; Answer choices: (A) $3722$, (B) $3732$, (C) $3914$, (D) $3924$, (E) $4007$.
Plan
Primary tool: #12 Draw a Venn Diagram
Secondary: #5 Look for a Pattern, #4 Introduce a Variable, #14 Extreme Principle
The set $S$ is the union of two lists that may overlap, so I picture two circles (Tool #12, Draw a Venn Diagram): the size of the union is the two list sizes added, minus the overlap counted twice. So $|S|=2004+2004-(\text{number of shared terms})$, and the whole problem reduces to counting the shared terms. That count is the real work. A number on both lists leaves the same remainders as each list, so the shared numbers form their own steady list that jumps by the least common multiple of the two step sizes (Tool #5, Look for a Pattern). To pin down where that list must stop, I use the smaller of the two final terms as a ceiling (Tool #14, Extreme Principle), which needs each sequence's term rule so I can find those final terms (Tool #4, Introduce a Variable).
Execute — Answer: A
6.EE.A.2 Step 1 Write a rule and find each last term
- Number the terms starting at $1$.
- In the first list each term is the start $1$ plus one $3$ for every jump already made, so the $n$-th term is $1+3(n-1)=3n-2$.
- In the second list the $m$-th term is $9+7(m-1)=7m+2$.
- The last term I keep is the $2004$-th of each.
- First list: $3\cdot 2004-2=6010$.
- Second list: $7\cdot 2004+2=14030$.
- Notice every first-list term leaves remainder $1$ when divided by $3$, and every second-list term leaves remainder $2$ when divided by $7$.
💡 A term is just the starting number plus one step for every jump already made.
6.NS.B.4 Step 2 Shared numbers jump by 21
- A number on both lists must leave remainder $1$ when divided by $3$ and remainder $2$ when divided by $7$ at the same time.
- Scan the second list for the first one that works: $9$ leaves remainder $0$ mod $3$, but $16$ leaves remainder $1$ mod $3$, so $16$ is the first shared number.
- To keep both remainders true after that, you must step up by a whole number of $3$'s and a whole number of $7$'s together, that is by the least common multiple of $3$ and $7$, which is $21$.
- So the shared numbers are $16,37,58,\ldots$, a new steady list starting at $16$ and jumping by $21$.
💡 To keep both remainders at once you can only step by a multiple of both gaps, and the smallest such step is their least common multiple.
6.EE.B.5 Step 3 Count the shared numbers
- A shared number must appear in $\textit{both}$ lists, so it cannot be larger than the smaller of the two final terms.
- The first list stops at $6010$ while the second runs to $14030$, so $6010$ is the ceiling.
- Count the terms $16+21k$ that are at most $6010$: solve $16+21k\le 6010$, giving $21k\le 5994$, so $k\le \tfrac{5994}{21}=285.4\ldots$, meaning $k=0,1,\ldots,285$.
- That is $286$ shared numbers, the largest being $16+21\cdot 285=6001$, which indeed sits below $6010$.
💡 A number on both lists cannot outrun whichever list ends first, so the shorter list's last term is the finish line.
4.OA.A.3 Step 4 Pool the lists with a Venn diagram
- Picture two circles: one holds the $2004$ first-list numbers, the other the $2004$ second-list numbers, and their overlap holds the $286$ shared numbers.
- Simply adding $2004+2004$ counts each shared number twice, so I subtract the overlap once: $|S|=2004+2004-286=4008-286=3722$.
- That is choice (A).
💡 Adding both piles double-counts whatever sits in both, so remove one copy of the overlap.
6.EE.A.2 Number the terms starting at $1$. In the first list each term is the start $1$ p 6.NS.B.4 A number on both lists must leave remainder $1$ when divided by $3$ and remainde 6.EE.B.5 A shared number must appear in $\textit{both}$ lists, so it cannot be larger tha 4.OA.A.3 Picture two circles: one holds the $2004$ first-list numbers, the other the $200 Review
Reasonableness: Before removing duplicates the pool holds $4008$ numbers, and choice (E) $4007$ is only one less, which would mean just a single repeat between two lists that genuinely cross many times, so (E) is far too high. Removing $286$ duplicates lands at $3722$, comfortably below $4008$ and equal to choice (A). Recount the overlap a second way: the shared numbers run $16,37,\ldots,6001$, and $\frac{6001-16}{21}+1=\frac{5985}{21}+1=285+1=286$, confirming the count. Every shared value ($\le 6001$) really does lie within both lists' ranges, so none was miscounted.
Alternative: Instead of a Venn diagram, count the second list's contribution directly. It brings $2004$ numbers, but $286$ of them already appear in the first list, so it adds only $2004-286=1718$ genuinely new numbers. Combine with the first list's full $2004$: $2004+1718=3722$. Same answer, now viewing the overlap as the numbers the second list repeats rather than a double-count to subtract.
CCSS standards used (min grade 6)
6.EE.A.2Write, read, and evaluate expressions in which letters stand for numbers (Writing each sequence's term rule $3n-2$ and $7m+2$ and evaluating them at $n=m=2004$ to find the last terms $6010$ and $14030$.)6.NS.B.4Find greatest common factor and least common multiple of two numbers (Recognizing that the shared numbers form a new sequence stepping by $\operatorname{lcm}(3,7)=21$.)6.EE.B.5Understand solving an inequality as finding which values make it true (Solving $16+21k\le 6010$ to find which values of $k$ keep a shared number within range, giving $286$ terms.)4.OA.A.3Solve multi-step word problems using four operations with whole numbers (Combining the counts by inclusion-exclusion: $2004+2004-286=3722$.)
⭐ Pool two lists by adding their lengths and subtracting the overlap; the overlapping numbers form their own list that jumps by the least common multiple of the two step sizes.
⭐ Pool two lists by adding their lengths and subtracting the overlap; the overlapping numbers form their own list that jumps by the least common multiple of the two step sizes.
More like this
Same archetype — closest grade level first.
