We are given a real number $a$, not equal to $0$ or $1$. Sacho and Deni play the following game. First is Sasho and then Deni and so on (they take turns). On each turn, a player changes one of the “*” symbols in the equation: \[*x^4+*x^3+*x^2+*x^1+*=0\] with a number of the type $a^n$, where $n$ is a whole number. Sasho wins if at the end the equation has no real roots, Deni wins otherwise. Determine (in term of $a$) who has a winning strategy
Problem
Source: Bulgarian National Olympiad 2012 Problem 3
Tags: algebra, polynomial, algebra proposed
22.05.2012 00:52
Name the coefficients $c_4,c_3,...,c_0$ for reference. I split the problem into three cases: If $|a|>1$, Sacho can always win by forcing an even coefficient to be the last one chosen, and choosing it large enough to make the polynomial strictly positive or negative. If $-1<a<0$, Deni can always win as follows: If on the first turn Sacho chooses one of either $c_0$ or $c_4$, then Deni can choose the other one to have opposite sign, thereby guaranteeing a root. Therefore Sacho will not choose $c_0$ or $c_4$, so he must choose one of $c_1,c_2,c_3$. But then Deni can choose one of $c_3$ or $c_2$ -- thus Deni can always force Sacho to choose $c_1$. But then Deni can choose $c_0$ to be small enough so that $c_1x+c_0$ has a root in such a small neighborhood of $0$ that the other terms are negligible. If $0<a<1$, Sacho can always win as follows: On the first move, Sacho chooses $c_4=a$. If Deni then chooses $c_1, c_2$, or $c_3$, Sacho will choose $c_0=a$, and regardless of the other choices the resulting polynomial will be strictly greater than $a(x^4+x^3+x+1)\geq 0$ for all $x<0$, so Sacho wins. If Deni instead chose $c_0$, then Sacho will choose $c_1$ so small such that $c_1x+c_0>0$ on $[-2,0]$, and then regardless of the other choices the resulting polynomial will be greater than $a(x^4+x^3+x^2)>0$ for all $x<0$, so Sacho wins.
25.05.2012 09:19
Well, I don't have a solution, but I know that the answer is that Sasho wins if a>0 or a = -1 and Deni wins otherwise. Besides are you sure about this "If |a|>1, Sacho can always win by forcing an even coefficient to be the last one chosen, and choosing it large enough to make the polynomial strictly positive or negative". I'm not sure it's OK for a<-1
27.05.2012 23:32
checkd: If $a<-1$ is neg. $a^2 x^4 + ... +a$ has roots. $f(0)<0$ and $f(\infty)>0$ limit, contradiction to your sol. joeblow. This part we have to change. Also if $a=-1$ we have to show, Sasho just makes $c_0=c_4$ and that $c_1,c_2,c_3$ aren't equal. We just have $3$ trivial AM-GMcases that are the other case when $x$ is negative. If $a>1$ it is trivial that yours work by AM-GM.
04.06.2012 17:48
Shacho always win I think when /a/>1, we can choose as joeblow. We choose the first is positive and last we choose a^n with n even and large enough. If /a/<1, why don't we choose all the confient is 1, beacause n is a whole number, n can be 0.
04.06.2012 18:31
No, the above posters are right, my solution doesn't work for the case $a<-1$. No matter how large you choose an even-power coefficient to be, you cannot extinguish a root in a neghborhood of $0$; it will always exist if the sign of the constant coefficient is of opposite sign.
05.01.2023 18:22
so anyone has a complete solution? i really didn't understand none of the posts above.
27.12.2023 22:04
for a<0 Deni always win, he waits to Sacho put one of leading or constant coefficients then he put other one something with different sign. now P(0) and P(+infinity) has different signs sow by Intermediate value theorem P has a real root.
31.12.2023 11:08
Suppose $c_0 , c_1 , c_2 , c_3$ and $ c_4$ are coefficients of $x^0 , x^1 , x^2 , x^3$ and $x^4$ and $P(x) = c_4x^4 + \cdots + c_0$. There are three cases : $a > 1 , 1 > a > 0 , 0 > a$ (I) $a<0$ : In this case Deni always wins , he waits to Sacho put one of leading or constant coefficients then he put other one something with different sign. now $P(0)$ and $P(+\infty)$ have different signs sow by Intermediate value theorem $P$ has a real root. (II) $a>1$ : Sacho wins this case , in his first turn he put $c_3 = a^0 = 1$ , then if Deni don't put $c_1$ he puts $c_1 = 1$ and it's easy to check with $c_1=c_3=1$ and $c_0 , c_2 , c_4 \geq 1$ Sacho wins, so Deni should put $c_1 = a^X$ , then Sacho put $c_0 = a^N$ where $N>2X+1$. now suppose by contradiction that $P$ has a real root such $\alpha$. first note that $\alpha$ should be negative because all coefficients are positive. there are three subcases : (a) if $|\alpha| < 1$ then $|c_2\alpha^2| > |c_3\alpha^3| = |\alpha^3|$ and $|c_0| > |c_1\alpha|$ so $P(\alpha) > 0$ (b) if $ 1 < |\alpha| \leq a^X $ then $|c_4\alpha^4| > |c_3\alpha^3|=|\alpha^3|$ and $|c_0| = |a^N| > |a^{2X}| \geq |a^X\alpha| = |c_1\alpha|$ so again $P(\alpha)>0$ (c) and if $|\alpha| > a^X$ then $|c_4\alpha^4| > |c_3\alpha^3|=|\alpha^3|$ and $|c_2\alpha^2| \geq |\alpha^2| > |a^X\alpha| = |c_1x|$ so $P(\alpha) > 0$ we conclude $P$ has not real root. (III) $0<a<1$ : Sacho wins this case too, in his turn he put $c_2=1$ , if Deni put $c_1$ Sacho put $c_0=1$ and if Deni put $c_0$ Sacho put $c_1$ something smaller than $c_0$ and Sacho do same thing for $c_3$ and $c_4$ , then $|c_2|,|c_0| \geq |c_1|$ and $|c_4|,|c_2| \geq |c_3|$ now by a same argument like case II we have $P(x)$ is always positive so it has not real root and we are done.
17.09.2024 17:32
A rather tricky problem, despite having easy parts, as to be expected from this author. We show that $A$ wins for $a>0$ and $a=-1$ and $B$ wins otherwise. Suppose the equation is $f(x) = a_4x^4 + a_3x^3 + a_2x^2 + a_1x + a_0 = 0$. Consider firstly $a=-1$. Let $A$ firstly fill in $a_2$. Then when $B$ fills in $a_1$ or $a_3$, $A$ fills in the other one with opposite sign; and when $B$ fills in $a_0$ or $a_4$, $A$ fills in the other one with the same sign. By replacing $x$ with $\frac{1}{x}$ or multiplying by $-1$, if necessary, we may assume that the resulting equation is $x^4 + x^3 \pm x^2 - x + 1 = 0$. This has no solution, as $x^4 + x^3 - x^2 - x + 1 = (x^2+x-1)^2 + (x^2-1)^2 + x^2 > 0$ and $x^4 + x^3 + x^2 - x + 1 = (x^4 + x^3 - x^2 - x + 1) + 2x^2 > 0$. (Alternatively, $x^4 + x^3 \pm x^2 - x + 1 = 0$ is equivalent to $x^2 + \frac{1}{x^2} + x - \frac{1}{x} \pm 1 = 0$, so with $t = x - \frac{1}{x}$ we have $t^2 + t + 1 = 0$ or $t^2 + t + 3 = 0$, neither of which have a real root.) Now suppose $a>0$. Let $A$ begin by filling in $a_1$ arbitrarily. On their next move they fill in $a_3$ arbitrarily if it is not filled in already, otherwise they fill in another coefficient. Suppose the last unfilled coefficient is $a_0$ or $a_4$ -- by replacing $x$ with $\frac{1}{x}$, if necessary, we may assume it is $a_0$. Then $A$ fills it in with a sufficiently large power of $a$ (postiive if $a>1$, negative if $0<a<1$) in order to ensure $f(x) > 0$ and hence win. Suppose the last unfilled coefficient is $a_2$. Then it is again possible for $A$ to fill it in with a sufficiently large power of $a$ and win. Indeed, $g(x) = a_4x^2 + a_3x + \frac{a_1}{x} + \frac{a_0}{x^2}$ satisfies $\lim_{x\to\pm \infty} g(x) = \lim_{x\to0} g(x) = \infty$, hence has a minimum. (Alternatively, picking $a_2 > \frac{1}{4}\left(\frac{a_3^2}{a_4}+\frac{a_1^2}{a_0}\right)$ suffices, since then $a_4x^4 + a_3x^3 + a_2x^2 + a_1x + a_0 > \frac{x^2}{a_4}\left(a_4x + \frac{a_3}{2}\right)^2 + \frac{1}{a_0}\left(\frac{a_1}{2}x + a_0\right)^2 \geq 0$.) Finally, the hardest case - suppose $a<0$, $a\neq -1$. By replacing $x$ with $\frac{1}{x}$, if necessary, we may assume that $A$ has initially filled in $a_0$, $a_1$ or $a_2$. If this is $a_0$, then $B$ fills in $a_4$ with a sufficiently large power of $a\neq -1$ of opposite sign (and wins, as there exists a root by the Intermediate value theorem). If this is not $a_0$, then $B$ fills in $a_4$ with a positive number. Now $A$ has to fill in $a_0$ with a positive number (otherwise, $B$ fills it in negatively with a sufficiently large power of $a\neq -1$ and $A$ loses by the Intermediate value theorem). Now consider the final move of $A$. - If $a_2$ is filled in already, let $A$ fill in $a_3$, so that $p_1(x) = a_4x^3 + a_3x^2 + a_2x + \frac{a_0}{x}$ satisfies $p_1(1) < p_1(-2)$. Note that $\lim_{x\to \pm \infty} p_1(x) = \lim_{x\to \pm 0} p_1(x) = \pm \infty$ and the previous inequality assures that the minimum for $x>0$ is smaller than the maximum for $x<0$. In particular, by the Intermediate Value theorem $p_1$ attains every possible value, thus $p_1(x) = -a_1$ has a solution and $A$ wins. - If $a_1$ is filled in already, let $A$ fill in $a_2$, so that $\displaystyle p_2(x) = a_4x + \frac{a_2}{x} + \frac{a_1}{x^2} + \frac{a_0}{x^3}$ satisfies $p_2(1) < p_2(-2)$. Note that $\lim_{x\to \pm \infty} p_2(x) = \lim_{x\to \pm 0} p_2(x) = \pm \infty$ and the previous inequality assures that the minimum for $x>0$ is smaller than the maximum for $x<0$. In particular, by the Intermediate value theorem $p_2$ attains every possible value, thus $p_2(x) = -a_3$ has a solution and $A$ wins.
17.09.2024 18:15
MrezaAttaran wrote: (I) $a<0$ : In this case Deni always wins , he waits to Sacho put one of leading or constant coefficients then he put other one something with different sign. now $P(0)$ and $P(+\infty)$ have different signs sow by Intermediate value theorem $P$ has a real root. This is not always possible, as Sacho's first two moves might involve only coefficients among $a_1$, $a_2$, $a_3$ and thus Deni will be forced to firstly put a value for $a_0$ or $a_4$.
19.11.2024 17:49
Assassino9931 wrote: MrezaAttaran wrote: (I) $a<0$ : In this case Deni always wins , he waits to Sacho put one of leading or constant coefficients then he put other one something with different sign. now $P(0)$ and $P(+\infty)$ have different signs sow by Intermediate value theorem $P$ has a real root. This is not always possible, as Sacho's first two moves might involve only coefficients among $a_1$, $a_2$, $a_3$ and thus Deni will be forced to firstly put a value for $a_0$ or $a_4$. Oops! Yes you are right