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). Hint: the answer is much smaller than you might believe!

Note: This problem was the October Conundrum challenge at Williams College. Communicated by Michael Biro.