Help Bob find Alice's P(x)$%^

[BMAD]

Alice and Bob are playing the following game: Alice has a secret polynomial P(x) = a_0 + a_1 x + a_2 x^2 + … + a_n x^n, with non-negative integer coefficients a_0, a_1, …, a_n. At each turn, Bob picks an integer k and Alice tells Bob the value of P(k). Find, as a function of the degree n, the minimum number of turns Bob needs to completely determine Alice’s polynomial P(x).

[EventHorizon]

Alice is so kinky...

Spoiler

As ThunderCloud noted:

On 3/17/2018 at 4:31 PM, ThunderCloud said:

P(1) is the sum of the coefficients

So that is my first guess.  This lets me know a range that all a_i are in.  They can be from 0 to P(1) since all a_i are non-negative and their sum is P(1).

My second guess is the next higher power of 10 greater than P(1).  From this I can get every a_i since they will essentially all be listed in the response.

For example, lets say P(x) = 4 + 19*x + 23423433*x^2.  P(1) is 4+19+23423433=23423456.  The next higher power of 10 is 100000000.  P(100000000) = 4 + 19 * 100000000 + 23423433*100000000^2 = 234234330000001900000004.  You just need to split the response into groups of digits equal to the number of 0's in the power of 10 guessed, then read off the values.  e.g., (23423433)(00000019)(00000004)

So my number of guesses as a function of n is G(n) = 2.

The only thing this won't find is if Alice is keeping a few trailing 0's secret.  If a_n = 0, the polynomial is identical the polynomial of one lesser degree and no amount of guesses will find how many trailing coefficients are 0.

 

[ThunderCloud]

Hmmm… assuming n is known to Bob, my first thoughts…

Spoiler

Naively, as there are n+1 unknown terms to be found, there would not need to be more than n+1 distinct choices of k to yield a solvable set of linear equations. In particular, P(0) = a_0, P(1) is the sum of the coefficients, P(-1) gives the sum of the even-indexed coefficients minus the sum of the odd-indexed coefficients, etc.

I haven't thought of a way to leverage the fact that each coefficient is an integer ≥ 0 to further reduce the number of P(k)'s Bob would need to fewer than n+1, but there could be one…

 

[BMAD]

n is not known

[ThunderCloud]

14 hours ago, BMAD said:

n is not known

Well, in that case…

Spoiler

Bob can determine a₀ by asking for P(0). After that, Bob can check for additional terms by guessing another positive integer, say, 1; if P(1) is different than P(0), Bob solves for a₁ assuming it is the only remaining term. Bob then tests a new value, maybe P(2)… if it is different than what would be predicted by the polynomial thus far, Bob then re-solves for a₁ and a₂ assuming there are no further remaining terms. Then tests another value… etc. Bob stops when testing confirms his assumption that there are no further terms — because each of the nonzero coefficients is positive, a single unique positive test value could determine whether any additional nonzero terms existed or not.

 

So, all in all, I think that Bob would need n +  2 test values to determine for certain the coefficients of Alice's n-degree polynomial.