Difference between revisions of "2007 AIME I Problems/Problem 14"
IMOJonathan (talk | contribs) |
IMOJonathan (talk | contribs) (→Solution 4) |
||
Line 107: | Line 107: | ||
Using lemma 3, the largest integer less than or equal to this value would be <math>k + 1</math>. | Using lemma 3, the largest integer less than or equal to this value would be <math>k + 1</math>. | ||
− | == Solution 4== | + | === Solution 4 (pure algebra)=== |
We will try to manipulate <math>\frac{a_0^2+a_1^2}{a_0a_1}</math> to get <math>\frac{a_1^2+a_2^2}{a_1a_2}</math>. | We will try to manipulate <math>\frac{a_0^2+a_1^2}{a_0a_1}</math> to get <math>\frac{a_1^2+a_2^2}{a_1a_2}</math>. | ||
<math>\frac{a_0^2+a_1^2}{a_0a_1} = \frac{a_0+\frac{a_1^2}{a_0}}{a_1} = \frac{a_0+\frac{a_1^2+2007}{a_0}-\frac{2007}{a_0}}{a_1}</math> | <math>\frac{a_0^2+a_1^2}{a_0a_1} = \frac{a_0+\frac{a_1^2}{a_0}}{a_1} = \frac{a_0+\frac{a_1^2+2007}{a_0}-\frac{2007}{a_0}}{a_1}</math> | ||
Line 127: | Line 127: | ||
<math>\frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}} = 2+223-\frac{2007}{a_{2006}a_{2007}}</math>. | <math>\frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}} = 2+223-\frac{2007}{a_{2006}a_{2007}}</math>. | ||
− | The greatest number that does not exceed this is <math>224</math> | + | The greatest number that does not exceed this is <math>224</math> |
+ | |||
== See also == | == See also == | ||
{{AIME box|year=2007|n=I|num-b=13|num-a=15}} | {{AIME box|year=2007|n=I|num-b=13|num-a=15}} |
Revision as of 01:04, 26 January 2017
Contents
Problem
A sequence is defined over non-negative integral indexes in the following way: , .
Find the greatest integer that does not exceed
Solution 1
We are given that
, .
Add these two equations to get
- .
This is an invariant. Defining for each , the above equation means
.
We can thus calculate that . Now notice that . This means that
. It is only a tiny bit less because all the are greater than , so we conclude that the floor of is .
Solution 2
The equation looks like the determinant Therefore, the determinant of this matrix is invariant. Guessing that this sequence might be a linear recursion because of the matrix form given below, we define the sequence defined by and for . We wish to find and such that for all . To do this, we use the following matrix form of a linear recurrence relation
When we take determinants, this equation becomes
We want for all . Therefore, we replace the two matrices by to find that
Therefore, . Computing that , and using the fact that , we conclude that . Clearly, , , and . We claim that for all . We proceed by induction. If for all , then clearly, We also know by the definition of that
We know that the RHS is by previous work. Therefore, . After substuting in the values we know, this becomes . Thinking of this as a linear equation in the variable , we already know that this has the solution . Therefore, by induction, for all . We conclude that satisfies the linear recurrence .
It's easy to prove that is a strictly increasing sequence of integers for . Now
The sequence certainly grows fast enough such that . Therefore, the largest integer less than or equal to this value is .
Solution 3 ( generalized )
This is a more elementary and rigorous solution to a slightly generalized version. The defining recursive sequence is generalized to
where is a positive integer and
Lemma 1 : For , We shall prove by induction. From (1), . From the lemma, Base case proven. Assume that the lemma is true for some . Then, eliminating the using (1) and (2) gives
It follows from (2) that
where the last line followed from (1) for case .
Lemma 2 : For Base case is obvious. Assume that for some . Then it follows that
This completes the induction.
Lemma 3 : For
Using (1) and Lemma 2, for
Finally, using (3), for Using lemma 3, the largest integer less than or equal to this value would be .
Solution 4 (pure algebra)
We will try to manipulate to get . Using the recurrence relation, Applying the relation to ,
We can keep on using this method to get that
This telescopes to
or
Finding the first few values, we notice that they increase rapidly, so . Calculating the other values, .
The greatest number that does not exceed this is
See also
2007 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
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.