Polynomial Playoff (9/23 – 10/6)
Alice and Bob are playing a game where they select the coefficients of the polynomial
$$P(x) = x^{2n} + a_{2n-1}x^{2n-1} + \dots + a_1x^1 + a_0x^0 \quad (n \in \mathbb{Z}^+)$$
one by one from \(a_0\) to \(a_{2n-1}\) starting from Alice.
Alice wins the game if \(P(x)\) has no real roots and Bob wins otherwise.
The restrictions for picking the coefficients is that \(|a_i| \leq \alpha\) for all \(0 \leq i < 2n\). (\(\alpha > 0\))
For which values of \(\alpha\) does Alice have a winning strategy regardless of the value of \(n\)?
Solution
Note that \(P(x)\) has a real root if the minimum of \(P(x)\) is less than or equal to 0. Therefore, we can see that Alice will always choose \(a_i = \alpha\) to maximize \(P(x)\) and Bob will choose his coefficients that make the minimum as small as possible. To achieve that, Bob needs all the coefficients to be the same sign and as large as possible. So he will either pick all of \(a_i=\alpha\) or \(a_i = -\alpha\). WLOG, suppose he picks \(a_i = -\alpha\).
Then, the polynomial with optimal play will be
$$P(x) = x^{2n} -\alpha x^{2n-1} + \alpha x^{2n-2} \dots -\alpha x+\alpha= (1-\alpha)x^{2n} + \alpha \frac{x^{2n + 1}+1}{x+1}$$
Since \(P(x)\) has a solution if and only if \(P(1/x)\) does, \(P(x)\) not having a solution is the same as
$$(1-\alpha) + \alpha \frac{x^{2n + 1}+1}{x+1}$$ not having a solution since \(P(0) \neq 0\) which is the same as
$$\min \frac{x^{2n+1} + 1}{x+1} > \frac{\alpha – 1}{\alpha}$$
Therefore, we are interested in the function
$$P_n(x) = \frac{x^{2n+1} + 1}{x+1}$$
It is clear that the minimum of \(P_n(x)\) occurs where \(x \in [0, 1]\) since \(P(0)=P(1)=1, P(x)>1\) when \(x < 0, x > 1\).
We also that the minimum of \(P_n(x)\) is decreasing as \(n\) increases since \(P_n(x)\) where \(x \in [0, 1] \) decreases as \(n\) increases.
Now, we claim that the minimum of \(P_n(x)\) converges to \(\frac{1}{2}\).
First, the minimum is bounded below by \(\frac{1}{2}\) since \(P_n(x) \geq \frac{1}{x+1} \geq \frac{1}{2}\) for \(x \in [0, 1]\).
Now, let \(L > \frac{1}{2}\). Letting \(x = 1 – \epsilon\) gives \(P_n(x) = \frac{(1-\epsilon)^{2n+1} + 1}{2-\epsilon}\). We select \(\epsilon\) such that \(\frac{1}{2} < \frac{1}{2-\epsilon} < L\). Then, $$\lim_{n \to \infty} \frac{(1-\epsilon)^{2n+1} + 1}{2 - \epsilon} = \frac{1}{2 - \epsilon} < L$$ Thus, the minimum of \(P_n(x)\) approaches \(\frac{1}{2}\). Solving for $$\frac{\alpha - 1}{\alpha} \leq \frac{1}{2}$$ tells us that Alice wins if \(\alpha \leq 2\).