11-th Czech-Slovak-Polish Match, 2011

For the sake of contradiction suppose that $P(x)$ is not constant and consider the case when $P(x)$ is a linear polynomial. It means that $P(x)=ax+b$ for some $a,b\in \mathbb{Z}$, where $a\ne 0$. Let $Q(x)=a{x}^2+(b+1)x$. Then $$P(Q(x))=a(a{x}^2+(b+1)x)+b=a^2{x}^2+a(b+1)x+b=(ax+b)(ax+1)$$ but polynomials $ax+b$ and $ax+1$ are not constant, a contradiction.

Now suppose that $\mathrm{deg}P=n>1$. Suppose also that $$P(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0,$$ where $a_n\ne 0$. Consider a polynomial $Q(x)=P(x)+x$. Clearly it has integer coefficients. Moreover, $$P(Q(x))-P(x)=P(P(x)+x)-P(x)=\sum _{i=0}^n{a}_i((P(x)+x{)}^i-x^i)$$ From the formula $$a^i-b^i=(a-b)(a^{i-1}+a^{i-2}b+\cdots +b^{i-1})$$ it follows that the polynomial $(P(x)+x{)}^i-x^i$ is divisible by the polynomial $P(x)$. So $P(Q(x))$ is divisible by $P(x)$ as well. But this is a contradiction, since $\mathrm{deg}P>1$ implies that the degree of $P(Q(x))$ is greater than the degree of $P(x)$, which means that $P(x)$ is a non-trivial divisor of $P(Q(x))$. Conclusion follows. $\square$