MathDB

Let

d

and

m

be two fixed positive integers. Pinocchio and Geppetto know the values of

d

and

m

and play the following game: In the beginning, Pinocchio chooses a polynomial

P

of degree at most

d

with integer coefficients. Then Geppetto asks him questions of the following form "What is the value of

P(n)

?'' for

n \in \mathbb{Z}

. Pinocchio usually says the truth, but he can lie up to

m

times. What is, as a function of

d

and

m

, the minimal number of questions that Geppetto needs to ask to be sure to determine

P

, no matter how Pinocchio chooses to reply?

Problem Statement