Explore BrainMass

Polynomial Discovery Algorithm Puzzle

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.

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 ...

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.