I got this problem from Rustan Leino, who was told it by Prakash Panangaden.

I solved it and wrote up my solution.

There's a polynomial and you have access to a function that evaluates that polynomial at a given number. You don't know the degree of the polynomial, nor do you know any of the coefficients of its terms. However, you're told that all coefficients are non-negative integers. How many times do you need to call the evaluation function to identify the polynomial (that is, to figure out the values of its coefficients)?

Twice, by the following reasoning.

First, we prove that twice is sufficient by describing the following algorithm, which only needs two evaluations to work. On the first evaluation, pass an input of 1. If the result is $M,$ you know that $M$ is the sum of all the coefficients. More importantly, you know that, since all the coefficients are non-negative integers, every coefficient is $\leq M$ and thus a valid digit in base $M+1.$ So, on the second evaluation, pass an input of $M+1.$ Expressing the result in base $M+1$ will reveal all the coefficients: for each $i,$ the digit in the $(M+1)^i$'s place in this representation is the coefficient of $x^i$ in the polynomial. After all, there's only one representation of any given number in base $M+1.$

Second, we prove that once is insufficient. If there were an algorithm that only required one evaluation, and its first submitted input was $I,$ then the result might be $I.$ If so, the algorithm would have no way of distinguishing the two polynomials $1x+0$ and $0x+1I,$ either of which could have produced the result.