Difference between revisions of "1988 AIME Problems/Problem 13"
MRENTHUSIASM (talk | contribs) m (→Solution 6 (Decreases the Powers)) |
Bobthegod78 (talk | contribs) |
||
Line 107: | Line 107: | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
+ | |||
+ | == Solution 7 (Use the roots) == | ||
+ | |||
+ | For simplicity, let <math>f(x) =ax^{17} + bx^{16} + 1</math> and <math>g(x) = x^2-x-1</math>. Notice that the roots of <math>g(x)</math> are also roots of <math>f(x)</math>. Let these roots be <math>u,v</math>. We get the system | ||
+ | \begin{align*} | ||
+ | au^{17} + bu^{16} + 1 &= 0, \ | ||
+ | av^{17} + bv^{16} + 1 &= 0. | ||
+ | \end{align*} | ||
+ | If we multiply the first equation by <math>v^{16}</math> and the second by <math>u^{16}</math> we get \begin{align*} | ||
+ | u^{17} v^{16} a + u^{16} v^{16} b + v^{16} &= 0, \ | ||
+ | u^{16} v^{17} a + u^{16} v^{16} b + u^{16} &= 0. | ||
+ | \end{align*} | ||
+ | Now subtracting, we get <cmath>a(u^{17}v^{16} -u^{16} v^{17}) = u^{16}-v^{16} \implies a = \frac{u^{16} - v^{16}}{u^{17}v^{16} -u^{16} v^{17}}.</cmath> | ||
+ | By Vieta's, <math>uv=-1</math> so the denominator becomes <math>u-v</math>. By difference of squares and dividing out <math>u-v</math> we get <cmath>a= (u^8+v^8)(u^4+v^4)(u^2+v^2)(u+v).</cmath> A simple exercise of Vieta's gets us <math>a= \boxed{987}.</math> | ||
+ | |||
+ | ~bobthegod78 | ||
== See also == | == See also == |
Revision as of 20:36, 30 August 2021
Contents
[hide]Problem
Find if and are integers such that is a factor of .
Solution 1 (Fibonacci Numbers)
Let represent the th number in the Fibonacci sequence. Therefore, The above uses the similarity between the Fibonacci recursion|recursive definition, , and the polynomial .
Solution 2 (Fibonacci Numbers)
We can long divide and search for a pattern; then the remainder would be set to zero to solve for . Writing out a few examples quickly shows us that the remainders after each subtraction follow the Fibonacci sequence. Carrying out this pattern, we find that the remainder is Since the coefficient of must be zero, this gives us two equations, and . Solving these two as above, we get that .
There are various similar solutions which yield the same pattern, such as repeated substitution of into the polynomial with a higher degree, as shown in Solution 6.
Solution 3 (Fibonacci Numbers: For Beginners, Less Technical)
Trying to divide by would be very tough, so let's try to divide using smaller degrees of . Doing , we get the following systems of equations: Continuing with : There is somewhat of a pattern showing up, so let's try to verify. We get: Now we begin to see that our pattern is actually the Fibonacci Numbers! Using the previous equations, we can make a general statement about : Also, noticing our solutions from the previous systems of equations, we can create the following statement:
If has as a factor, then and
Thus, if has as a factor, we get that and so .
Solution 4 (Fibonacci Numbers: Not Rigorous)
Let's work backwards! Let and let be the polynomial such that .
Clearly, the constant term of must be . Now, we have where is some coefficient. However, since has no term, it must be true that .
Let's find now. Notice that all we care about in finding is that . Therefore, . Undergoing a similar process, , , , and we see a nice pattern. The coefficients of are just the Fibonacci sequence with alternating signs! Therefore, , where denotes the 16th Fibonnaci number and .
Solution 5 (Fibonacci Numbers)
The roots of are (the Golden Ratio) and . These two must also be roots of . Thus, we have two equations: Subtract these two and divide by to get Noting that the formula for the th Fibonacci number is , we have . Since and are coprime, the solutions to this equation under the integers are of the form and , of which the only integral solutions for on are and . cannot work since does not divide , so the answer must be . (Note that this solution would not be valid on an Olympiad or any test that does not restrict answers as integers between and ).
Solution 6 (Decreases the Powers)
We are given that is a factor of so the roots of must also be roots of
Let be a root of so that or It follows that Note that We rewrite the left side of as a linear expression of Since this linear equation has two solutions of it must be an identity. Therefore, we have the following system of equations: To eliminate we multiply the first equation by and multiply the second equation by then subtract the resulting equations: from which ~MRENTHUSIASM
Solution 7 (Use the roots)
For simplicity, let and . Notice that the roots of are also roots of . Let these roots be . We get the system
~bobthegod78
See also
1988 AIME (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.