2007 AIME I Problems/Problem 14
Find the greatest integer that does not exceed
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 .
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 .
|2007 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|