Iranian Mathematical Olympiad

It is clear that the solutions of the inequality, $|P(x)|\le M$, is a subset of an interval of the form $(-a,a)$ for some positive real number $a$. Now, assume $\mathrm{deg}Q(x)=d\ge m$. Consider, integers $x_0<\cdots <x_d$. Then by Lagrange's interpolation formula, one can find that $$Q(x)=\sum _{i=0}^{d}Q(x_i)\prod _{i\ne j}\frac{x-x_j}{x_i-x_j}$$ Since, $Q(x)$ is monic, we can find that $$1=\sum _{i=0}^{d}Q(x_i)\prod _{i\ne j}\frac{1}{x_i-x_j}$$ The right hand side is less than or equal to $$\underset{i}{\max }|Q(x_i)|\sum _{i=0}^d\frac{1}{i!(d-i)!}<\underset{i}{\max }|Q(x_i)|\cdot \frac{2^d}{d!}$$ Hence, $$\underset{i}{\max }|Q(x_i)|>\frac{d!}{2^d}\ge \frac{m!}{2^m}$$ Now, choose $m$, such that $\left(-\frac{m!}{2^m},\frac{m!}{2^m}\right)\subseteq (-a,a)$. We deduce that, from any $d+1$ integers, at least one of them satisfies that inequality $|Q(x)|>\frac{m!}{2^m}$. But, all the integer solutions of the inequality $|P(Q(x))|\le M$, must satisfy the inequality $|Q(x)|\le \frac{m!}{2^m}$. Hence the claim of the problem. ■