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 "2010 AMC 12A Problems/Problem 20"

(Created page with '== Problem 20 == Arithmetic sequences <math>\left(a_n\right)</math> and <math>\left(b_n\right)</math> have integer terms with <math>a_1=b_1=1<a_2 \le b_2</math> and <math>a_n b_n…')
 
(→‎Solution)
 
(17 intermediate revisions by 11 users not shown)
Line 1: Line 1:
−
== Problem 20 ==
+
== Problem ==
 
Arithmetic sequences <math>\left(a_n\right)</math> and <math>\left(b_n\right)</math> have integer terms with <math>a_1=b_1=1<a_2 \le b_2</math> and <math>a_n b_n = 2010</math> for some <math>n</math>. What is the largest possible value of <math>n</math>?
 
Arithmetic sequences <math>\left(a_n\right)</math> and <math>\left(b_n\right)</math> have integer terms with <math>a_1=b_1=1<a_2 \le b_2</math> and <math>a_n b_n = 2010</math> for some <math>n</math>. What is the largest possible value of <math>n</math>?
  
Line 5: Line 5:
  
 
== Solution ==
 
== Solution ==
 +
 +
=== Solution 1 ===
 
Since <math>\left(a_n\right)</math> and <math>\left(b_n\right)</math> have integer terms with <math>a_1=b_1=1</math>, we can write the terms of each sequence as
 
Since <math>\left(a_n\right)</math> and <math>\left(b_n\right)</math> have integer terms with <math>a_1=b_1=1</math>, we can write the terms of each sequence as
  
 +
<cmath>\begin{align*}&\left(a_n\right) \Rightarrow \{1, x+1, 2x+1, 3x+1, ...\}\\
 +
&\left(b_n\right) \Rightarrow \{1, y+1, 2y+1, 3y+1, ...\}\end{align*}</cmath>
 +
 +
where <math>x</math> and <math>y</math> (<math>x\leq y</math>) are the common differences of each, respectively.
 +
 +
 +
Since
 +
 +
<cmath>\begin{align*}a_n &= (n-1)x+1\\
 +
b_n &= (n-1)y+1\end{align*}</cmath>
 +
 +
it is easy to see that
 +
 +
<math>a_n \equiv b_n \equiv 1 \mod{(n-1)}</math>.
 +
 +
 +
Hence, we have to find the largest <math>n</math> such that <math>\frac{a_n-1}{n-1}</math> and <math>\frac{b_n-1}{n-1}</math> are both integers; equivalently, we want to maximize <math>\gcd(a_n-1, b_n-1)</math>.
 +
 +
 +
The prime factorization of <math>2010</math> is <math>2\cdot{3}\cdot{5}\cdot{67}</math>. We list out all the possible pairs that have a product of <math>2010</math>, noting that these are the possible values of <math>(a_n, b_n)</math> and we need <math>a_n \leq b_n</math>:
 +
 +
<cmath>(2,1005), (3, 670), (5,402), (6,335), (10,201),(15,134),(30,67)</cmath>
  
−
<math>\left(a_n\right) \Rightarrow \{1, x+1, 2x+1, 3x+1, ...\}</math>
+
and soon find that the largest <math>n-1</math> value is <math>7</math> for the pair <math>(15, 134)</math>, and so the largest <math>n</math> value is <math>\boxed{8\ \textbf{(C)}}</math>.
  
−
<math>\left(b_n\right) \Rightarrow \{1, y+1, 2y+1, 3y+1, ...\}</math>
+
=== Solution 2 ===
  
 +
As above, let <math>a_n=(n-1)x+1</math> and <math>b_n=(n-1)y+1</math> for some <math>1\leq x\leq y</math>.
  
−
where <math>x</math> and <math>y</math> are the common differences of each, respectively.
+
Now we get <math>2010 = a_n b_n = (n-1)^2xy + (n-1)(x+y) + 1</math>, hence <math>2009 = (n-1)( (n-1)xy + x + y )</math>. Therefore <math>n-1</math> divides <math>2009 = 7^2 \cdot 41</math>. And as the second term is greater than the first one, we only have to consider the options <math>n-1\in\{1,7,41\}</math>.
  
 +
For <math>n=42</math> we easily see that for <math>x=y=1</math> the right side is less than <math>49</math> and for any other <math>(x,y)</math> it is way too large.
  
 +
For <math>n=8</math> we are looking for <math>(x,y)</math> such that <math>7xy + x + y = 2009/7 = 7\cdot 41</math>. Note that <math>x+y</math> must be divisible by <math>7</math>. We can start looking for the solution by trying the possible values for <math>x+y</math>, and we easily discover that for <math>x+y=21</math> we get <math>xy + 3 = 41</math>, which has a suitable solution <math>(x,y)=(2,19)</math>.
 +
 +
