Question 36
Let $n$ be a given positive integer. Alice and Bob play a game. Alice chooses a polynomial $P(x)$ with integer coefficients and degree at most $n$, without telling Bob what it is. Bob must determine whether there is an integer $k$ for which $P(x)=k$ has no integer solution. Bob may ask the following type of question: he specifies a constant $c$, and Alice tells him how many integers $t$ satisfy $P(t)=c$. Each question costs one dollar. What is the minimum amount Bob must pay to guarantee that he achieves his goal?