Santa asks Rudolph the Red-Nosed Reindeer and Frosty the Snowman to play a game. The winner can get an extra Christmas present, which is a cute Christmas frog! The rules of the game are as follows: Santa writes the following expression on the blackboard: $$x^{2024} +\_ \,\, x^{2023} + \_ \,\, x^{2022} + \_ \,\, x^{2021} + ... + \_ \,\, x^2 + \_ \,\, x +\_ \,\, $$Santa will first choose a positive integer $n \le 2024$. Rudolph will then choose $n$ consecutive blanks $(\_)$. Frosty will fill in the chosen blanks with real numbers. Finally Rudolph will fill in all the remaining blanks. If the resulting polynomial has $2024$ non-zero real roots, then Rudolph wins. Otherwise, Frosty wins. Find the value(s) of $n$ such that Rudolph has a winning strategy and the value(s) of $n$ such that Frosty has a winning strategy. What are their respective winning strategies?
Problem
Source: 2024 IGMO Christmas Edition #3 International Gamma Mathematical Olympiad
Tags: algebra, polynomial
03.02.2025 06:10
We claim that Rudolph wins when $n = 1$, and Frosty wins when $n \ge 2$. It suffices to show that Rudolph wins when $n = 1$ and Frosty wins when $n = 2$. Say that $n = 2$. Frosty chooses both coefficients to be $0$, say for $x^{2024-k},x^{2023-k}$. Suppose that Rudolph can get all roots to be real. We will prove by induction that if the $i$th and $i+1$th symmetric sums of $r_1,r_2,\dots,r_k$ are $0$ (for $0 \le i \le k$), then one of $r_1,r_2,\dots,r_k$ is $0$ or imaginary. The base case $k = 2$ is done, as we must have $x_1x_2 = 0$, so one of $x_1,x_2$ is $0$. Now, suppose that it holds for $k = \ell$, and we wish to prove for $k = \ell+1$. Let one root be $p$, and let $e_i$, $S_i$ be the $i$th symmetric sum and mean for the other $\ell$ roots. For some $i \ge 1$, we have $pe_{i-1} + e_i = 0$, and $pe_{i}+e_{i+1} = 0$. Suppose $e_{i-1} = 0$. Then, $e_i = 0$, a contradiction to our I.H. So, $e_{i-1} \neq 0$. Similarly, $e_{i} \neq 0$, and as $p \neq 0$, $e_{i+1} \neq 0$. This gives that $p = -\dfrac{e_{i+1}}{e_{i}} = -\dfrac{e_{i}}{e_{i-1}}$, or $e_i^2 = e_{i+1}e_{i-1}$. This is equivalent to $$S_{i+1}S_{i-1} = S_i^2 \cdot \dfrac{\binom{\ell}{i}^2}{\binom{\ell}{i-1}\binom{\ell}{i+1}} = S_i^2\dfrac{(\ell-i+1)(i+1)}{i(\ell-i)} > S_i^2.$$This is a contradiction with Newton's Inequality, so our induction is done, and so Frosty wins. Now, say $n = 1$. Rudolph forces Frosty to choose the coefficient of $x^{2023}$, say $-a$. We can have Frosty choose $\epsilon$ for $2023$ of the roots, and the last root as $a - 2023\epsilon$, which will work for large enough $\epsilon$. Then, Rudolph fills in the remaining numbers using Vieta's, and wins.