Difference between revisions of "2009 AIME I Problems/Problem 13"

(Solution)
 
(16 intermediate revisions by 8 users not shown)
Line 2: Line 2:
 
The terms of the sequence <math>(a_i)</math> defined by <math>a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}</math> for <math>n \ge 1</math> are positive integers. Find the minimum possible value of <math>a_1 + a_2</math>.
 
The terms of the sequence <math>(a_i)</math> defined by <math>a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}</math> for <math>n \ge 1</math> are positive integers. Find the minimum possible value of <math>a_1 + a_2</math>.
  
== Solution ==
+
==Solution 1==
 +
 
 
This question is guessable but let's prove our answer
 
This question is guessable but let's prove our answer
  
Line 14: Line 15:
  
  
let put <math>n+1</math> into <math>n</math> now
+
lets put <math>n+1</math> into <math>n</math> now
  
  
Line 35: Line 36:
  
  
Let make it looks nice and let <math>b_n=a_{n + 2}-a_n</math>
+
Let's make it look nice and let <math>b_n=a_{n + 2}-a_n</math>
  
  
Line 41: Line 42:
  
  
Since <math>b_n</math> and <math>b_{n+1}</math> are integer, we can see <math>b_{n+1}</math> is divisible by <math>b_n</math>
+
Since <math>b_n</math> and <math>b_{n+1}</math> are integers, we can see <math>b_n</math> is divisible by <math>b_{n+1}</math>
  
  
Line 68: Line 69:
  
  
To minimize <math>a_{1}+a_{2}</math>, we need <math>41 and 49</math>
+
To minimize <math>a_{1}+a_{2}</math>, we need <math>41</math> and <math>49</math>
 +
 
 +
 
 +
Thus, our answer <math>= 41+49=\boxed {090}</math>
 +
 
 +
==Solution 2==
 +
 
 +
If <math>a_{n} \ne \frac {2009}{a_{n+1}}</math>, then either
 +
<cmath>a_{n} = \frac {a_{n}}{1} < \frac {a_{n} + 2009}{1 + a_{n+1}} < \frac {2009}{a_{n+1}}</cmath>
 +
 
 +
or
 +
 
 +
<cmath>\frac {2009}{a_{n+1}} < \frac {2009 + a_{n}}{a_{n+1} + 1} < \frac {a_{n}}{1} = a_{n}</cmath>
 +
 
 +
All the integers between <math>a_{n}</math> and <math>\frac {2009}{a_{n+1}}</math> would be included in the sequence. However the sequence is infinite, so eventually there will be a non-integral term.
 +
 
 +
So <math>a_{n} = \frac {2009}{a_{n+1}}</math>, which <math>a_{n} \cdot a_{n+1} = 2009</math>. When <math>n = 1</math>, <math>a_{1} \cdot a_{2} = 2009</math>. The smallest sum of two factors which have a product of <math>2009</math> is <math>41 + 49=\boxed {090}</math>
 +
 
 +
 
 +
 
 +
== Solution 3 (BS Solution) ==
  
 +
Essentially you see that it must be an integer for infinite numbers, which doesn't quite seem probable. The most logical explanation is that the sequence repeats, and the numbers in the sequence that repeat are integers. We list out some terms.
 +
<cmath>
 +
\begin{align*}
 +
a_{1} &= a \\
 +
a_{2} &= b \\
 +
a_{3} &=\frac{a+2009}{1+b} \\
 +
a_{4} &=\frac{(b+1)(b+2009)}{a+b+2010} \\
 +
\end{align*}
 +
</cmath>
 +
The terms get more and more wacky, so we just solve for <math>a,b</math> such that <math>a_{1}=a_{3}</math> and <math>a_{2}=a_{4}.</math>
  
Thus, answer <math>= 41+49=\boxed {090}</math>
+
Solving we find both equations end up to the equation <math>ab=2009</math> in which we see to minimize we see that <math>a = 49</math> and <math>b=41</math> or vice versa for an answer of <math>\boxed{90}.</math> This solution is VERY non rigorous and not recommended.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2009|n=I|num-b=12|num-a=14}}
 
