Egor and Igor take turns (Igor starts) replacing the coefficients of the polynomial \[a_{99}x^{99} + \cdots + a_1x + a_0\]with non-zero integers. Egor wants the polynomial to have as many different integer roots as possible. What is the largest number of roots he can always achieve?
Problem
Source: 239-School Open Olympiad 2022, Junior League P1
Tags: algebra, game, polynomial
starchan
19.05.2023 09:25
Solved with mueller.25
The answer is $2$. First of all, observe that Igor can ensure that the final polynomial has at most $2$ distinct integer roots, by simply setting $a_0 = 1$ in the first move. Now the final roots can only divide $1$, so either $-1$ or $1$. On the other hand, Egor can always ensure $x^2-1$ divides the final polynomial. He achieves this by dividing the coefficients into pairs by pairing $(a_{4k}, a_{4k+2});(a_{4k+1}, a_{4k+3})$ for all $0 \leq k \leq 24$. Now each time Igor sets a coefficient of some pair to a value, say $v$, Egor responds by setting the value of the other coefficient to $-v$. This ensures that the final polynomial is divisible by $x^2-1$ and hence has at least $2$ distinct roots, $\pm 1$ so we are done.
Nuterrow
03.01.2025 12:28
The largest number of roots that can be achieved is $2$. For the bound, notice that if Egor chooses $a_0$ to be 1, the only possible distinct roots would be $1$ and $-1$. To ensure this, whenever Egor replaces a coefficient $a_i$ with $c$, Igor just replaces a coefficient $a_j$ with $-c$ such that $i$ and $j$ have same parity and this clearly ensures that $1$ and $-1$ are roots since there are an even number of coefficients with odd and even indices. $\blacksquare$