Susana and Brenda play a game writing polynomials on the board. Susana starts and they play taking turns. 1) On the preparatory turn (turn 0), Susana choose a positive integer $n_0$ and writes the polynomial $P_0(x)=n_0$. 2) On turn 1, Brenda choose a positive integer $n_1$, different from $n_0$, and either writes the polynomial $$P_1(x)=n_1x+P_0(x) \textup{ or } P_1(x)=n_1x-P_0(x)$$ 3) In general, on turn $k$, the respective player chooses an integer $n_k$, different from $n_0, n_1, \ldots, n_{k-1}$, and either writes the polynomial $$P_k(x)=n_kx^k+P_{k-1}(x) \textup{ or } P_k(x)=n_kx^k-P_{k-1}(x)$$ The first player to write a polynomial with at least one whole whole number root wins. Find and describe a winning strategy.
Problem
Source: OMCC 2017
Tags: OMCC, OMCC 2017, CENTRO, Game Theory, algebra, polynomial, combinatorics
duck_master
26.06.2017 04:58
On turn 0: Susana does not want Brenda to write $x-n_0$ and win, so she must pick 1. On turn 1: If Brenda writes $nx-1$, then Susana can writes $(n+1)x^2 +nx -1$ on turn 2 and wins. If Brenda writes $nx+1$, then Susana writes $(n+1)x^2 -nx-1$ on turn 2 and wins. So Brenda must write $2x-1$. Similarly, the game proceeds $3x^2-2x+1$, $5x^3-3x^2+2x-1$, $8x^4-5x^3+3x^2-2x+1$, $13x^5-8x^4+5x^3-3x^2+2x-1$. Each coefficient is especially picked so that the other player cannot write a polynomial with root 1(the only whole number root possible by the Rational Root Theorem), and so neither player has a winning strategy and the game lasts forever.
jestrada
28.06.2017 17:51
jg123 wrote:
On turn 0: Susana does not want Brenda to write $x-n_0$ and win, so she must pick 1. On turn 1: If Brenda writes $n_1x+1$, then Susana can write $(n_1+1)x^2 -n_1x -1$ on turn 2 and wins(...)
If Brenda writes $n_1x-1$, then Susana writes $(n_1-1)x^2-n_1x+1$ unless $n_1=2$, then Susana can't pick $n_2=1$. So $P_1(x)=2x-1$. Then Susana picks $P_2(x)=3x^2+2x-1$ and wins (root $x=-1$).
The Rational Root Theorem reduces the possible whole roots to 1 and -1.
Modesti
30.03.2021 23:52
Susana has a winning strategy. Let's describe it. $\bullet$ In turn 0, Susana writes 1. $\bullet$ In turn 1, suppose Brenda writes $nx\pm1$. As $n\ne 1$ (by rules of the game), this polynomial does not have an integer root. $\bullet$ In turn 2, if Brenda wrote $nx-1$, Susana writes $(n+1)x^2+nx-1$. As $-1$ is a root of this polynomial, Susana wins. Similarly, if Brenda wrote $nx+1$, Susana writes $(n+1)x^2-nx-1$. As $1$ is a root, she wins, too. Hence, Susana can always win in turn 2, so we are done. $\square$