Let $n \ge 2$ be an integer and $f_1(x), f_2(x), \ldots, f_{n}(x)$ a sequence of polynomials with integer coefficients. One is allowed to make moves $M_1, M_2, \ldots $ as follows: in the $k$-th move $M_k$ one chooses an element $f(x)$ of the sequence with degree of $f$ at least $2$ and replaces it with $(f(x) - f(k))/(x-k)$. The process stops when all the elements of the sequence are of degree $1$. If $f_1(x) = f_2(x) = \cdots = f_n(x) = x^n + 1$, determine whether or not it is possible to make appropriate moves such that the process stops with a sequence of $n$ identical polynomials of degree 1.
Problem
Source: Indian IMOTC 2013, Team Selection Test 4, Problem 2
Tags: algebra, polynomial, algebra proposed
23.03.2014 16:48
We show that it is possible for all odd $n$. I shall call the co-efficient of the term of exponent $d-1$ of a polynomial of degree $d$ to be its vice-leading coefficient. (I couldn't find a better name ) Lemma: Suppose that $f(x)$ is a monic polynomial. Then, the move $M_k$ increases the vice-leading coefficient by $k$. Proof of Lemma: Let $f(x) = \sum_{i=0}^n a_ix^i$, where $a_n=1$. Therefore, \[ \frac{f(x)-f(k)}{x-k} = x^{n-1}+(k+a_{n-1})x^{n-2} + \cdots \] Obviously, all omitted terms have lower degree. Using this lemma, the vice-leading coefficient acts as a semi-invariant. Clearly, each move reduces the respective polynomial into another monic polynomial with degree exactly $1$ less than its predecessor. So, to reduce each of the polynomials into linear ones, a total of $n(n-1)$ moves are required. Furthermore, the moves must be made in such a way, that the final polynomials have their vice-leading coefficients all equal. Consequently the sum of the indexes of the moves made on $f_i(x)$ should be equal for all $i \in [1,n]$. From here, we infer that $1+2+ %Error. "costs" is a bad command. +n(n-1)=n(n-1)(n^2-n+1)/2$ should be divisible by $n$. Therefore $n$ is odd. Now, we show a construction of the move sequence for odd $n$. We apply the moves $M_{2kn+i}, M_{2(k+1)n+1-i}$ on the polynomial $f_i(x)$ for all $k$ from $0$ to $(n-3)/2$. Clearly, all moves are covered in this construction exactly once. Moreover, after each pair of moves has been applied on all of the polynomials, the vice-leading coefficients found to be all equal. Therefore, even after completion of all the moves, the vice-leading co-efficients i.e. the constant term of the linear polynomials must be all equal.