Any ideas on how to do this problem? (long) Petya and Vasya play a game, alternating turns in the usual way. Petya starts by choosing a polynomial $P(x)$ with integer coefficients. Each time that it is his turn, Vasya gives 1 dollar to Petya and tells him some integer $a$. Vasya cannot choose the same number twice. Except for his initial turn, Petya responds to Vasya by telling him the number of integer solutions to $P(x)=a$.Vasya wins when Petya tells him a number that was already reported by him (not necessarily on the preceding move). Determine the minimum number of dollars sufficient for Vasya to win the game for sure.
 A: If $P(x)=a$ has at least three distinct solutions $r_1,r_2,r_3,$ then by polynomial division it can be written as $P=(x-r_1)(x-r_2)(x-r_3)Q+a$ for some integer coefficient polynomial $Q.$ This means $P(x)=a\pm 1$ has no solutions: $|(x-r_1)(x-r_2)(x-r_3)Q|=1$ implies $|x-r_i|=1$ for $i=1,2,3,$ which is impossible.
Similarly if $P(x)=a$ has two distinct solutions $r_1,r_2,$ then $P(x)=a\pm 1$ has at most one solution: $|(x-r_1)(x-r_2)Q|=1$ implies $x=r_1+1=r_2-1$ (swapping $r_1$ and $r_2$ if necessary).
This means that as Vasya you can win with four dollars. First say $0$ and $1.$ If the game isn't over, without loss of generality (applying $x\mapsto 1-x$ symmetry) the second response is positive. Say $2.$ If the game isn't over, then without loss of generality (applying $x\mapsto 2-x$ symmetry) the response to $2$ is positive. Say $3.$ If the game got this far, each of $0,1,2,3$ has a neighboring integer that got a positive response: $1,2,1,2$ respectively. So they must each have got a response of at most $2.$ So you win by the pigeonhole principle.
On the other hand, Vasya can't win with three dollars. If Vasya says $a,b,c$ then Petya can reply $0,1,2$ and Vasya will not have won. Petya just needs to have happens to choose a polynomial with the correct number of solutions. For example assume $c-b\neq -1$ (otherwise negate everything) and set $P=(x-c+b)(x+1)((|c-a|+2)x-1)+c.$ Then $P(x)=c$ has exactly two solutions $c-b$ and $-1,$ while $P(x)=b$ has exactly one solution $0,$ and $P(x)=a$ has no solutions.
