| |
|
|---|
Amazingly, no matter how large a polynomial Alice picks, you can always find all of the coefficients after just two queries!
Suppose you knew that all of the coefficients were at most 9. Then you could ask her the value of P(10), and the digits of her answer would give the coefficients directly. For instance, if she told you that P(10) were 3721, you could immediately answer that her polynomial is 3x^3 + 7x^2 + 2x + 1.
The same trick works whenever a bound k is known on the values of the coefficients, except that you must work in base k+1. The problem is that we don't know such a bound. No matter how high a bound we guess, it might turn out that she has used a coefficient that is even larger.
To force her to give you a bound on the values of the coefficients, just ask her the value of P(1) for the first question; this is at least as great as any of the coefficients.
This gives us our two-query strategy: ask her the value of P(1), then ask her the value of P(P(1)+1), then return the digits of this number, base P(1) + 1, as the coefficients of her polynomial.
Scott Lundberg and Nicolae Popescu get the ice cream.