Ali and Naqi are playing a game. At first, they have Polynomial $P(x) = 1+x^{1398}$. Naqi starts. In each turn one can choice natural number $k \in [0,1398]$ in his trun, and add $x^k$ to the polynomial. For example after 2 moves $P$ can be : $P(x) = x^{1398} + x^{300} + x^{100} +1$. If after Ali's turn, there exist $t \in R$ such that $P(t)<0$ then Ali loses the game. Prove that Ali can play forever somehow he never loses the game!
Problem
Source: Iran MO 2019 , secound round , day 2 , p5
Tags: combinatorics, Game Theory, algebra
03.05.2019 12:15
One even can prove the result with starting polynomial $x^{2018}$ or $1$.
03.05.2019 12:44
Here is my solution with starting polynomial $x^{2018}$:Whenever Naqi writes $x^{2k}$ Ali will write $x^{2k}$ again.When Naqi writes $x^{2k+1}$ Ali writes $x^{2k}$ when the coefficient of $x^{2k+1}$ becomes odd and writes $x^{2k}$ otherwise. To see why this works just note that since $x^{2k}+x^{2k+2} \ge 2x^{2k+1} ,x^{2k} \ge 0$ we may assume that Naqi didn't choose any even power or any odd power more than once.Now if $x$ is non-negative everything is clear.If $0>x \ge -1$ pair each odd powe with some even degree less than it.Each pairing has a positive sum so the total is non-negative.If $x<-1$ pair odd power with some even power more than it and again each pairing has non-negative sum so the total sum is nonnegative the reverse argument shows the proof for starting polynomial $1$.
05.05.2019 15:58
07.05.2019 10:22
Bad format, might fix later!
16.04.2022 11:13
we'll propose a strategy which Ali won't ever lose and prove that the strategy works. Strategy $:$ If Naqi adds $x^{2n}$ then Ali will add $x^{2n}$ as well. If Naqi adds $x^{2n+1}$ and after adding it's coefficient is odd then Ali will add $x^{2n}$ and If it's coefficient is even then Ali will add $x^{2n+2}$. Note that by AM-GM we have $x^{2n} + x^{2n+2} \ge |2x^{2n+1}|$ so we can simplify our polynomial after each 2 moves such that coefficient of every $x$ with odd power is $1$ or $0$. Case $1 : x \le 0$. obviously in this case $P(x) > 0$ cause all are nonnegative. Case $2 : -1 \le x < 0$. Note that for every $k$ if $x^{2k+1}$ has coefficient $1$ then by our strategy definition there exists at least one $x^{2k}$ and note that since $-1 \le x < 0$ then $x^{2n} \ge |x^{2n+1}|$ so again our polynomial is nonnegative. Case $3 : x < -1$. Like last part we'll pair $x^{2n},x^{2n+1}$ together and sort our pairs from least odd degree to most. Now we define our new pairs like this $:$ For every $2$ consecutive pairs $(x^{2n},x^{2n+1})$ and $(x^{2n'},x^{2n'+1})$ we put $x^{2n+1},x^{2n'}$ in a new pair. Note that in every new pair like $x^{2s+1},x^{2s'}$ we have $x^{2s'} > |x^{2s+1}|$ and also note that now $x^{2t+1}$ with greatest odd power isn't in any pair so Take $x^{1398}$ from our main polynomial and make $x^{2t+1},x^{1398}$ a pair and clearly $1398 > 2t+1$ so again our polynomial is nonnegative. so we have proves that our strategy works so Ali can play play forever somehow he never loses the game.