Maths Olympiad Prep

Library / /10 of 10

Algebra Difficulty 7.2 National olympiad, round 2 Find the answer

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 n0n_0 and writes the polynomial P0(x)=n0P_0(x)=n_0.

2) On turn 1, Brenda choose a positive integer n1n_1, different from n0n_0, and either writes the polynomial

P1(x)=n1x+P0(x) or P1(x)=n1xP0(x)P_1(x)=n_1x+P_0(x) \textup{ or } P_1(x)=n_1x-P_0(x)

3) In general, on turn kk, the respective player chooses an integer nkn_k, different from n0,n1,,nk1n_0, n_1, \ldots, n_{k-1}, and either writes the polynomial

Pk(x)=nkxk+Pk1(x) or Pk(x)=nkxkPk1(x)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.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let us analyze the game played by Susana and Brenda, where they write polynomials on the board.

### Rules Recap
1. Initially, Susana selects a positive integer n0 n_0 and writes the polynomial P0(x)=n0 P_0(x) = n_0 .
2. On her first turn, Brenda must choose a positive integer n1n0 n_1 \neq n_0 and write either:
P1(x)=n1x+P0(x)orP1(x)=n1xP0(x). P_1(x) = n_1x + P_0(x) \quad \text{or} \quad P_1(x) = n_1x - P_0(x).
3. For turn k k , the player chooses a positive integer nkn0,n1,,nk1 n_k \neq n_0, n_1, \ldots, n_{k-1} and writes either:
Pk(x)=nkxk+Pk1(x)orPk(x)=nkxkPk1(x). P_k(x) = n_kx^k + P_{k-1}(x) \quad \text{or} \quad P_k(x) = n_kx^k - P_{k-1}(x).
4. The first player to write a polynomial with an integer root wins.

### Winning Strategy for Susana

1. Turn 0:
- Susana writes P0(x)=1 P_0(x) = 1 .

2. Turn 1:
- Brenda, not allowed to use n1=1 n_1 = 1 , writes either:
P1(x)=n1x+1orP1(x)=n1x1. P_1(x) = n_1x + 1 \quad \text{or} \quad P_1(x) = n_1x - 1.
- Neither of these polynomials have integer roots since for P1(x)=n1x+1 P_1(x) = n_1x + 1 or P1(x)=n1x1 P_1(x) = n_1x - 1 , solving for integer roots would require x=1n1 x = -\frac{1}{n_1} or x=1n1 x = \frac{1}{n_1} , both of which are not integers as n1±1 n_1 \neq \pm 1 .

3. Turn 2:
- Depending on Brenda's choice in Turn 1:
- If Brenda wrote P1(x)=n1x1 P_1(x) = n_1x - 1 , Susana writes:
P2(x)=(n1+1)x2+n1x1. P_2(x) = (n_1 + 1)x^2 + n_1x - 1.
Substituting x=1 x = -1 :
P2(1)=(n1+1)(1)2+n1(1)1=(n1+1)n11=0, P_2(-1) = (n_1 + 1)(-1)^2 + n_1(-1) - 1 = (n_1 + 1) - n_1 - 1 = 0,
Thus, 1-1 is a root, and Susana wins.
- If Brenda wrote P1(x)=n1x+1 P_1(x) = n_1x + 1 , Susana writes:
P2(x)=(n1+1)x2n1x1. P_2(x) = (n_1 + 1)x^2 - n_1x - 1.
Substituting x=1 x = 1 :
P2(1)=(n1+1)(1)2n1(1)1=(n1+1)n11=0, P_2(1) = (n_1 + 1)(1)^2 - n_1(1) - 1 = (n_1 + 1) - n_1 - 1 = 0,
Thus, 11 is a root, and Susana wins.

Based on this strategy, Susana ensures that no matter what polynomial Brenda writes on Turn 1, Susana can always write a polynomial on Turn 2 that has an integer root. Therefore, the solution allows Susana to win the game by setting up the situation in such a way that Brenda's choices do not affect the outcome by Turn 2.

The strategy can be concluded with the realization that Susana has a winning path by carefully managing her choices:

Susana wins by writing P2(x) that has +1 or 1 as a root. \boxed{\text{Susana wins by writing } P_2(x) \text{ that has } +1 \text{ or } -1 \text{ as a root.}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.