IMO 2016 Shortlisted Problems

Let $P(x)=a_d{x}^d+a_{d-1}{x}^{d-1}+\cdots +a_0$. Consider the substitution $y=d{a}_{d}x+a_{d-1}$. By defining $Q(y)=P(x)$, we find that $Q$ is a polynomial with rational coefficients without the term $y^{d-1}$. Let $Q(y)=b_d{y}^d+b_{d-2}{y}^{d-2}+b_{d-3}{y}^{d-3}+\cdots +b_0$ and $B={\max }_{0⩽i⩽d}\left\{\left|b_i\right|\right\}$ (where $b_{d-1}=0$ ). The condition shows that for each $n⩾1$, there exist integers $y_1,y_2,\dots ,y_n$ such that $\frac{1}{2}<\frac{Q\left(y_i\right)}{Q\left(y_j\right)}<2$ and $\frac{Q\left(y_i\right)}{Q\left(y_j\right)}$ is the $d$-th power of a rational number for $1⩽i,j⩽n$. Since $n$ can be arbitrarily large, we may assume all $x_i$'s and hence $y_i$'s are integers larger than some absolute constant in the following. By Dirichlet's Theorem, since $d$ is odd, we can find a sufficiently large prime $p$ such that $p\equiv 2(\mathrm{mod}d)$. In particular, we have $(p-1,d)=1$. For this fixed $p$, we choose $n$ to be sufficiently large. Then by the Pigeonhole Principle, there must be $d+1$ of $y_1,y_2,\dots ,y_n$ which are congruent $\mathrm{mod}p$. Without loss of generality, assume $y_i\equiv y_j(\mathrm{mod}p)$ for $1⩽i,j⩽d+1$. We shall establish the following. - Claim. $\frac{Q\left(y_i\right)}{Q\left(y_1\right)}=\frac{y_i^d}{y_1^d}$ for $2⩽i⩽d+1$. Proof. Let $\frac{Q\left(y_i\right)}{Q\left(y_1\right)}=\frac{l^d}{m^d}$ where $(l,m)=1$ and $l,m>0$. This can be rewritten in the expanded form $$\begin{array}{c}{b}_d\left(m^d{y}_i^d-l^d{y}_1^d\right)=-\sum _{j=0}^{d-2}{b}_j\left(m^d{y}_i^j-l^d{y}_1^j\right)\end{array}\text{\hspace{1em}(1)}$$ Let $c$ be the common denominator of $Q$, so that $cQ(k)$ is an integer for any integer $k$. Note that $c$ depends only on $P$ and so we may assume $(p,c)=1$. Then $y_1\equiv y_i(\mathrm{mod}p)$ implies $cQ\left(y_1\right)\equiv cQ\left(y_i\right)(\mathrm{mod}p)$. - Case 1. $p\mid cQ\left(y_1\right)$. In this case, there is a cancellation of $p$ in the numerator and denominator of $\frac{cQ\left(y_i\right)}{cQ\left(y_1\right)}$, so that $m^d⩽p^{-1}\left|cQ\left(y_1\right)\right|$. Noting $\left|Q\left(y_1\right)\right|<2B{y}_1^d$ as $y_1$ is large, we get $$\begin{array}{c}m⩽p^{-\frac{1}{d}}(2cB{)}^{\frac{1}{d}}{y}_1.\end{array}\text{\hspace{1em}(2)}$$ For large $y_1$ and $y_i$, the relation $\frac{1}{2}<\frac{Q\left(y_i\right)}{Q\left(y_1\right)}<2$ implies $$\begin{array}{c}\frac{1}{3}<\frac{y_i^d}{y_1^d}<3\end{array}\text{\hspace{1em}(3)}$$ We also have $$\begin{array}{c}\frac{1}{2}<\frac{l^d}{m^d}<2\end{array}\text{\hspace{1em}(4)}$$ Now, the left-hand side of (1) is $$b_d\left(m{y}_i-l{y}_1\right)\left(m^{d-1}{y}_i^{d-1}+m^{d-2}{y}_i^{d-2}l{y}_1+\cdots +l^{d-1}{y}_1^{d-1}\right).$$ Suppose on the contrary that $m{y}_i-l{y}_1\ne 0$. Then the absolute value of the above expression is at least $\left|b_d\right|m^{d-1}{y}_i^{d-1}$. On the other hand, the absolute value of the right-hand side of (1) is at most $$\begin{array}{rl}\sum _{j=0}^{d-2}B\left(m^d{y}_i^j+l^d{y}_1^j\right)& ⩽(d-1)B\left(m^d{y}_i^{d-2}+l^d{y}_1^{d-2}\right)\\ & ⩽(d-1)B\left(7m^d{y}_i^{d-2}\right)\\ & ⩽7(d-1)B\left(p^{-\frac{1}{d}}(2cB{)}^{\frac{1}{d}}{y}_1\right)m^{d-1}{y}_i^{d-2}\\ & ⩽21(d-1)B{p}^{-\frac{1}{d}}(2cB{)}^{\frac{1}{d}}{m}^{d-1}{y}_i^{d-1}\end{array}$$ by using successively (3), (4), (2) and again (3). This shows $$\left|b_d\right|m^{d-1}{y}_i^{d-1}⩽21(d-1)B{p}^{-\frac{1}{d}}(2cB{)}^{\frac{1}{d}}{m}^{d-1}{y}_i^{d-1}$$ which is a contradiction for large $p$ as $b_d,B,c,d$ depend only on the polynomial $P$. Therefore, we have $m{y}_i-l{y}_1=0$ in this case. - Case 2. $\left(p,cQ\left(y_1\right)\right)=1$. From $cQ\left(y_1\right)\equiv cQ\left(y_i\right)(\mathrm{mod}p)$, we have $l^d\equiv m^d(\mathrm{mod}p)$. Since $(p-1,d)=1$, we use Fermat Little Theorem to conclude $l\equiv m(\mathrm{mod}p)$. Then $p\mid m{y}_i-l{y}_1$. Suppose on the contrary that $m{y}_i-l{y}_1\ne 0$. Then the left-hand side of (1) has absolute value at least $\left|b_d\right|p{m}^{d-1}{y}_i^{d-1}$. Similar to Case 1, the right-hand side of (1) has absolute value at most $$21(d-1)B(2cB{)}^{\frac{1}{d}}{m}^{d-1}{y}_i^{d-1}$$ which must be smaller than $\left|b_d\right|p{m}^{d-1}{y}_i^{d-1}$ for large $p$. Again this yields a contradiction and hence $m{y}_i-l{y}_1=0$. In both cases, we find that $\frac{Q\left(y_i\right)}{Q\left(y_1\right)}=\frac{l^d}{m^d}=\frac{y_i^d}{y_1^d}$. From the Claim, the polynomial $Q\left(y_1\right)y^d-y_1^{d}Q(y)$ has roots $y=y_1,y_2,\dots ,y_{d+1}$. Since its degree is at most $d$, this must be the zero polynomial. Hence, $Q(y)=b_d{y}^d$. This implies $P(x)=a_d{\left(x+\frac{a_{d-1}}{d{a}_d}\right)}^d$. Let $\frac{a_{d-1}}{d{a}_d}=\frac{s}{r}$ with integers $r,s$ where $r⩾1$ and $(r,s)=1$. Since $P$ has integer coefficients, we need $r^d\mid a_d$. Let $a_d=r^{d}a$. Then $P(x)=a(rx+s{)}^d$. It is obvious that such a polynomial satisfies the conditions.