{{AIME box|year=2009|n=I|num-b=12|num-a=14}}
 +
{{MAA Notice}}

Latest revision as of 15:39, 15 February 2021

Problem

The terms of the sequence $(a_i)$ defined by $a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}$ for $n \ge 1$ are positive integers. Find the minimum possible value of $a_1 + a_2$.

Solution 1

This question is guessable but let's prove our answer

\[a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}\]


\[a_{n + 2}(1 + a_{n + 1})= a_n + 2009\]


\[a_{n + 2}+a_{n + 2} a_{n + 1}-a_n= 2009\]


lets put $n+1$ into $n$ now


\[a_{n + 3}+a_{n + 3} a_{n + 2}-a_{n+1}= 2009\]


and set them equal now


\[a_{n + 3}+a_{n + 3} a_{n + 2}-a_{n+1}= a_{n + 2}+a_{n + 2} a_{n + 1}-a_n\]


\[a_{n + 3}-a_{n+1}+a_{n + 3} a_{n + 2}-a_{n + 2} a_{n + 1}= a_{n + 2}-a_n\]


let's rewrite it


\[(a_{n + 3}-a_{n+1})(a_{n + 2}+1)= a_{n + 2}-a_n\]


Let's make it look nice and let $b_n=a_{n + 2}-a_n$


\[(b_{n+1})(a_{n + 2}+1)= b_n\]


Since $b_n$ and $b_{n+1}$ are integers, we can see $b_n$ is divisible by $b_{n+1}$


But we can't have an infinite sequence of proper factors, unless $b_n=0$


Thus, $a_{n + 2}-a_n=0$


\[a_{n + 2}=a_n\]


So now, we know $a_3=a_1$


\[a_{3} = \frac {a_1 + 2009} {1 + a_{2}}\]


\[a_{1} = \frac {a_1 + 2009} {1 + a_{2}}\]


\[a_{1}+a_{1}a_{2} = a_1 + 2009\]


\[a_{1}a_{2} = 2009\]


To minimize $a_{1}+a_{2}$, we need $41$ and $49$


Thus, our answer $= 41+49=\boxed {090}$

Solution 2

If $a_{n} \ne \frac {2009}{a_{n+1}}$, then either \[a_{n} = \frac {a_{n}}{1} < \frac {a_{n} + 2009}{1 + a_{n+1}} < \frac {2009}{a_{n+1}}\]

or

\[\frac {2009}{a_{n+1}} < \frac {2009 + a_{n}}{a_{n+1} + 1} < \frac {a_{n}}{1} = a_{n}\]

All the integers between $a_{n}$ and $\frac {2009}{a_{n+1}}$ would be included in the sequence. However the sequence is infinite, so eventually there will be a non-integral term.

So $a_{n} = \frac {2009}{a_{n+1}}$, which $a_{n} \cdot a_{n+1} = 2009$. When $n = 1$, $a_{1} \cdot a_{2} = 2009$. The smallest sum of two factors which have a product of $2009$ is $41 + 49=\boxed {090}$


Solution 3 (BS Solution)

Essentially you see that it must be an integer for infinite numbers, which doesn't quite seem probable. The most logical explanation is that the sequence repeats, and the numbers in the sequence that repeat are integers. We list out some terms. \begin{align*} a_{1} &= a \\ a_{2} &= b \\ a_{3} &=\frac{a+2009}{1+b} \\ a_{4} &=\frac{(b+1)(b+2009)}{a+b+2010} \\ \end{align*} The terms get more and more wacky, so we just solve for $a,b$ such that $a_{1}=a_{3}$ and $a_{2}=a_{4}.$

Solving we find both equations end up to the equation $ab=2009$ in which we see to minimize we see that $a = 49$ and $b=41$ or vice versa for an answer of $\boxed{90}.$ This solution is VERY non rigorous and not recommended.

See also

2009 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 12
Followed by
Problem 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png