# Determine a polynomial with nonnegative integer coefficients with minimum queries.

A friend of us makes up a polynomial with nonnegative integer coefficients. Our task is to find it out with a minimum number of queries. For each query we give him a nonnegative integer L and he computes P(L) and returns the result to us.

I know the beautiful trick to solve this - first ask P(1) to determine the sum of the coefficients that is at least as great as the greatest coefficent of the polynomial. Let T be the result of P(1). Then we ask P(T + 1). The value we get we covert to T + 1-base positional system and this way we figure the coefficients of the polynomial in 2 queries. I was wondering if it is possible to find it with a single querie or 2 queries is the lower bound of the worst case?

• It is impossible to get it in one query. Notice, for example, that for any number that you pick to evaluate, there are an infinite number of polynomials that pass thru that point. If the point is $c$ then every polynomial multiple of $(x-c)$ is a candidate. – Phicar Mar 21 '20 at 0:24

You give your friend the number $$\pi$$. A polynomial with integer coefficients is completely determined by its value at $$\pi$$. Of course, any transcendental would do, in place of $$\pi$$.