Difference between revisions of "2009 AIME I Problems/Problem 13"
m (→Solution: typo fixed.) |
Mathboy282 (talk | contribs) |
||
(10 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
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 1== | ||
+ | Our expression is | ||
+ | <cmath>a_{n + 2} = \frac {a_n + 2009} {1 + a_{n + 1}}.</cmath> | ||
+ | Manipulate this to obtain: | ||
+ | <cmath>a_{n + 2}a_{n + 1}+a_{n+2}= a_n + 2009.</cmath> | ||
+ | Our goal is to cancel terms. If we substitute in <math>n+1</math> for <math>n,</math> we get: | ||
+ | <cmath>a_{n+3}a_{n+2}+a_{n+3}=a_{n+1}+2009.</cmath> | ||
+ | Subtracting these two equations and manipulating the expression yields: | ||
+ | <cmath>(a_{n+2}+1)(a_{n+3}-a_{n+1})=a_{n+2}-a_n.</cmath> | ||
+ | Notice we have the form <math>a_{k+2}-a_k</math> on both sides. Let <math>b_n=a_{n+2}-a_n.</math> Then: | ||
+ | <cmath>b_{n+1}(a_{n+2}+1)=b_n.</cmath> | ||
+ | Notice that since <math>a_n</math> is always an integer, <math>a_{n+2}+1</math> and <math>b_n</math> must also always be an integer. It is also clear that <math>b_n</math> is a multiple of <math>b_{n+1},</math> implying a decreasing sequence. | ||
− | == | + | However, if the decreasing factor is nonzero, we will eventually have a <math>b_k</math> that is not an integer, contradicting our conditions for <math>b_n</math>. Thus, we need either <math>a_{n+2}+1=0 \Rightarrow a_{n+2}=-1</math> (impossible as <math>a_n</math> for all indices must be positive integers) or <math>b_n=0 \Rightarrow a_{n+2}=a_n.</math> |
− | + | ||
+ | Given this, we want to find the minimum of <math>a_1+a_2.</math> We have, from the problem: | ||
+ | <cmath>\frac{a_1+2009}{1+a_2}=a_3=a_1 \Rightarrow a_1 a_2 = 2009.</cmath> | ||
+ | By AM-GM, to minimize this, we have to make <math>a_1</math> and <math>a_2</math> factors as close as possible. Hence, the smallest possible sum is <math>41+49=90.</math> | ||
+ | |||
+ | ~mathboy282 | ||
+ | ==Solution 2== | ||
This question is guessable but let's prove our answer | This question is guessable but let's prove our answer | ||
Line 16: | Line 34: | ||
− | + | lets put <math>n+1</math> into <math>n</math> now | |
Line 37: | Line 55: | ||
− | Let make it | + | Let's make it look nice and let <math>b_n=a_{n + 2}-a_n</math> |
Line 43: | Line 61: | ||
− | Since <math>b_n</math> and <math>b_{n+1}</math> are | + | 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 73: | Line 91: | ||
− | Thus, answer <math>= 41+49=\boxed {090}</math> | + | Thus, our answer <math>= 41+49=\boxed {090}</math> |
− | + | ==Solution 3== | |
If <math>a_{n} \ne \frac {2009}{a_{n+1}}</math>, then either | If <math>a_{n} \ne \frac {2009}{a_{n+1}}</math>, then either | ||
Line 87: | Line 105: | ||
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> | 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 4 (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> | ||
+ | |||
+ | 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 16:00, 28 November 2024
Contents
[hide]Problem
The terms of the sequence defined by for are positive integers. Find the minimum possible value of .
Solution 1
Our expression is Manipulate this to obtain: Our goal is to cancel terms. If we substitute in for we get: Subtracting these two equations and manipulating the expression yields: Notice we have the form on both sides. Let Then: Notice that since is always an integer, and must also always be an integer. It is also clear that is a multiple of implying a decreasing sequence.
However, if the decreasing factor is nonzero, we will eventually have a that is not an integer, contradicting our conditions for . Thus, we need either (impossible as for all indices must be positive integers) or
Given this, we want to find the minimum of We have, from the problem: By AM-GM, to minimize this, we have to make and factors as close as possible. Hence, the smallest possible sum is
~mathboy282
Solution 2
This question is guessable but let's prove our answer
lets put into now
and set them equal now
let's rewrite it
Let's make it look nice and let
Since and are integers, we can see is divisible by
But we can't have an infinite sequence of proper factors, unless
Thus,
So now, we know
To minimize , we need and
Thus, our answer
Solution 3
If , then either
or
All the integers between and would be included in the sequence. However the sequence is infinite, so eventually there will be a non-integral term.
So , which . When , . The smallest sum of two factors which have a product of is
Solution 4 (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. The terms get more and more wacky, so we just solve for such that and
Solving we find both equations end up to the equation in which we see to minimize we see that and or vice versa for an answer of This solution is VERY non rigorous and not recommended.
See also
2009 AIME I (Problems • Answer Key • Resources) | ||
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.