[Prakash Panangaden told me this problem.]

There is 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 are told that all coefficients are non-negative integers. How many times do you need to call the evaluation function in order to identify the polynomial (that is, to figure out the values of its coefficients)?

January 2014