Players Alfred and Bertrand jointly define a polynomial $x^{n}+a_{n-1} x^{n-1}+\cdots+a_{0}$ with a given degree $n \geq 2$. They do this by alternately choosing the value of one coefficient in $n$ moves, where all coefficients must be integers and $a_{0} \neq 0$ must hold. Alfred is the first to move. Alfred wins if the polynomial has an integer root at the end.

(a) For which $n$ can Alfred force a win if the coefficients $a_{j}$ are set from right to left, i.e., for $j=0,1, \ldots, n-1$?

(b) For which $n$ can Alfred force a win if the coefficients $a_{j}$ are set from left to right, i.e., for $j=n-1, n-2, \ldots, 0$?

(Theresia Eisenkölbl, Clemens Heuberger)

Answer. In both cases, Alfred can force a win if and only if $n$ is odd.
(a) If Alfred is the last to move, he simply sets 1 and obtains a linear equation in $a_{n-1}$ for 1 to be a root. Since $a_{n-1}$ appears with a coefficient of 1 in this linear equation, it has an integer solution.

If Bertrand is the last to move, integer roots can only arise for the divisors of the constant term. This gives him finitely many linear equations in the coefficient $a_{n-1}$ for one of these divisors of the constant term to be a root, and he chooses $a_{n-1}$ differently.

(b) If Alfred is the last to move, he writes $P(x) = x Q(x) + a_{0}$. He chooses an integer $y \neq 0$ with $Q(y) \neq 0$ (which is certainly possible because $Q(x)$ is not the zero polynomial) and sets $a_{0} = -y Q(y)$. It follows that $a_{0} \neq 0$ and $P(y) = 0$.

If Bertrand is the last to move, he also writes

$$
P(x) = x Q(x) + a_{0}
$$

and chooses a prime $p$ that is neither one of the finitely many roots of $Q(x) + 1 = 0$ or $Q(-x) - 1 = 0$ nor equal to $-Q(1)$ or $Q(-1)$. He now sets $a_{0} = p$. The conditions ensure that $P(\pm p) \neq 0$ and $P(\pm 1) \neq 0$ hold, and therefore $P$ has no integer root. Thus, Alfred can ensure victory exactly when he is the last to move, i.e., when $n$ is odd.

(Clemens Heuberger)