Let $F$ be the set of all polynomials $\Gamma$ such that all the coefficients of $\Gamma (x)$ are integers and $\Gamma (x) = 1$ has integer roots. Given a positive intger $k$, find the smallest integer $m(k) > 1$ such that there exist $\Gamma \in F$ for which $\Gamma (x) = m(k)$ has exactly $k$ distinct integer roots.
Problem
Source: China TST 2000, problem 4
Tags: function, algebra, polynomial, algebra unsolved
23.05.2010 05:20
Since $\Gamma (x)=m$ has $k$ distinct integer roots,we have $\Gamma (x)= (x-x_1)(x-x_2)....(x-x_k)Q(x)+m$ for distinct integers $x_1,x_2,...,x_k$ and $Q \in Z[X]$ Let $t$ be a solution of $\Gamma (x)=1$.Then $(t-x_1)(t-x_2)...(t-x_k)Q(x)=1-m$ => $|1-m|=|t-x_1||t-x_2||t-x_3|....|t-x_k||Q(x)|$ => $|1-m| \geq 1.2.3...k.1$ => $m-1 \geq k!$ =>$m \geq k!+1$ Thus,the minimum value of $m$ is $k!+1$. The equality occurs when $\Gamma (x) = (x-1)(x-2)...(x-k+1)(x+k) + k!+1$ .
14.10.2014 22:11
the moduli $|t-x_i|$ need not be distinct. for example to prove $m(3)=3$ consider the polynomial $X^3+2X^2-X+1$
26.08.2019 04:15
Indeed, the answer is $1 + \left( \left \lfloor \frac{k}{2} \right \rfloor \right)! \left( \left \lceil \frac{k}{2} \right \rceil \right)!$. To show that this is optimal do the same proof as KDS did above, with the minor fix that at most two of the $|t-x_i|$'s can be equal to each other. To construct this, consider the polynomial $\Gamma(x) = 1 + \left( \left \lfloor \frac{k}{2} \right \rfloor \right)! \left( \left \lceil \frac{k}{2} \right \rceil \right)! + (-1)^{\left \lfloor \frac{k+2}{2} \right \rfloor}(x-1)(x-2) \cdots \left (x- \left \lfloor \frac{k}{2} \right \rfloor \right) (x+1) (x+2) \cdots \left( x + \left \lceil \frac{k}{2} \right \rceil \right).$ Then $\Gamma(x) = 1$ has the root $x = 0$, and $\Gamma(x) = 1 + \left( \left \lfloor \frac{k}{2} \right \rfloor \right)! \left( \left \lceil \frac{k}{2} \right \rceil \right)!$ has exactly $k$ distinct integer roots. $\square$