Problem 1

Let $d$ and $m$ be two fixed strictly positive integers. Pinocchio and Geppetto know the values of $d$ and $m$, and play the following game. First, Pinocchio chooses a polynomial $P$ of degree at most $d$ with coefficients in $\mathbb{Z}$. Then, Geppetto asks him questions of the form “What is the value of $P(n)$?”, where $n \in \mathbb{Z}$. Pinocchio usually tells the truth, but he can lie up to $m$ times. What is, in terms of $d$ and $m$, the minimum number of questions that Geppetto must ask to be sure to determine $P$ regardless of Pinocchio's answers?

Note: $\mathbb{Z}$ denotes the set of integers, regardless of their sign.
Solution

The minimum number sought is $2 m+d+1$.

First, let's show that Geppetto can find $P$ with $2 m+d+1$ questions. Geppetto asks Pinocchio the value of $P(t)$ for $2 m+d+1$ distinct integer values. Suppose, for the sake of contradiction, that there exist two distinct polynomials $P_{1}, P_{2} \in \mathbb{Z}[x]$ of degree at most $d$ that each do not pass through more than $m$ points $(t, P(t))$ given by Pinocchio. Therefore, there are at least $d+1$ of these points through which both $P_{1}$ and $P_{2}$ pass. Since these are two polynomials of degree at most $d$, this implies that $P_{1}=P_{2}$, leading to the desired contradiction. Geppetto can determine the polynomial $P$ by trying the $(\underset{d+1}{2 m+d+1})(d+1)$-tuples of points and, for each of them, computing the unique polynomial that passes through these points (Lagrange polynomial) and verifying that it passes through at least $m+d+1$ of these points.

Now, suppose that Geppetto can find the polynomial by asking only $2 m+d$ questions. In this case, Pinocchio chooses a polynomial $P$ of degree at most $d$ in $\mathbb{Z}[x]$ (for example, $x^{d}$). He then honestly answers the first $d$ questions from Geppetto, indicating that $P$ passes through the points $\left(a_{1}, P\left(a_{1}\right)\right), \ldots,\left(a_{d}, P\left(a_{d}\right)\right)$. At this point, $P$ is a potential solution for Geppetto, but so is $Q=P+\prod_{i=1}^{d}\left(x-a_{i}\right)$. Pinocchio then honestly answers the next $m$ questions and responds as if the chosen polynomial were $Q$ to the last $m$ questions. Both polynomials $P$ and $Q$ are therefore valid in Geppetto's eyes, and he cannot choose the correct one with certainty.