Hence <math>n=8</math> is the largest possible <math>n</math>. (There is no need to check <math>n=2</math> anymore.)
 +
 +
=== Solution 3 (using answer choices) ===
 +
 +
Consider <math>n=288</math>, which would imply <math>b_{288}\ge a_{288}\ge 288</math>. However then <math>a_n b_n\ge 288^2>2010</math>, so we just need to show that <math>n=8</math> is achievable. This is true when <math>a_n=1+2n</math> and <math>b_n=1+19n</math>, giving <math>a_8 b_8=(15)(134)=2010</math>. Hence the answer is <math>\boxed{\textbf{(C)}\ 8}</math>.
 +
 +
==Alternative Thinking==
 
Since
 
Since
  
−
<math>a_n = (n-1)x+1</math>
 
  
−
<math>b_n = (n-1)y+1</math>
+
<math>a_n*b_n = 2010,</math>
 +
 
 +
 
 +
and
 +
 
 +
 
 +
<math>a_n \le b_n</math>,
 +
blue+yellow=green
 +
 
 +
 
 +
it follows that
 +
 
 +
 
 +
<math>a_n \le \sqrt{2010} \Rightarrow a_n \le 44</math>.
 +
 
 +
 
 +
But <math>a_n</math> and <math>b_n</math> are also integers, so <math>a_n</math> must be a factor of <math>2010</math> smaller than <math>44</math>. Notice that <math>2010 = 2*3*5*67</math>. Therefore <math>a_n = 2, 3, 5, 6, 112, 15,</math> or <math>30</math> and <math>b_n = 1005, 670, 402, 335, 201, 134,</math> or <math>67</math>; respectively.
 +
 
 +
 
 +
Notice that the term <math>a_m</math> is equivalent to the first term <math>a_1 = 1</math> plus <math>(m-1)</math> times the common difference for that particular arithmetic sequence. Let the common difference of <math>(a_n)</math> be <math>k</math> and the common difference of <math>(b_n)</math> be <math>i</math> (not <math>\sqrt{-1}</math>). Then
 +
 
 +
 
 +
<math>a_n</math> (the <math>n</math>th term, not the sequence itself) <math>=1 + k(n-1)</math>
 +
 
 +
 
 +
and
 +
 
 +
 
 +
<math>b_n = 1 + i(n-1)</math>
 +
 
 +
 
 +
Subtracting one from all the possible values listed above for <math>a_n</math> and <math>b_n</math>, we get
  
−
it is easy to see that
 
  
−
<math>a_n \equiv b_n \equiv 1 \mod{(n-1)}</math>.
+
<math>k(n-1) = 1, 2, 4, 5, 9, 14, 29</math>
  
  
−
Hence, we have to find the largest <math>n</math> such that <math>\frac{a_n-1}{n-1}</math> and <math>\frac{a_n-1}{n-1}</math> are both integers.
+
and
  
  
−
The prime factorization of <math>2010</math> is <math>2\cdot{3}\cdot{5}\cdot{67}</math>. We list out all the possible pairs that have a product of <math>2010</math>
+
<math>i(n-1) = 1004, 669, 401, 334, 200, 133, 66</math>
  
  
−
<math>(2,1005), (3, 670), (5,402), (6,335), (10,201),(15,134),(30,67)</math>
+
In order to maximize <math>n</math>, we must maximize <math>n-1</math>. Therefore <math>k</math> and <math>i</math> are [[coprime]] and <math>n-1</math> is the [[Greatest common factor|GCF]] of any corresponding pair. Inspecting all of the pairs, we see that the [[Greatest common factor|GCF]] is always <math>1</math> except for the pair <math>(14, 133),</math> which has a GCF of <math>7</math>. Therefore the maximum value of <math>n</math> is <math>8 \Rightarrow \boxed{\text{C}}</math>.
  
 +
== See also ==
 +
{{AMC12 box|year=2010|num-b=19|num-a=21|ab=A}}
  
−
and soon find that the largest <math>n-1</math> value is <math>7</math> for the pair <math>(15, 134)</math>, and so the largest <math>n</math> value is <math>\boxed{8\ \textbf{(C)}}</math>.
+
[[Category:Introductory Algebra Problems]]
 +
{{MAA Notice}}

Latest revision as of 16:41, 26 August 2024

Problem

Arithmetic sequences $\left(a_n\right)$ and $\left(b_n\right)$ have integer terms with $a_1=b_1=1<a_2 \le b_2$ and $a_n b_n = 2010$ for some $n$. What is the largest possible value of $n$?

$\textbf{(A)}\ 2 \qquad \textbf{(B)}\ 3 \qquad \textbf{(C)}\ 8 \qquad \textbf{(D)}\ 288 \qquad \textbf{(E)}\ 2009$

