Explore BrainMass

Explore BrainMass

    Polynomial Discovery Algorithm Puzzle

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com October 9, 2019, 9:06 pm ad1c9bdddf

    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.