Fibonacci(x)
A polynomial f ( x ) has all integer coefficients. Also, f ( x ) = x ONLY when x = 1 , 2 , 3 , 5 , 8 . Find the smallest positive integer solution for f ( 9 ) .
Assume
-you may use a calculator for, +,-,/,*
The answer is 1353.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
my 1000 th problem
Why must the function look like that? Why can't we get it to be any smaller?
Is that the only integer polynomial function that works? Why, or why not?
Log in to reply
Suppose there's some polynomial that has this property. Subtract
x
from it. The function then has the roots
(
1
,
2
,
3
,
5
,
8
)
and no others, which means it's a
5
t
h
order polynomial. You can recombine some integer multiple of
(
x
−
1
)
(
x
−
2
)
(
x
−
3
)
(
x
−
5
)
(
x
−
8
)
with
x
, and the resulting polynomial will work. But for the smallest positive value
f
(
9
)
, the multiple has to be
1
, as those factors are all positive for
x
>
8
.
Log in to reply
There could be different interpretations of the setup. For example, if f ( x ) = x holds only for x = 1 , 2 , 3 , 5 , 8 and no other integers / real numbers / complex numbers, then the case is different.
The set of functions which satisfy the conditions are
f ( x ) = x + ( x − 1 ) ( x − 2 ) ( x − 3 ) ( x − 5 ) ( x − 8 ) g ( x )
where g ( x ) is an integer polynomial with no integer / real / complex solutions. In each of these scenarios, we know that g ( 9 ) ≥ 1 , and hence the answer is 1353.
However, to answer the question of "Is this the only polynomial", then it depends on which scenario we are in.
For the case of no complex solutions, the only possibility as mentioned is g ( x ) = 1 . (Do you know how to show this?)
For the case of no real solutions, we have other possibilities like g ( x ) = h ( x ) 2 ( x − 9 ) 2 + 1 , where h ( x ) is any integer polynomial. (Do you know how to show this?)
For the case of no integer solutions, I'm not too sure how to classify the solutions. We could have things like g ( x ) = 2 x − 1 7 .
Log in to reply
@Calvin Lin – Let's call x − 1 ) ( x − 2 ) . . . ( x − 8 ) = t so the equation becomes f ( x ) = x + t . To solve for f ( x ) = x , we must find t=0, which occurs at x=1,2,3,5,8. We can't multiply t by p ( x ) = ( x − n ) because that would cause f(x)=x at x=n and the question states that f(x) can only equal x when x=1,2,3,5,8. However, if n=1,2,3,5,8, then the function will only get larger if x=9. Also, we cant change one of the binomials to be smaller than it is (Exg: changing (x-1) to ( 2 x − 1 because that would cause the function to have non integer coefficients. Also, the smallest values we can change t and x by are 1,-1. We cant change t by -1 because that would make the answer negative and the question asks for the smallest possible positive answer. Finally, all polynomial a have roots weather real or imaginary (unless R ( x ) = W where w is a constant such as 6). So if we multiply t by z(x), then f(x) will equal x when z(x)=0, therefore, t cannot be manipulated.
@Calvin Lin – That "integer multiple" would be g ( 9 ) , and you can't get it smaller than 1 and still be positive. All we'll be doing is saying it's "at least" a 5 t h order polynomial. There's no getting around that those factors still have to be present.
Nice proof, I was just about to type out mine but you got to it first.
@Calvin Lin : Have you locked this discussion? :/
Log in to reply
If you can add a comment to this, it is not locked right?
We (generally) only lock solution commenting for problems that are sent out to new members, to reduce the complexity of the experience for them.
I would replace the word "function" in the problem by "polynomial." Otherwise it doesn't make sense to speak of "coefficients."
In the short, the equation will look like this f ( x ) = x + ( x − 1 ) ( x − 2 ) ( x − 3 ) ( x − 5 ) ( x − 8 ) .
Plugging in x=9, we find the answer to be 1 3 5 3