Question 936281
Here's a solution: Suppose we played the same game, but you are given that your opponent's polynomial's coefficients are in the range {0,1,...,d-1} for some positive integer d. Then you should ask for P(d). Note that the value of P(d) corresponds to a base-d integer, and it is well known that every positive integer has a unique base-d representation with coefficients in {0,1...,d-1}.


For example, if you know that the coefficients of P(x) are in {0,1,...,9}, then d = 10, and suppose P(10) = a*10^3 + b*10^2 + c*10 + d = 2549. Then P(x) = 2x^3 + 5x^2 + 4x + 9.


To find a value of d, first guess P(1), which is the sum of the coefficients. Since the coefficients are positive integers, P(1) >= d, so you should guess P(1) and then P(P(1)).