If $c$ is not an integer, the $k$ given by Alice is trivially 0, and it wastes Bob one dollar. Therefore, let $c$ be an integer. Suppose in the $i$-th round, Bob asks $c_i$. If Bob asks less than $n+1$ times, then Alice can construct $P(x)=a\prod_{i=1}^n(x-c_i)+x$, and Bob still doesn't know the value of $a$. For any $c_{n+1}$ Bob asks, $k_{n+1}$ can be 1 if $a=0$, or be 0 if $a$ is large enough. Therefore, Bob should ask at least $n+1$ times. Let's construct a stragey for Bob to ask at most $n+1$ times. Let $c_i=i$, the game ends if $k_i=0$ for some $i$, or $k_1, k_2, \dots, k_{n+1}\neq 0$. $\because a-b|P(a)-P(b)$, which means the solution to $1, 2, \dots, n+1$ is $n+1$ consecutive integers, ensuring that $P(x)=\pm x+c$. $\Rightarrow$ no integer $k$ such that no roots of $P(x)=k$ exists. Therefore, the answer is $n+1$.

If $P (x)=xQ (x)+a $ then pick the sequence of $\{p_1-1,p_2-a,\hdots,\}$ with each $p_i $ is a prime. $xQ(x) $ can't be a prime for infinite value of $x $ if $Q(x)\ne 1. $ Except that, all the answers are possible for $k.$ Bob need to check if $Q(x)=1,P(x)=x+a. $ When he knows that $\deg P\le n $ he can check by $n $ at most $n $ question. The simple questions with $n $ consecutive numbers. If in each answer it shows yes, then $P (x) $ and $x $ in each question will be $2$ consecutive number if $P (x_1)-P (x_2)=1, x_1-x_2$ divided by $1. $ The polynomial $P (x)-P (x-1) $ has degree at most $n-1. $ To check if it is $\ne 1$ we need at most $n-1$ or at most $n $ questions

sn6dh wrote: If $c$ is not an integer, the $k$ given by Alice is trivially 0, and it wastes Bob one dollar. Therefore, let $c$ be an integer. Suppose in the $i$-th round, Bob asks $c_i$. If Bob asks less than $n+1$ times, then Alice can construct $P(x)=a\prod_{i=1}^n(x-c_i)+x$, and Bob still doesn't know the value of $a$. For any $c_{n+1}$ Bob asks, $k_{n+1}$ can be 1 if $a=0$, or be 0 if $a$ is large enough. Therefore, Bob should ask at least $n+1$ times. Let's construct a stragey for Bob to ask at most $n+1$ times. Let $c_i=i$, the game ends if $k_i=0$ for some $i$, or $k_1, k_2, \dots, k_{n+1}\neq 0$. $\because a-b|P(a)-P(b)$, which means the solution to $1, 2, \dots, n+1$ is $n+1$ consecutive integers, ensuring that $P(x)=\pm x+c$. $\Rightarrow$ no integer $k$ such that no roots of $P(x)=k$ exists. Therefore, the answer is $n+1$. It is not immediately clear that solutions to P(x)=k to consecutive k differs by \pm 1 implies the sequence of the solutions to P(x)=k forms an arithmetic sequence of difference \pm 1. Can you please elaborate on why? I tried using the "What Alice could (have) construct" type of argument but failed. I could show that if P(x) = k has multiple solutions for some k, then it has no solution to some other k using a bit calculus, which validates your answer. But I fail to understand your solution without the need of this fact.

