A secret polynomial

Question

Alice has a secret polynomial $P$ with positive integer coefficients. When Bob gives Alice a positive integer $n \neq 2016$, Alice replies with the value of $P(n)$. After doing this several times, Bob guesses the value of $P(2016)$; he wins if he is correct and loses if not.

How can Bob guarantee a win in as few such exchanges as possible?

Answer 1

Bob can get it in

2 questions.

Here's how:

First guess 1. Then guess a power of 10 greater than the response; he can simply "read off" the coefficients. That uniquely determines the polynomial, so he can just calculate $P(2016)$ for his final answer.

What I mean by the term in quotes:

I'll use the polynomial $17x^4 + 4x^3 + 5x^2 + 8$ as an example: $f(1) = 34$, so I choose any power of ten greater than 34. I pick 1000. $f(1000) = 17004005000008$, and you can easily see the coefficients there, separated by zeroes. (Chunk starting from the right in groups of $n$, where $10^n$ is the number you picked.)

Answer 2

If we allow Bob to ask for values not at positive integers, he can find $P(2016)$ with just one question. He asks for $P(\pi)$ and tells Alice to give him the integral part, then pause until he says start, then keep outputting decimal digits until he says stop. There are only finitely many monomials with values less than this at $\pi$. They can be combined in finitely many ways. He makes a finite list of all the polynomials that produce a value of $P(\pi)$ between the integral part Alice said and $1$ more and computes the decimal expansions until every one differs from the rest. He then asks Alice to start giving him decimals and tells her to stop when he knows the polynomial.

For example, if $100 \le P(\pi) \lt 101$, he can only use constants $1$ through $100$, linear terms $x$ through $31x$, quadratics $x^2$ through $9x^2$, cubics $x^3$ through $4x^3$ and $x^4$. Most combinations of those will be too large, but $97+x$ evaluates to $100.14159$, $x^3+4x^2+60$ evaluates to $100.615$and $x^3+4x^2+x^2+x+27$ to $100.6263$. I don't know how close they can be, but it won't take too many decimals to sort it out.

Answer 3

Post-script. Jared is right and I didn't read the conditions correctly. I missed that the coefficients have to be positive. What I wrote below is rubbish.

He can't. Let S = {s₁, s₂, ... s_n} be the set of numbers on which he could choose to sample P(x) so he will know the values P(s₁), P(s₂), ... P(s_n). Now define the polynomial M_V(x) as Product _{all i in S except V} (x-i) so now M_V(x) is zero everywhere in S but non-zero at x=V. (The value at V is probably quite large)

Alice now chooses a random polynomial Q(x) and a random integer R and adds P(x) and R.M₂₀₁₆(x) to get P(x).

When Bob samples P(x) he gets the values of Q(x) because M₂₀₁₆(x) is zero on all his sample points. He doesn't know R so he can't work out the value P(2016) = Q(2016)+R.M₂₀₁₆(2016)

---

The answer that has been accepted above uses Q(x) = 17x⁴ + 4x³ + 5x² + 8 as an example but P(x) = Q(x) + (x-1)(x-1000) takes exactly the same values at the sample-points of 1 and 1000.