Let $n \geq 4$ be a natural number. The polynomials $x^{n+1} + x$, $x^n$, and $x^{n-3}$ are written on the board. In one move, you can choose two polynomials $f(x)$ and $g(x)$ (not necessarily distinct) and add the polynomials $f(x)g(x)$, $f(x) + g(x)$, and $f(x) - g(x)$ to the board. Find all $n$ such that after a finite number of operations, the polynomial $x$ can be written on the board.
Problem
Source: XII International Festival of Young Mathematicians Sozopol 2023, Theme for 10-12 grade
Tags: algebra
pco
24.09.2024 15:58
GeorgeRP wrote: Let $n \geq 4$ be a natural number. The polynomials $x^{n+1} + x$, $x^n$, and $x^{n-3}$ are written on the board. In one move, you can choose two polynomials $f(x)$ and $g(x)$ (not necessarily distinct) and add the polynomials $f(x)g(x)$, $f(x) + g(x)$, and $f(x) - g(x)$ to the board. Find all $n$ such that after a finite number of operations, the polynomial $x$ can be written on the board. 1) $x^{\alpha n+\beta(n-3)}$ can be written on the board, whatever are integers $\alpha,\beta\ge 1$
$x^n$ on the board implies $x^{\alpha n}$ may be written on the board whatever is integer $\alpha\ge 1$
$x^{n-3}$ on the board implies $x^{\beta(n-3)}$ may be written on the board whatever is integer $\beta\ge 1$
And so $x^{\alpha n+\beta(n-3)}$ can be written on the board, whatever are integers $\alpha,\beta\ge 1$
Q.E.D.
2) $x^{kn+1}-(-1)^kx$ can be written on the board whatever is integer $k\ge 1$
If $x^{kn+1}+x,x^{kn},x^{kn-3}$ are on the board for some $k\ge 1$, Then, multiplying by $x^n$ :
$x^{(k+1)n+1}+x^{n+1},x^{(k+1)n},x^{(k+1)n-3}$ are on the board and, subtracting $x^{n+1}+x$ from the first :
$x^{(k+1)n+1}-x,x^{(k+1)n},x^{(k+1)n-3}$ are on the board
If $x^{kn+1}-x,x^{kn},x^{kn-3}$ are on the board for some $k\ge 1$, Then, multiplying by $x^n$ :
$x^{(k+1)n+1}-x^{n+1},x^{(k+1)n},x^{(k+1)n-3}$ are on the board and, adding $x^{n+1}+x$ to the first :
$x^{(k+1)n+1}+x,x^{(k+1)n},x^{(k+1)n-3}$ are on the board
And so induction gives $x^{kn+1}-(-1)^kx,x^{kn},x^{kn-3}$ can be written on the board whatever is integer $k\ge 1$
Q.E.D.
3) If $n=3m+1$, $x$ can be written on the board
Using $\alpha=1$ and $\beta=m$, 1) implies $x^{3m^2+m+1}$ can be written on the board
Using $k=m$, 2) implies $x^{3m^2+m+1}-(-1)^mx$ can be written on the board
And so their difference $x$ can be written on the board
Q.E.D.
4) If $n=3m+2$, $x$ can be written on the board
Using $\alpha=1$ and $\beta=2m+1$, 1) implies $x^{6m^2+4m+1}$ can be written on the board
Using $k=2m$, 2) implies $x^{6m^2+4m+1}-x$ can be written on the board
And so their difference $x$ can be written on the board
Q.E.D.
5) If $n=3m$, $x$ can never be written on the board
Set $x=j$ ($e^{\frac{2i\pi}3}$) in each polynomial on the board
Since $j^3=1$, starting situation will be $2j,1,1$
Claim : numbers on the board will always be in the form $a+2bj$ where $a,b\in\mathbb Z$
This is true at starting situation for $1$ and for $2j$
And obviously, the set of numbers in the form $a+2bj$ is stable by addition, subtraction and multiplication (remember $j^2=-1-j$)
And since $j$ is not in this form, $x$ can not be written on the board
Q.E.D.
Hence the answer $\boxed{n\equiv 1,2\pmod 3}$