We can prove that if $P(x) = k$ has multiple solutions for some k, then it has no solution to some other $k'$. In fact, we can prove even stronger: Quote: Claim: There's no $k$ such that $P(x) = k$ has no integer solution if and only if $P(x) = x+c$ or $-x+c$ for some $c$. which implies that if $P(x) = k$ has multiple solution, it is not of the form $\pm x + c$, so there is in fact a $k$ so that $P(x) = k$ has no integer solution. Proof of the Claim. The converse clearly holds, now suppose $P(x) = k$ always has an integer solution. Write $P(x) = a_mx^m + ... + a_0$ with W.L.O.G $a_m>0$. Expanding, it's straightforward to see $\lim_{n \to \infty} P(n+1) - P(n) = ... + a_2 ( 2n + 1 ) + a_1 = \infty$ for any $m \geq 2$. If $m \geq 2$ is even, $P(x)$ is bounded below since $\lim_{x \to \infty} P(x) = \lim_{x \to -\infty} P(x) = \infty$, implying that $\exists X_+, X_-$ so that $\forall x > X_+ (P(x) > 0)$ and $\forall x < X_- (P(x)>0)$, but then $[X_-, X_+]$ is compact (Heine Borel) or empty (which is trivial), and thus $\{ P(x) | x \in [X_-, X_+] \} $achieves a minimum $m_0$, then $m = \min\{m_0, 0\}$ gives the desired lower bound. So this contradicts our hypothesis since $P(x) = {\lfloor m \rfloor}-1$ has no solution. If $m \geq 3$ is odd, we claim that $P(n)$ when $n$ is large must skip some integer value in its range. Recall that $\lim_{n \to \infty} P(n+1) - P(n) = \infty$, so in particular $\exists X_0$ so that $\forall n \in \mathbb{N} (n > X_0 \implies P(n+1) - P(n) > 1)$. Similarly $\{ P(x) | x \in (- \infty, X_0] \}$ must be bounded above (as $P(x) \to -\infty$ as $x \to -\infty$, and the rest is bounded using compactness), say by $M$. Now say $P(x) > M$ whenever $x > X_1$, then pick any integer $n_0 > \max \{ X_0, X_1 \}$. Claim. $P(n)$ must skip the value of $P(n_0)+1$. (1) $n \leq X_0$, then $P(n) \leq M < P(n_0) < P(n_0) +1$ since $n_0 > X_1$. (2) $n > X_0$ and $n \leq n_0$, then $P(n) \leq P(n_0) < P(n_0)+1$ since $P(n+1) > P(n)+1$ whenever $n > X_0$. (3) $n > X_0$ and $n \geq n_0+1$, then $P(n) \geq P(n_0+1) \gneq P(n_0) + 1$ since, again, $P(n+1) > P(n)+1$ whenever $n > X_0$. So this leaves $P(x)$ constant (which clearly doesn't satisfy our assumption) or $P(x) = ax+b$ with $a \neq 0$. It is then easy to see that $a = \pm 1$, ending our proof. Hope this clarifies my comment. I would really like to know if there's an approach not needing this fact.

Acclab wrote: sn6dh wrote: If $c$ is not an integer, the $k$ given by Alice is trivially 0, and it wastes Bob one dollar. Therefore, let $c$ be an integer. Suppose in the $i$-th round, Bob asks $c_i$. If Bob asks less than $n+1$ times, then Alice can construct $P(x)=a\prod_{i=1}^n(x-c_i)+x$, and Bob still doesn't know the value of $a$. For any $c_{n+1}$ Bob asks, $k_{n+1}$ can be 1 if $a=0$, or be 0 if $a$ is large enough. Therefore, Bob should ask at least $n+1$ times. Let's construct a stragey for Bob to ask at most $n+1$ times. Let $c_i=i$, the game ends if $k_i=0$ for some $i$, or $k_1, k_2, \dots, k_{n+1}\neq 0$. $\because a-b|P(a)-P(b)$, which means the solution to $1, 2, \dots, n+1$ is $n+1$ consecutive integers, ensuring that $P(x)=\pm x+c$. $\Rightarrow$ no integer $k$ such that no roots of $P(x)=k$ exists. Therefore, the answer is $n+1$. It is not immediately clear that solutions to P(x)=k to consecutive k differs by \pm 1 implies the sequence of the solutions to P(x)=k forms an arithmetic sequence of difference \pm 1. Can you please elaborate on why? I tried using the "What Alice could (have) construct" type of argument but failed. I could show that if P(x) = k has multiple solutions for some k, then it has no solution to some other k using a bit calculus, which validates your answer. But I fail to understand your solution without the need of this fact. I set $c_j=c_0+2\lceil j/2\rceil+11\lfloor j/2\rfloor,j=1,\cdots,n$ with $c_0=0,$ and it seems also work XD. That is $\{c_j\}_{j=0}^{n}=\{0,2,13,15,26,\cdots\}$ If $|k_j-k_{j+1}|=1$ or $(k_j-k_{j+1})(k_{j+1}-k_{j+2})<0,$ then $c_{j-1}-c_{j+1}\nmid k_{j-1}-k_{j+1}$ or $c_{j}-c_{j+2}\nmid k_{j}-k_{j+2}$ But it still relies on your claim.