Difference between revisions of "2007 AIME I Problems/Problem 14"
IMOJonathan (talk | contribs) (→Solution 4 (pure algebra)) |
m (→Solution 4 (pure algebra)) |
||
Line 114: | Line 114: | ||
<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> | <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>, | 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}{ | + | <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_1a_2}-\frac{2007}{a_0a_1}</math> |
We can keep on using this method to get that | We can keep on using this method to get that |
Revision as of 00:23, 3 February 2018
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.