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 AIME II Problems/Problem 9"

(→‎Solution)
m (→‎Solution 4)
 
(16 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
 
A [[sequence]] of positive integers with <math> a_1=1 </math> and <math> a_9+a_{10}=646 </math> is formed so that the first three terms are in [[geometric sequence|geometric progression]], the second, third, and fourth terms are in [[arithmetic sequence|arithmetic progression]], and, in general, for all <math> n\ge1, </math> the terms <math> a_{2n-1}, a_{2n}, a_{2n+1} </math> are in geometric progression, and the terms <math> a_{2n}, a_{2n+1}, </math> and <math> a_{2n+2} </math> are in arithmetic progression. Let <math> a_n </math> be the greatest term in this sequence that is less than <math>1000</math>. Find <math> n+a_n. </math>
 
A [[sequence]] of positive integers with <math> a_1=1 </math> and <math> a_9+a_{10}=646 </math> is formed so that the first three terms are in [[geometric sequence|geometric progression]], the second, third, and fourth terms are in [[arithmetic sequence|arithmetic progression]], and, in general, for all <math> n\ge1, </math> the terms <math> a_{2n-1}, a_{2n}, a_{2n+1} </math> are in geometric progression, and the terms <math> a_{2n}, a_{2n+1}, </math> and <math> a_{2n+2} </math> are in arithmetic progression. Let <math> a_n </math> be the greatest term in this sequence that is less than <math>1000</math>. Find <math> n+a_n. </math>
  
−
== Solution 1==
+
== Solution 1 ==
 +
 
 
Let <math>x = a_2</math>; then solving for the next several terms, we find that <math>a_3 = x^2,\ a_4 = x(2x-1),\ a_5</math> <math>= (2x-1)^2,\ a_6</math> <math>= (2x-1)(3x-2)</math>, and in general, <math>a_{2n} = f(n-1)f(n)</math>, <math>a_{2n+1} = f(n)^2</math>, where <math>f(n) = nx - (n-1)</math>.{{ref|1}}  
 
Let <math>x = a_2</math>; then solving for the next several terms, we find that <math>a_3 = x^2,\ a_4 = x(2x-1),\ a_5</math> <math>= (2x-1)^2,\ a_6</math> <math>= (2x-1)(3x-2)</math>, and in general, <math>a_{2n} = f(n-1)f(n)</math>, <math>a_{2n+1} = f(n)^2</math>, where <math>f(n) = nx - (n-1)</math>.{{ref|1}}  
  
Line 8: Line 10:
  
 
The answer is <math>957 + 16 = \boxed{973}</math>.
 
The answer is <math>957 + 16 = \boxed{973}</math>.
−
 
−
 
  
 
{{note|1}} We can show this by simultaneous [[induction]]: since  
 
{{note|1}} We can show this by simultaneous [[induction]]: since  
Line 21: Line 21:
 
\end{align*}</cmath>
 
\end{align*}</cmath>
  
−
==Solution 2 (Cheese)==
+
== Solution 2 ==
 +
 
 
Let <math>x = a_2</math>. It is apparent that the sequence grows relatively fast, so we start trying positive integers to see what <math>x</math> can be. Finding that <math>x = 5</math> works, after bashing out the rest of the terms we find that <math>a_{16} = 957</math> and <math>a_{17} = 1089</math>, hence our answer is <math>957 + 16 = \boxed{973}</math>.
 
Let <math>x = a_2</math>. It is apparent that the sequence grows relatively fast, so we start trying positive integers to see what <math>x</math> can be. Finding that <math>x = 5</math> works, after bashing out the rest of the terms we find that <math>a_{16} = 957</math> and <math>a_{17} = 1089</math>, hence our answer is <math>957 + 16 = \boxed{973}</math>.
  
−
== See also ==
+
== Solution 3 ==
 +
We can find the value of <math>a_{9}</math> by its bounds using three conditions:
 +
 
 +
#<math>0<a_{8} = 2a_{9}-a_{10}</math>
 +
#<math>a_{10} < a_{11}</math> (note that the sequence must be increasing on all terms, not monotonically increasing) <math>a_{10} < \frac{a_{10}^2}{a_{9}} \rightarrow a_{9} < a_{10}</math>
 +
#<math>a_{11} = \frac{a_{10}^2}{a_{9}} = \frac{(646-a_{9})^2}{a_{9}}</math>, so necessarily <math>a_{9}</math> is a factor of <math>646^2</math>, which factorizes to <math>2^2\cdot 17^2 \cdot 19^2</math>
 +
 
 +
Rearranging conditions 1 and 2, we get:
 +
 
 +
<cmath>\frac{646}{3} < a_{9} < \frac{646}{2}</cmath>
 +
 
 +
trying all the terms from the third condition, it is clear that <math>a_9 = 289</math> is the only solution.
 +
Then we can calculate the next few terms from there since we have <math>a_{10}</math> as well, to find that <math>a_{16} = 957</math> and <math>a_{17} = 1089</math>, thus we have our answer of <math>957 + 16 = \boxed{973}</math>.
 +
 
 +
~KafkaTamura
 +
 
 +
==Solution 4 (quadratic)==
 +
 
 +
Let <math>a_2 = x</math>. We will write the first 10 terms in terms of <math>x</math> (this will require some rigorous polynomial division):
 +
 
 +
{| class="wikitable"
 +
|+ First 10 Terms
 +
|-
 +
! Term
 +
! Value
 +
|-
 +
| <math>a_1</math>
 +
| <math>1</math>
 +
|-
 +
| <math>a_2</math>
 +
| <math>x</math>
 +
|-
 +
| <math>a_3</math>
 +
| <math>x^2</math>
 +
|-
 +
| <math>a_4</math>
 +
| <math>2x^2 - x</math>
 +
|-
 +
| <math>a_5</math>
 +
| <math>4x^2 - 4x + 1</math>
 +
|-
 +
| <math>a_6</math>
 +
| <math>6x^2 - 7x + 2</math>
 +
|-
 +
| <math>a_7</math>
 +
| <math>9x^2 - 12x + 4</math>
 +
|-
 +
| <math>a_8</math>
 +
| <math>12x^2 - 17x + 6</math>
 +
|-
 +
| <math>a_9</math>
 +
| <math>16x^2 - 24x + 9</math>
 +
|-
 +
| <math>a_{10}</math>
 +
| <math>20x^2 - 31x + 12</math>
 +
|}
 +
The problem tells us that <math>a_9 + a_{10} = 646,</math> so we can write a quadratic and solve for <math>x</math>:
 +
 
 +
<cmath>(16x^2 - 24x + 9) + (20x^2 - 31x + 12) = 646</cmath>
 +
<cmath>36x^2 - 55x + 21 = 646 </cmath>
 +
<cmath>36x^2 - 55x - 625 = 0.</cmath>
 +
<cmath>x = \frac {-(-55) \pm \sqrt{(-55)^2 - 4(36)(-625)}}{2(36)}</cmath>
 +
<cmath>x = \frac {55 \pm \sqrt{3025 + 90000}}{72}</cmath>
 +
<cmath>x = \frac {55 \pm \sqrt{93025}}{72}</cmath>
 +
<math>x = \frac {55 \pm 305}{72} = \xcancel{-\frac{125}{36}}, 5.</math>
 +
 
 +
Since every number in the series has to be a positive integer, <math>x</math> must be <math>5</math>.
 +
Using <math>x=5</math> we can find <math>a_9</math> and <math>a_{10}</math>:
 +
<cmath>a_9 = 16(5)^2 - 24(5) + 9 = 16(25) - 120 + 9 = 400 - 120 + 9 = 289.</cmath>
 +
<cmath>a_{10} = 20(5)^2 - 31(5) + 12 = 20(25) - 155 + 12 = 500 - 155 + 12 = 357.</cmath>
 +
 
 +
 
 +
Notice that our arithmetic differences are increasing by 16: <math>20 \rightarrow 36 \rightarrow 52 \rightarrow 68...</math> So following this pattern, the next differences will be <math>84, 100, 116</math>.
 +
 
 +
The geometric ratios follow a pattern of adding <math>4</math> to the numerator and denominator: <math>\frac{9}{5} \rightarrow \frac{13}{9} \rightarrow \frac{17}{13}</math>. The next ratios will be <math>\frac{21}{17}, \frac{25}{21}, \frac{29}{25}.</math>
 +
 
 +
We have everything we need to calculate the next few terms:
 +
 
 +
<math>a_{11} = 357 \cdot \frac{21}{17} = 441,</math>
 +
<math>a_{12} = 441 + 84 = 525,</math>
 +
<math>a_{13} = 525 \cdot \frac{25}{21} = 625,</math>
 +
<math>a_{14} = 625 + 100 = 725,</math>
 +
<math>a_{15} = 725 \cdot \frac{29}{25} = 841,</math>
 +
<math>a_{16} = 841 + 116 = 957.</math>
 +
We stop here because it's clear the next term will exceed 1000. Since <math>a_{16} = 957,</math> the answer is <math>957 + 16 = \boxed{973}.</math>
 +
 
 +
~[[User:grogg007|grogg007]]
 +
 
 +
== See Also ==
 +
 
 
{{AIME box|year=2004|n=II|num-b=8|num-a=10}}
 
{{AIME box|year=2004|n=II|num-b=8|num-a=10}}
−
 
 
[[Category:Intermediate Algebra Problems]]
 
[[Category:Intermediate Algebra Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 20:33, 29 July 2025

Problem

A sequence of positive integers with $a_1=1$ and $a_9+a_{10}=646$ is formed so that the first three terms are in geometric progression, the second, third, and fourth terms are in arithmetic progression, and, in general, for all $n\ge1,$ the terms $a_{2n-1}, a_{2n}, a_{2n+1}$ are in geometric progression, and the terms $a_{2n}, a_{2n+1},$ and $a_{2n+2}$ are in arithmetic progression. Let $a_n$ be the greatest term in this sequence that is less than $1000$. Find $n+a_n.$

Solution 1

Let $x = a_2$; then solving for the next several terms, we find that $a_3 = x^2,\ a_4 = x(2x-1),\ a_5$ $= (2x-1)^2,\ a_6$ $= (2x-1)(3x-2)$, and in general, $a_{2n} = f(n-1)f(n)$, $a_{2n+1} = f(n)^2$, where $f(n) = nx - (n-1)$.[1]

From \[a_9 + a_{10} = f(4)^2 + f(4)f(5) = (4x-3)(9x-7) = 646 = 2\cdot 17 \cdot 19\], we find that by either the quadratic formula or trial-and-error/modular arithmetic that $x=5$. Thus $f(n) = 4n+1$, and we need to find the largest $n$ such that either $f(n)^2\, \mathrm{or}\, f(n)f(n-1) < 1000$. This happens with $f(7)f(8) = 29 \cdot 33 = 957$, and this is the $2(8) = 16$th term of the sequence.

The answer is $957 + 16 = \boxed{973}$.

^ We can show this by simultaneous induction: since \begin{align*}a_{2n} &= 2a_{2n-1} - a_{2n-2} = 2a_{2(n-1)+1} - a_{2(n-1)} \\ &= 2f(n-1)^2 - f(n-2)f(n-1) \\ &= f(n-1)[2f(n-1) - f(n-2)] \\ &= f(n-1)[(2n-2-n+2)x-(2n-4-n+3)] \\ &= f(n-1)f(n) \end{align*} and \begin{align*}a_{2n+1} &= \frac{a_{2n}^2}{a_{2n-1}} = \frac{f(n-1)^2f(n)^2}{f(n-1)^2} = f(n)^2 \\ \end{align*}

Solution 2

Let $x = a_2$. It is apparent that the sequence grows relatively fast, so we start trying positive integers to see what $x$ can be. Finding that $x = 5$ works, after bashing out the rest of the terms we find that $a_{16} = 957$ and $a_{17} = 1089$, hence our answer is $957 + 16 = \boxed{973}$.

Solution 3

We can find the value of $a_{9}$ by its bounds using three conditions:

  1. $0<a_{8} = 2a_{9}-a_{10}$
  2. $a_{10} < a_{11}$ (note that the sequence must be increasing on all terms, not monotonically increasing) $a_{10} < \frac{a_{10}^2}{a_{9}} \rightarrow a_{9} < a_{10}$
  3. $a_{11} = \frac{a_{10}^2}{a_{9}} = \frac{(646-a_{9})^2}{a_{9}}$, so necessarily $a_{9}$ is a factor of $646^2$, which factorizes to $2^2\cdot 17^2 \cdot 19^2$

Rearranging conditions 1 and 2, we get:

\[\frac{646}{3} < a_{9} < \frac{646}{2}\]

trying all the terms from the third condition, it is clear that $a_9 = 289$ is the only solution. Then we can calculate the next few terms from there since we have $a_{10}$ as well, to find that $a_{16} = 957$ and $a_{17} = 1089$, thus we have our answer of $957 + 16 = \boxed{973}$.

~KafkaTamura

Solution 4 (quadratic)

Let $a_2 = x$. We will write the first 10 terms in terms of $x$ (this will require some rigorous polynomial division):

First 10 Terms
Term Value
$a_1$ $1$
$a_2$ $x$
$a_3$ $x^2$
$a_4$ $2x^2 - x$
$a_5$ $4x^2 - 4x + 1$
$a_6$ $6x^2 - 7x + 2$
$a_7$ $9x^2 - 12x + 4$
$a_8$ $12x^2 - 17x + 6$
$a_9$ $16x^2 - 24x + 9$
$a_{10}$ $20x^2 - 31x + 12$

The problem tells us that $a_9 + a_{10} = 646,$ so we can write a quadratic and solve for $x$:

\[(16x^2 - 24x + 9) + (20x^2 - 31x + 12) = 646\] \[36x^2 - 55x + 21 = 646\] \[36x^2 - 55x - 625 = 0.\] \[x = \frac {-(-55) \pm \sqrt{(-55)^2 - 4(36)(-625)}}{2(36)}\] \[x = \frac {55 \pm \sqrt{3025 + 90000}}{72}\] \[x = \frac {55 \pm \sqrt{93025}}{72}\] $x = \frac {55 \pm 305}{72} = \xcancel{-\frac{125}{36}}, 5.$

Since every number in the series has to be a positive integer, $x$ must be $5$. Using $x=5$ we can find $a_9$ and $a_{10}$: \[a_9 = 16(5)^2 - 24(5) + 9 = 16(25) - 120 + 9 = 400 - 120 + 9 = 289.\] \[a_{10} = 20(5)^2 - 31(5) + 12 = 20(25) - 155 + 12 = 500 - 155 + 12 = 357.\]


Notice that our arithmetic differences are increasing by 16: $20 \rightarrow 36 \rightarrow 52 \rightarrow 68...$ So following this pattern, the next differences will be $84, 100, 116$.

The geometric ratios follow a pattern of adding $4$ to the numerator and denominator: $\frac{9}{5} \rightarrow \frac{13}{9} \rightarrow \frac{17}{13}$. The next ratios will be $\frac{21}{17}, \frac{25}{21}, \frac{29}{25}.$

We have everything we need to calculate the next few terms:

$a_{11} = 357 \cdot \frac{21}{17} = 441,$ $a_{12} = 441 + 84 = 525,$ $a_{13} = 525 \cdot \frac{25}{21} = 625,$ $a_{14} = 625 + 100 = 725,$ $a_{15} = 725 \cdot \frac{29}{25} = 841,$ $a_{16} = 841 + 116 = 957.$ We stop here because it's clear the next term will exceed 1000. Since $a_{16} = 957,$ the answer is $957 + 16 = \boxed{973}.$

~grogg007

See Also

2004 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_AIME_II_Problems/Problem_9&oldid=255953"