Another polynomial game

Question

I came across the following problem and I'm stumped.

Players X and Y play the following game.

For $n\geq 2$, they consider a monic polynomial with degree $2n$, with undetermined coefficients (except the constant one): $X^{2n}+\square X^{2n-1}+\ldots+\square X+1$

The players take turn to fill the blanks with a real number of their choice.

X wins, if, when completing the last blank square available, the resulting polynomial has no real root. Otherwise Y wins.

If X plays first, who has a winning strategy ?

Answer 1

$Y$ always wins. The strategy for $Y$ is: play all even coefficients as long as there are any; the numbers chosen don't matter until the last move. At $Y$'s final move, play an even coefficient if there is one, otherwise play the coefficient with the smaller exponent; it suffices to play a sufficiently large negative number.

This proof is inspired by Ross Millikan's post. Let us play as $Y$. We only play even coefficients as long as there are any left to play. Since the game starts out with $n-1$ even coefficients and $n$ odd coefficients, it follows that at $Y$'s final move, there will be at most one even coefficient left. If there is an even coefficient, then $Y$ will choose to play it, and we win by choosing a sufficiently large negative number, by the reasoning in Ross's last paragraph. Otherwise there remain two odd coefficients corresponding to $x^{d_1}$ and $x^{d_2}$ for some odd $d_1<d_2$. The polynomial is now of the form $$p(x)+ax^{d_1}+bx^{d_2}$$ for some polynomial $p(x)$. Choose a small $\epsilon>0$ ($\epsilon=1/2$ will suffice). Let $$\delta=\min(\frac12, \dfrac12 \dfrac{1-2\epsilon^{d_2-d_1}}{2\epsilon^{d_2}}),$$ and choose $N>0$ such that $|p(x)/N|\leq \delta$ for all $x\in[-1,1]$. Player $Y$ will now choose to play $a=-N/\epsilon^{d_1}$. Then $p(x)+ax^{d_1}<(-1+\delta)N<0$ at $x=\epsilon$ and thus $p(x)+ax^{d_1}$ has a real root. To compensate, $X$ must play as his final move some $b\geq (1-\delta)N/\epsilon^{d_2} \geq N/(2\epsilon^{d_2})$ in order to make $p(x)+ax^{d_1}+bx^{d_2}$ positive at $x=\epsilon$. But now, at $x=-1$ we get $$p(1)-a-b<(\delta+\dfrac1{\epsilon^{d_1}}-\dfrac1{2\epsilon^{d_2}}) N = (\delta-\dfrac{1-2\epsilon^{d_2-d_1}}{2\epsilon^{d_2}})N<-\delta N<0$$ and thus $p(x)+ax^{d_1}+bx^{d_2}$ has a real root. Player $Y$ wins!

Answer 2

$Y$ wins $n=2$. If $Y$ is allowed to pick the coefficient of $x^2$, he wins by choosing $-8$. The polynomial $x^4-8x^2+1$ is negative at both $\pm \frac 12$. As the polynomial $X$ chooses is odd, it can only bring one of these above $0$, so $X$ must open with the coefficient of $x^2$. He picks some positive value, presumably large, call it $a$. The polynomial so far is $x^4+ax^2+1$. $Y$ now adds in $-(20+\frac a{10})x$, which will make the value at $x=0.1$ to be $-0.9999$. Now $X$ has to add in at least $999.9x^3$, which makes the polynomial negative at $x=-1$

Added: for higher $n, Y$ wins if he plays the last even coefficient. The argument is the same as for $n=2$. If there is a root of the even part of the polynomial, there will be roots symmetric around zero. Then the odd part will increase one minimum and decrease the other, so there will still be at least two real roots.