Silk Road Mathematics Competition

Answer: $P(x)=ax+b$, where $a\ne 0$, $b$ are rational numbers.

Obviously, $P(x)$ is not constant, so $\mathrm{deg}P>0$.

First of all we prove that the coefficients of $P(x)$ are rational numbers. Let $\mathrm{deg}P=n$, consider $n+1$ distinct rational numbers $r_1,r_2,\dots ,r_{n+1}$ and rationals $x_1,x_2,\dots ,x_{n+1}$ such that $P(x_i)=r_i,\forall 1\le i\le n+1$. Then by the Lagrange's interpolation theorem we have $$P(x)=\sum _{i=1}^{n+1}{r}_i\frac{{\prod }_{j\ne i}(x-x_j)}{{\prod }_{j\ne i}(x_i-x_j)}$$ and it easily follows all coefficients of the polynomial are rational numbers.

Multiplying by appropriate integer we can assume that $P(x)$ has integer coefficients (and, of course, it satisfies the condition of the problem).

Let $a_n$ be the leading coefficient of $P(x)$, w.l.o.g. $a_n>0$ and let $a_0$ be the last coefficient of $P(x)$.

Consider numbers $r$ of the kind $r=p_1+a_0$, where $p_1$ is a prime number. There exist an integer $p_r$ and a positive integer $q_r$ with $(p_r,q_r)=1$ such that $P(p_r/q_r)=r$. Then it is easy to see that $p_r\mid r-a_0=p_1$ and $q_r\mid a_n$, hence, $p_r\in \{-1,1,-p_1,p_1\}$.

There are infinitely many different $r$, so taking them into consideration we obtain infinitely many different corresponding pairs $(p_r,q_r)$.

We state that among these pairs there are infinitely many $(p_r,q_r)$, for which $p_r\in \{-p_1,p_1\}$, since otherwise $|p_r/q_r|\le 1$, but $r$ can take very large values; then at some moment the equation $P(p_r/q_r)=r$ is impossible.

W.l.o.g. assume that there are infinitely many pairs $(p_r,q_r)$ with $p_r=p_1$ (if sign is negative solution is similar). Since the number of divisors of $a_n$ is finite, there are infinitely many prime numbers $p_1$ and some constant $d$ (the divisor of $a_n$) with $P(p_1/d)=p_1+a_0$.

Then consider another polynomial $f(x)=P(x/d)$. So, there are infinitely many numbers $a\in \mathbb{Z}$ for which $f(a)=a+a_0$ and, therefore, $f(x)\equiv x+c$. Finally, we have that $P(x)=dx+c$ is a linear polynomial.