Consider the following game: Alice chooses a polynomial p with non-negative integer coefficients and challenges Bob to determine the polynomial. Bob is allowed to ask Alice for the value of p(n) for an n of his choice and upon receiving the answer can ask Alice for the value of p(m) for an m of his choice. Is there a strategy for Bob such that after receiving these two values he can always determine the coefficients of Alice’s polynomial?

On first glance, this looks pretty tough for Bob: Alice has infinitely many choices, and isn’t even constrained in the degree of the polynomial she chooeses. However, there’s a really easy winning strategy for him: first ask for p(1) and then ask for p(m) for any m greater than p(1). That’s it!

### Like this:

Like Loading...

Can you explain why that works? The way I see it, you’re only determining the value of the polynomial at two points, and there are infinitely many polynomials through any given 2 points.

Sure; the strategy given above is really just a hint. As you say, there are infinitely many polynomials passing through any two points, so the restriction to non-negative integer coefficients is vital.

Suppose that p(x) = a_0 + a_1 x + a_2 x^2 + … + a_n x^n. Consider what you get when you divide p(m) by m. As m > a_0 + a_1 + … + a_n, you know that the term a_0/m must be less than 1. Therefore p(m)/m = (something less than one) + a_1 + m(a_2 + … + a_n m^(n-1) ). So if you know m and p(m) you can read off a_1 from this. Now consider p(m) / m^2 = (something less than one) + a_2 + m(something). Is it now clear how you can read off the a_i? It hinges on the fact that (a_0+…a_i)/m < 1 for any i between 0 and n, by the choice of m.

Ankit: Let’s do this for a nice big m. Let’s say n = 9. Then you know the biggest coefficient can’t be more than 9. So you give m = 10 and read off the coefficients in base 10. Similarly if n = 13 you can give m = 16 and read off the coefficients in hex, or instead m = 2934 and read them off in base 2934. Note the constraints in the first paragraph.

Where n=p(1) 🙂

This is the slightly slicker way of thinking about the algorithm I mentioned in my comment.