Polynomial Discovery Algorithm Puzzle
Not what you're looking for?
A student thinks of a polynomial p(x) of arbitrary degree, and non-negative integer coefficients. How can you determine the student's polynomial by asking for two values of her polynomial, say p(a) and p(b), where a and b are positive integers? Hint: A positive integer n can be written uniquely in base k, where k is a positive integer. This follows directly by a repeated application of the division algorithm.
Purchase this Solution
Solution Summary
This solution shows, with justification, how to discover a polynomial given only two evaluations of the polynomial. It lays out why the solution works, and the thought process involved in arriving at the solution.
The solution is both plain text, and in a Word document to use equations for clarity.
Solution Preview
Let's let the unknown coefficients of the student's polynomial be c_i (meaning "c sub i"), so that
p(x) = sum( c_i * x^i ) for i = 0 to infinity
OK, we need to think of values for a and b which will allow us to reconstruct her polynomial. I conclude that the problem is assuming we can specify a, and then choose b given p(a), especially given the hint. In fact, we can't even choose a and b at the same time and be able to reconstruct p(x) from the response. For example, if we got the response p(a) = ab + a^2, and p(b) = ab + b^2 (whatever those numbers work out to be), we wouldn't know if the student had p(x) = ab + x^2, or p(x) = (a+b)x.
We want to find the values of c_i. So let's choose a, get an answer, and then choose b. The idea will be to choose an a such that we can then choose a b and be guaranteed of knowing the c_i. I'll go through the logic first, then the motivation in figuring ...
Purchase this Solution
Free BrainMass Quizzes
Exponential Expressions
In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.
Know Your Linear Equations
Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts