Difference between revisions of "2007 AIME I Problems/Problem 14"
(Add a solution to a more elementary and rigorous solution to a slightly generalized version.) |
IMOJonathan (talk | contribs) |
||
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== | ||
+ | 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> | ||
+ | Using the recurrence relation, | ||
+ | <math>= \frac{a_0+a_2-\frac{2007}{a_0}}{a_1} = \frac{a_0a_2+a_2^2-\frac{2007a_2}{a_0}}{a_1a_2}</math> | ||
+ | Applying the relation to <math>a_0a_2</math>, | ||
+ | <math>= \frac{a_1^2+2007+a_2^2-\frac{2007a_2}{a_0}}{a_1a_2} = \frac{a_1^2+a_2^2}{a_1a_2}+\frac{2007}{a_1}{a_2}-\frac{2007}{a_0}{a_1}</math> | ||
+ | |||
+ | We can keep on using this method to get that | ||
+ | <math>\frac{a_0^2+a_1^2}{a_0a_1} = \frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}}+\frac{2007}{a_{2006}a_{2007}}-\frac{2007}{a_{2005}a_{2006}}+\frac{2007}{a_{2005}a_{2006}}-\ldots-\frac{2007}{a_{0}a_{1}}</math> | ||
+ | |||
+ | This telescopes to | ||
+ | <math>\frac{a_0^2+a_1^2}{a_0a_1} = \frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}}+\frac{2007}{a_{2006}a_{2007}}-\frac{2007}{a_{0}a_{1}}</math> | ||
+ | |||
+ | or | ||
+ | <math>\frac{a_{2006}^2+a_{2007}^2}{a_{2006}a_{2007}} = \frac{a_0^2+a_1^2}{a_0a_1}+\frac{2007}{a_{0}a_{1}}-\frac{2007}{a_{2006}a_{2007}}</math> | ||
+ | |||
+ | Finding the first few values, we notice that they increase rapidly, so <math>\frac{2007}{a_{2006}a_{2007}} < 1</math>. Calculating the other values, | ||
+ | <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>. | ||
== 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 02:03, 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
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.