Difference between revisions of "1988 AIME Problems/Problem 13"
MRENTHUSIASM (talk | contribs) m (→Solution 3 (Fibonacci Version 3: For Beginners, Less Technical)) |
Jonathan.li (talk | contribs) (→Solution 9 (mod)) |
||
(22 intermediate revisions by 4 users not shown) | |||
Line 48: | Line 48: | ||
Thus, if <math>ax^{17}+bx^{16}+1</math> has <math>x^2-x-1</math> as a factor, we get that <math>a = 987</math> and <math>b = -1597,</math> so <math>a = \boxed {987}</math>. | Thus, if <math>ax^{17}+bx^{16}+1</math> has <math>x^2-x-1</math> as a factor, we get that <math>a = 987</math> and <math>b = -1597,</math> so <math>a = \boxed {987}</math>. | ||
− | == Solution 4 (Fibonacci | + | == Solution 4 (Fibonacci Numbers: Not Rigorous)== |
Let's work backwards! Let <math>F(x) = ax^{17} + bx^{16} + 1</math> and let <math>P(x)</math> be the polynomial such that <math>P(x)(x^2 - x - 1) = F(x)</math>. | Let's work backwards! Let <math>F(x) = ax^{17} + bx^{16} + 1</math> and let <math>P(x)</math> be the polynomial such that <math>P(x)(x^2 - x - 1) = F(x)</math>. | ||
Line 55: | Line 55: | ||
Let's find <math>c_{14}</math> now. Notice that all we care about in finding <math>c_{14}</math> is that <math>(x^2 - x - 1)(\cdots + c_{14}x^2 + x - 1) = \text{something} + 0x^2 + \text{something}</math>. Therefore, <math>c_{14} = - 2</math>. Undergoing a similar process, <math>c_{13} = 3</math>, <math>c_{12} = - 5</math>, <math>c_{11} = 8</math>, and we see a nice pattern. The coefficients of <math>P(x)</math> are just the Fibonacci sequence with alternating signs! Therefore, <math>a = c_1 = F_{16}</math>, where <math>F_{16}</math> denotes the 16th Fibonnaci number and <math>a = \boxed{987}</math>. | Let's find <math>c_{14}</math> now. Notice that all we care about in finding <math>c_{14}</math> is that <math>(x^2 - x - 1)(\cdots + c_{14}x^2 + x - 1) = \text{something} + 0x^2 + \text{something}</math>. Therefore, <math>c_{14} = - 2</math>. Undergoing a similar process, <math>c_{13} = 3</math>, <math>c_{12} = - 5</math>, <math>c_{11} = 8</math>, and we see a nice pattern. The coefficients of <math>P(x)</math> are just the Fibonacci sequence with alternating signs! Therefore, <math>a = c_1 = F_{16}</math>, where <math>F_{16}</math> denotes the 16th Fibonnaci number and <math>a = \boxed{987}</math>. | ||
− | == Solution 5 (Fibonacci | + | == Solution 5 (Fibonacci Numbers) == |
The roots of <math>x^2-x-1</math> are <math>\phi</math> (the Golden Ratio) and <math>1-\phi</math>. These two must also be roots of <math>ax^{17}+bx^{16}+1</math>. Thus, we have two equations: | The roots of <math>x^2-x-1</math> are <math>\phi</math> (the Golden Ratio) and <math>1-\phi</math>. These two must also be roots of <math>ax^{17}+bx^{16}+1</math>. Thus, we have two equations: | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
Line 63: | Line 63: | ||
Subtract these two and divide by <math>\sqrt{5}</math> to get <cmath>\frac{a(\phi^{17}-(1-\phi)^{17})}{\sqrt{5}}+\frac{b(\phi^{16}-(1-\phi)^{16})}{\sqrt{5}}=0.</cmath> Noting that the formula for the <math>n</math>th Fibonacci number is <math>\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}</math>, we have <math>1597a+987b=0</math>. Since <math>1597</math> and <math>987</math> are coprime, the solutions to this equation under the integers are of the form <math>a=987k</math> and <math>b=-1597k</math>, of which the only integral solutions for <math>a</math> on <math>[0,999]</math> are <math>0</math> and <math>987</math>. <math>(a,b)=(0,0)</math> cannot work since <math>x^2-x-1</math> does not divide <math>1</math>, so the answer must be <math>\boxed{987}</math>. (Note that this solution would not be valid on an Olympiad or any test that does not restrict answers as integers between <math>000</math> and <math>999</math>). | Subtract these two and divide by <math>\sqrt{5}</math> to get <cmath>\frac{a(\phi^{17}-(1-\phi)^{17})}{\sqrt{5}}+\frac{b(\phi^{16}-(1-\phi)^{16})}{\sqrt{5}}=0.</cmath> Noting that the formula for the <math>n</math>th Fibonacci number is <math>\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}</math>, we have <math>1597a+987b=0</math>. Since <math>1597</math> and <math>987</math> are coprime, the solutions to this equation under the integers are of the form <math>a=987k</math> and <math>b=-1597k</math>, of which the only integral solutions for <math>a</math> on <math>[0,999]</math> are <math>0</math> and <math>987</math>. <math>(a,b)=(0,0)</math> cannot work since <math>x^2-x-1</math> does not divide <math>1</math>, so the answer must be <math>\boxed{987}</math>. (Note that this solution would not be valid on an Olympiad or any test that does not restrict answers as integers between <math>000</math> and <math>999</math>). | ||
− | == Solution 6 ( | + | == Solution 6 (Reduces the Powers) == |
We are given that <math>x^2 - x - 1</math> is a factor of <math>ax^{17} + bx^{16} + 1,</math> so the roots of <math>x^2 - x - 1</math> must also be roots of <math>ax^{17} + bx^{16} + 1.</math> | We are given that <math>x^2 - x - 1</math> is a factor of <math>ax^{17} + bx^{16} + 1,</math> so the roots of <math>x^2 - x - 1</math> must also be roots of <math>ax^{17} + bx^{16} + 1.</math> | ||
− | Let <math>x=r</math> be a root of <math>x^2 - x - 1</math> so that <math>r^2 - r - 1 = 0,</math> or <math>r^2 = r + 1.</math> It follows that <cmath>ar^{17} + br^{16} + 1 = 0. \hspace{ | + | Let <math>x=r</math> be a root of <math>x^2 - x - 1</math> so that <math>r^2 - r - 1 = 0,</math> or <math>r^2 = r + 1.</math> It follows that <cmath>ar^{17} + br^{16} + 1 = 0. \hspace{20mm} (\bigstar)</cmath> |
Note that | Note that | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
Line 80: | Line 80: | ||
&= 441r^2 + 546r + 169 \\ | &= 441r^2 + 546r + 169 \\ | ||
&= 441(r+1) +546r + 169 \\ | &= 441(r+1) +546r + 169 \\ | ||
− | &= 987r + 610 | + | &= 987r + 610. |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | + | We rewrite the left side of <math>(\bigstar)</math> as a linear expression of <math>r:</math> | |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
(ar+b)r^{16} + 1 &= 0 \\ | (ar+b)r^{16} + 1 &= 0 \\ | ||
Line 88: | Line 88: | ||
987ar^2 + (610a+987b)r + 610b + 1 &= 0 \\ | 987ar^2 + (610a+987b)r + 610b + 1 &= 0 \\ | ||
987a(r+1) + (610a+987b)r + 610b + 1 &= 0 \\ | 987a(r+1) + (610a+987b)r + 610b + 1 &= 0 \\ | ||
− | (1597a+987b)r + 987a + 610b + 1 &= 0. | + | (1597a+987b)r + (987a + 610b + 1) &= 0. |
\end{align*}</cmath> | \end{align*}</cmath> | ||
Since this linear equation has two solutions of <math>r,</math> it must be an identity. Therefore, we have the following system of equations: | Since this linear equation has two solutions of <math>r,</math> it must be an identity. Therefore, we have the following system of equations: | ||
Line 107: | Line 107: | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
~MRENTHUSIASM | ~MRENTHUSIASM | ||
+ | |||
+ | == Solution 7 (Uses 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 | ||
+ | <cmath>\begin{align*} | ||
+ | au^{17} + bu^{16} + 1 &= 0, \\ | ||
+ | av^{17} + bv^{16} + 1 &= 0. | ||
+ | \end{align*}</cmath> | ||
+ | If we multiply the first equation by <math>v^{16}</math> and the second by <math>u^{16}</math> we get <cmath>\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*}</cmath> | ||
+ | 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 | ||
+ | |||
+ | == Solution 8 (Engineer's Induction, only use if you don't have time left) == | ||
+ | |||
+ | We see that <math>ax^{17} + bx^{16} + 1 = (x^2-x-1)P(x)</math> for some polynomial <math>P(x)</math>. Working forwards, we notice that the constant term of <math>P(x)</math> must equal <math>-1</math>, to multiply the constant term of <math>(x^2-x-1)</math> into <math>1</math>. We can similarly continue to use this logic, by repeatedly cancelling out the middle term, and obtain the process: | ||
+ | <math>(x^2-x-1)(-1) = -x^2 + x + 1</math> | ||
+ | <math>(x^2-x-1)(-1 + x) = x^3 - 2x^2 + 1</math> | ||
+ | <math>(x^2-x-1)(-1 + x - 2x^2) = -2x^4 + 3x^3 + 1</math> | ||
+ | <math>(x^2-x-1)(-1 + x - 2x^2 + 3x^3) = 3x^5 - 5x^4 + 1</math>. | ||
+ | By this time, you can hopefully notice that the coefficient of the <math>x^n</math> term in <math>P(x)</math> is equal to <math>(-1)^{n-1} * F_{n}</math>, where <math>F_n</math> equals the <math>n</math>th number in the Fibonacci sequence. From here, we just need to find the coefficient of the <math>x^15</math> term in <math>P(x)</math>, which happens to be <math>F_15 = \boxed{987}</math>. | ||
+ | Again, try to only use Engineer's Induction when you have no other options. A rigorous proof is usually not needed, but when you have extra time, checking a solution with a rigorous method is better than worrying about your Engineer's Induction solution. | ||
== See also == | == See also == |
Latest revision as of 02:27, 30 June 2024
Contents
- 1 Problem
- 2 Solution 1 (Fibonacci Numbers)
- 3 Solution 2 (Fibonacci Numbers)
- 4 Solution 3 (Fibonacci Numbers: For Beginners, Less Technical)
- 5 Solution 4 (Fibonacci Numbers: Not Rigorous)
- 6 Solution 5 (Fibonacci Numbers)
- 7 Solution 6 (Reduces the Powers)
- 8 Solution 7 (Uses the Roots)
- 9 Solution 8 (Engineer's Induction, only use if you don't have time left)
- 10 See also
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 (Reduces 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 (Uses the Roots)
For simplicity, let and
. Notice that the roots of
are also roots of
. Let these roots be
. We get the system
If we multiply the first equation by
and the second by
we get
Now subtracting, we get
By Vieta's,
so the denominator becomes
. By difference of squares and dividing out
we get
A simple exercise of Vieta's gets us
~bobthegod78
Solution 8 (Engineer's Induction, only use if you don't have time left)
We see that for some polynomial
. Working forwards, we notice that the constant term of
must equal
, to multiply the constant term of
into
. We can similarly continue to use this logic, by repeatedly cancelling out the middle term, and obtain the process:
.
By this time, you can hopefully notice that the coefficient of the
term in
is equal to
, where
equals the
th number in the Fibonacci sequence. From here, we just need to find the coefficient of the
term in
, which happens to be
.
Again, try to only use Engineer's Induction when you have no other options. A rigorous proof is usually not needed, but when you have extra time, checking a solution with a rigorous method is better than worrying about your Engineer's Induction solution.
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.