Difference between revisions of "2010 AMC 12A Problems/Problem 20"

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}}$ .

@@ Line 46: / Line 46: @@
 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 ===
+=== Solution 3 (using answer choices) ===
-Let <math>d_1</math> be the common difference of the arithmetic sequence <math>(a_n)</math>. The first term is <math>a_1 = 1</math>, so <math>a_n = 1 + (n - 1) d_1</math> for all <math>n \ge 1</math>. Since <math>a_2 > 1</math>, the common difference <math>d_1</math> is positive.
-Similarly, let <math>d_2</math> be the common difference of the arithmetic sequence <math>(b_n)</math>. The first term is <math>b_1 = 1</math>, so <math>b_n = 1 + (n - 1) d_2</math> for all <math>n \ge 1</math>. Since <math>b_2 > 1</math>, the common difference <math>d_2</math> is also positive.
+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>.
-We observe that <math>n - 1</math> divides both <math>a_n - 1</math> and <math>b_n - 1</math> for all <math>n</math>. Also, since <math>a_2 \le b_2</math>, <math>a_n \le b_n</math> for all <math>n</math>.
-If <math>a_n b_n = 2010</math>, then <math>(a_n, b_n)</math> must be one of the pairs <math>(2,1005)</math>, <math>(3,670)</math>, <math>(5,402)</math>, <math>(6,335)</math>, <math>(10,201)</math>, <math>(15,134)</math>, or <math>(30,67)</math>. For each such pair, we compute the largest number dividing both <math>a_n - 1</math> and <math>b_n - 1</math>:
-\[
-\begin{array}{c|c|c}
-a_n & b_n & \gcd(a_n - 1, b_n - 1) \\ \hline
-& 1005 & 1 \\
-& 670 & 1 \\
-& 402 & 1 \\
-& 335 & 1 \\
-& 201 & 1 \\
-& 134 & 7 \\
-& 67 & 1
-\end{array}
-\]
-We see that the largest possible value of <math>n - 1</math> is 7 (for <math>a_n = 15</math> and <math>b_n = 134</math>), so the largest possible value of <math>n</math> is <math>\boxed{8}</math>. The corresponding arithmetic sequences are <math>a_n = 2n - 1</math> and <math>b_n = 19n - 18</math>. The answer is (C).
 ==Alternative Thinking==
@@ Line 79: / Line 61: @@
 <math>a_n \le b_n</math>,
+blue+yellow=green
@@ Line 87: / Line 70: @@
-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, 10, 15,</math> or <math>30</math> and <math>b_n = 1005, 670, 402, 335, 201, 134,</math> or <math>67</math>; respectively.
+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.

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

Page

Toolbox

Search