Solution

Solution 1

Since $\left(a_n\right)$ and $\left(b_n\right)$ have integer terms with $a_1=b_1=1$, we can write the terms of each sequence as

\begin{align*}&\left(a_n\right) \Rightarrow \{1, x+1, 2x+1, 3x+1, ...\}\\ &\left(b_n\right) \Rightarrow \{1, y+1, 2y+1, 3y+1, ...\}\end{align*}

where $x$ and $y$ ($x\leq y$) are the common differences of each, respectively.


Since

\begin{align*}a_n &= (n-1)x+1\\ b_n &= (n-1)y+1\end{align*}

it is easy to see that

$a_n \equiv b_n \equiv 1 \mod{(n-1)}$.


Hence, we have to find the largest $n$ such that $\frac{a_n-1}{n-1}$ and $\frac{b_n-1}{n-1}$ are both integers; equivalently, we want to maximize $\gcd(a_n-1, b_n-1)$.


The prime factorization of $2010$ is $2\cdot{3}\cdot{5}\cdot{67}$. We list out all the possible pairs that have a product of $2010$, noting that these are the possible values of $(a_n, b_n)$ and we need $a_n \leq b_n$:

\[(2,1005), (3, 670), (5,402), (6,335), (10,201),(15,134),(30,67)\]

and soon find that the largest $n-1$ value is $7$ for the pair $(15, 134)$, and so the largest $n$ value is $\boxed{8\ \textbf{(C)}}$.

Solution 2

As above, let $a_n=(n-1)x+1$ and $b_n=(n-1)y+1$ for some $1\leq x\leq y$.

Now we get $2010 = a_n b_n = (n-1)^2xy + (n-1)(x+y) + 1$, hence $2009 = (n-1)( (n-1)xy + x + y )$. Therefore $n-1$ divides $2009 = 7^2 \cdot 41$. And as the second term is greater than the first one, we only have to consider the options $n-1\in\{1,7,41\}$.

For $n=42$ we easily see that for $x=y=1$ the right side is less than $49$ and for any other $(x,y)$ it is way too large.

For $n=8$ we are looking for $(x,y)$ such that $7xy + x + y = 2009/7 = 7\cdot 41$. Note that $x+y$ must be divisible by $7$. We can start looking for the solution by trying the possible values for $x+y$, and we easily discover that for $x+y=21$ we get $xy + 3 = 41$, which has a suitable solution $(x,y)=(2,19)$.

Hence $n=8$ is the largest possible $n$. (There is no need to check $n=2$ anymore.)

Solution 3 (using answer choices)

Consider $n=288$, which would imply $b_{288}\ge a_{288}\ge 288$. However then $a_n b_n\ge 288^2>2010$, so we just need to show that $n=8$ is achievable. This is true when $a_n=1+2n$ and $b_n=1+19n$, giving $a_8 b_8=(15)(134)=2010$. Hence the answer is $\boxed{\textbf{(C)}\ 8}$.

Alternative Thinking

Since


$a_n*b_n = 2010,$


and


$a_n \le b_n$, blue+yellow=green


it follows that


$a_n \le \sqrt{2010} \Rightarrow a_n \le 44$.


But $a_n$ and $b_n$ are also integers, so $a_n$ must be a factor of $2010$ smaller than $44$. Notice that $2010 = 2*3*5*67$. Therefore $a_n = 2, 3, 5, 6, 112, 15,$ or $30$ and $b_n = 1005, 670, 402, 335, 201, 134,$ or $67$; respectively.


Notice that the term $a_m$ is equivalent to the first term $a_1 = 1$ plus $(m-1)$ times the common difference for that particular arithmetic sequence. Let the common difference of $(a_n)$ be $k$ and the common difference of $(b_n)$ be $i$ (not $\sqrt{-1}$). Then


$a_n$ (the $n$th term, not the sequence itself) $=1 + k(n-1)$


and


$b_n = 1 + i(n-1)$


Subtracting one from all the possible values listed above for $a_n$ and $b_n$, we get


$k(n-1) = 1, 2, 4, 5, 9, 14, 29$


and


$i(n-1) = 1004, 669, 401, 334, 200, 133, 66$


In order to maximize $n$, we must maximize $n-1$. Therefore $k$ and $i$ are coprime and $n-1$ is the GCF of any corresponding pair. Inspecting all of the pairs, we see that the GCF is always $1$ except for the pair $(14, 133),$ which has a GCF of $7$. Therefore the maximum value of $n$ is $8 \Rightarrow \boxed{\text{C}}$.

See also

2010 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 19 		Followed by
Problem 21
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 12 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=2010_AMC_12A_Problems/Problem_20&oldid=225822"