In a game, Andi and a computer take turns. At the beginning, the computer shows a polynomial $x^2 + mx + n$ where $m,n \in \mathbb{Z}$, such that it doesn't have real roots. Andi then begins the game. On his turn, Andi may change a polynomial in the form $x^2 + ax + b$ into either $x^2 + (a+b)x + b$ or $x^2 + ax + (a+b)$. However, Andi may only choose a polynomial that has real roots. On the computer's turn, it simply switches the coefficient of $x$ and the constant of the polynomial. Andi loses if he can't continue to play. Find all $(m,n)$ such that Andi always loses (in finitely many turns).
Problem
Source: Indonesian National Science Olympiad 2018, Mathematics P4
Tags: algebra
BlazingMuddy
23.06.2019 01:02
This has not been answered yet? Hmm...
The answers are:
1. $(3, 0)$, $(2, 0)$, $(1, 0)$,
2. $(0, n)$ where $1\leq n\leq 3$,
3. $(-1, n)$ where $2\leq n\leq 5$,
4. $(-2, n)$ where $4\leq n\leq 7$,
5. $(-3, n)$ where $6\leq n\leq 8$,
6. $(-4, n)$ where $9\leq n\leq 10$.
If Andi does not lose in the first turn and $n\neq 0$, then Andi can continue the game indefinitely and avoid loss.
Notice that a polynomial $x^2 + ax + b$ has a real root if and only if $a^2 \geq 4b$.
First, observe that if the computer ever throws in a polynomial $x^2 + ax + b$ where $a + b \leq 0$, then at least one of $a$ and $b$ is non-positive. If $a \leq 0$, Andi chooses $x^2 + ax + (a + b)$. Otherwise, $b\leq 0$, and Andi chooses $x^2 + (a+b)x + b$. Either way, the resulting polynomial has both it's constant and $x$ coefficients non-positive (and thus has real roots). In each subsequent turns the computer can only throw a polynomiaal with this property, so Andi would not lose. Let it be position $1$.
Second, if the computer ever throws in a polynomial $x^2 + ax + b$ where $a, b > 0$, then Andi can pick $x^2 + (a + b)x + b$. Note that $(a + b)^2 \geq (b + 1)^2 \geq 4b$, so it has real roots. Then, in every subsequent turns, the computer would only be able to throw polynomials $x^2 + ax + b$ where $a, b > 0$, and Andi can just repeat the strategy and avoid loss. Let this be position $2$.
Third, if if the computer ever throws in a polynomial $x^2 + ax + b$ where $b < 0$ and $a + b > 0$, then by picking $x^2 + ax + (a + b)$ as $a > a + b > 0$, reaching the position $2$ after the computer changes it to $x^2 + (a + b)x + a$. Let it be position $3$.
Hence, for the remaining case, since $n\neq 0$, we assume that $m + n > 0$ but $m < 0$. Obviously, if Andi can choose $x^2 + (m + n)x + n$, since $n > n + m > 0$, then he had reached position $2$. Meanwhile, if Andi can choose $x^2 + mx + (m + n)$, then the computer throws in $x^2 + (m + n)x + m$ where $m + n > 0 > m$, thus either reaching position $3$ if $2m + n = (m + n) + m > 0$, or reaching position $1$ otherwise, if $2m + n = (m + n) + m \leq 0$. Either way, Andi would not lose.
Hence, the claim holds.
The claim means that in the case $n\neq 0$, Andi loses if and only if he loses on the first turn; i.e. if and only if both $(m + n)^2 < 4n$ and $m^2 < 4(m + n)$ holds. Note that this means $m \leq 0 < n$ and $m + n > 0$. The first one is then equivalent to $m + n < 2\sqrt{n}$ and then $(\sqrt{n} - 1)^2 < 1 + (-m)$. Meanwhile, the second one is simply equivalent to $n > (-m) + \left( \frac{-m}{2}\right)^2$. As a result,
$$ (-m) + \left( \frac{-m}{2}\right)^2 < n < (1 + \sqrt{1 + (-m)})^2 = 2 + (-m) + 2\sqrt{1 + (-m)}$$
But it can easily be checked that if $-m \geq 6$, then $ \left( \frac{-m}{2}\right)^2 \geq 2 + 2\sqrt{1 + (-m)} $. So, $0 \leq (-m) \leq 5$. Then, the results can be found by manual checking.
The rest of the case is $n = 0$, for which if $m\leq 0$ then Andi wins as both coefficients will never be positive (except the obvious $x^2$ coefficient), and if $m\geq 4$ then Andi can pick $x^2 + mx + m$ and avoid loss, while he loses if $1\leq m\leq 3$ as he is forced to go with $x^2 + mx$, then the computer returns $x^2 + m$, for which he cannot move.
mivinca789
12.07.2024 11:38
BlazingMuddy wrote: This has not been answered yet? Hmm...
The answers are:
1. $(3, 0)$, $(2, 0)$, $(1, 0)$,
2. $(0, n)$ where $1\leq n\leq 3$,
3. $(-1, n)$ where $2\leq n\leq 5$,
4. $(-2, n)$ where $4\leq n\leq 7$,
5. $(-3, n)$ where $6\leq n\leq 8$,
6. $(-4, n)$ where $9\leq n\leq 10$.
If Andi does not lose in the first turn and $n\neq 0$, then Andi can continue the game indefinitely and avoid loss.
Notice that a polynomial $x^2 + ax + b$ has a real root if and only if $a^2 \geq 4b$.
First, observe that if the computer ever throws in a polynomial $x^2 + ax + b$ where $a + b \leq 0$, then at least one of $a$ and $b$ is non-positive. If $a \leq 0$, Andi chooses $x^2 + ax + (a + b)$. Otherwise, $b\leq 0$, and Andi chooses $x^2 + (a+b)x + b$. Either way, the resulting polynomial has both it's constant and $x$ coefficients non-positive (and thus has real roots). In each subsequent turns the computer can only throw a polynomiaal with this property, so Andi would not lose. Let it be position $1$.
Second, if the computer ever throws in a polynomial $x^2 + ax + b$ where $a, b > 0$, then Andi can pick $x^2 + (a + b)x + b$. Note that $(a + b)^2 \geq (b + 1)^2 \geq 4b$, so it has real roots. Then, in every subsequent turns, the computer would only be able to throw polynomials $x^2 + ax + b$ where $a, b > 0$, and Andi can just repeat the strategy and avoid loss. Let this be position $2$.
Third, if if the computer ever throws in a polynomial $x^2 + ax + b$ where $b < 0$ and $a + b > 0$, then by picking $x^2 + ax + (a + b)$ as $a > a + b > 0$, reaching the position $2$ after the computer changes it to $x^2 + (a + b)x + a$. Let it be position $3$.
Hence, for the remaining case, since $n\neq 0$, we assume that $m + n > 0$ but $m < 0$. Obviously, if Andi can choose $x^2 + (m + n)x + n$, since $n > n + m > 0$, then he had reached position $2$. Meanwhile, if Andi can choose $x^2 + mx + (m + n)$, then the computer throws in $x^2 + (m + n)x + m$ where $m + n > 0 > m$, thus either reaching position $3$ if $2m + n = (m + n) + m > 0$, or reaching position $1$ otherwise, if $2m + n = (m + n) + m \leq 0$. Either way, Andi would not lose.
Hence, the claim holds.
The claim means that in the case $n\neq 0$, Andi loses if and only if he loses on the first turn; i.e. if and only if both $(m + n)^2 < 4n$ and $m^2 < 4(m + n)$ holds. Note that this means $m \leq 0 < n$ and $m + n > 0$. The first one is then equivalent to $m + n < 2\sqrt{n}$ and then $(\sqrt{n} - 1)^2 < 1 + (-m)$. Meanwhile, the second one is simply equivalent to $n > (-m) + \left( \frac{-m}{2}\right)^2$. As a result,
$$ (-m) + \left( \frac{-m}{2}\right)^2 < n < (1 + \sqrt{1 + (-m)})^2 = 2 + (-m) + 2\sqrt{1 + (-m)}$$
But it can easily be checked that if $-m \geq 6$, then $ \left( \frac{-m}{2}\right)^2 \geq 2 + 2\sqrt{1 + (-m)} $. So, $0 \leq (-m) \leq 5$. Then, the results can be found by manual checking.
The rest of the case is $n = 0$, for which if $m\leq 0$ then Andi wins as both coefficients will never be positive (except the obvious $x^2$ coefficient), and if $m\geq 4$ then Andi can pick $x^2 + mx + m$ and avoid loss, while he loses if $1\leq m\leq 3$ as he is forced to go with $x^2 + mx$, then the computer returns $x^2 + m$, for which he cannot move.
But if (m,n)= (3,0),(2,0),(1,0) , then the polynomial x^2+mx+n will have real roots, meanwhile the question said that the polynomial doesn't have real roots. Hmm