, 2021

B must pay at least $n+1$ dollars.

We first prove: if for all $c \in [0, n] \cap \mathbb{Z}$, $P(x) = c$ has an integer solution, then $P(x) = \pm x + d$, where $d$ is some constant. We need the following lemma:

Lemma. If an integer-coefficient polynomial $P(x)$ satisfies $P(a) = k$, $P(b) = k + 1$ where $a, b$ are both integers, then $|a - b| = 1$.

(Proof of lemma: since $b - a \mid P(b) - P(a) = 1$, we have $|a - b| = 1$.)

Returning to the original problem. By assumption, there exist $a_0, a_1, \dots, a_n$ respectively such that $P(a_i) = i, i = 0, 1, \dots, n$. By the lemma, $|a_i - a_{i+1}| = 1$ holds for all $i = 0, 1, \dots, n-1$. But since these $a_i$ are pairwise distinct, $a_0, \dots, a_n$ must form an arithmetic sequence with common difference $1$ or $-1$.

Let us first discuss the case where the common difference is $1$: since $P(a_0) = 0$, we have $P(x) = (x - a_0)Q(x)$, where $Q$ has degree not exceeding $n-1$. But substituting $a_i$ again gives $Q(a_i) = 1, i = 1, 2, \dots, n$, so $Q(x)$ is the constant polynomial $1$, and $P(x) = x - a_0$.

Similarly, when the common difference is $-1$, $P(x) = -(x - a_0)$.

Based on the above, B only needs to query $P(x) = c, c = 0, 1, \dots, n$ in sequence. If any one of these $c$ has no integer solution, B has achieved his goal. Otherwise $P(x) = c$ has an integer solution for every integer $c \in [0, n]$, so $P(x) = \pm x + d$, and it follows that $P(x) = k$ has an integer solution for every integer $k$, so B has also achieved his goal.

Therefore B can always achieve his goal after at most $n+1$ queries.

On the other hand, if B only makes $n$ queries, suppose without loss of generality that the integers $c$ he asks about are $c_1, c_2, \dots, c_n$ respectively. Then consider the following two polynomials:
$$P_1(x) = x + A \prod_{i=1}^{n} (x - c_i), \quad P_2(x) = x.$$
As long as $A$ is taken sufficiently large, then $P_1(x) = c_i$ has only one integer solution $x = c_i$, and simultaneously $P_2(x) = c_i$ also has only one integer solution $x = c_i$, so B cannot distinguish between these two polynomials. But the answers given by these two polynomials are not the same, which shows that B cannot achieve his goal at this point.