47-я Международная Математическая OлимпиадаСловения, Любляна, 2006 год

Пусть $P\left( x \right)$ — многочлен степени $n > 1$ с целыми коэффициентами, $k$ — произвольное натуральное число. Рассмотрим многочлен $Q(x)=P(P(\ldots P(P(x))\ldots ))$ (здесь $P$ применен $k$ раз). Докажите, что существует не более $n$ целых чисел $t$ таких, что $Q\left( t \right)=t$.

Комментарий/решение

Предположим, что нашлось множество $S$ из $n+1$ целых различных чисел, каждое $t\in S$ которое удовлетворяет $Q(t)=t$. По целочисленной теореме Безу:

$$x-y\mid P(x)-P(y)\mid P(P(x))-P(P(y))\mid\dots\mid P^{k-1}(x)- P^{k-1}(y)\mid P^k(x)-P^k(y)=Q(x)-Q(y)$$

Для любых $x,y\in S$, $x-y=Q(x)-Q(y)$ делится на $P(x)-P(y)$. Кроме того, $P(x)-P(y)$ делится на $x-y$ по лемме Безу. Значит $\vert P(x)-P(y)\vert=\vert x-y\vert$. Допустим, что нашлись $x,y,z\in S$ такие, что $P(x)-P(y)=x-y$ и $P(x)-P(z)=-(x-z)$. Тогда $P(y)-P(z)=y+z-2x$. Либо $z-y=y+z-2x$ либо $y-z=y+z-2x$. В первом случае выходит, что $x=z$. А во втором случае $y=z$. В любом случае противоречие, ведь числа в $S$ различны. Получается, что либо $P(x)-P(y)=x-y$ для всех $x,y\in S$, либо $P(x)-P(y)=y-x$ для всех $x,y\in S$.

Б.О.О будем считать, что $P(x)-P(y)=x-y$ (другой случай аналогичен). Тогда $P(x)-x=P(y)-y$ для всех чисел $x,y\in S$. Пусть все $P(x)-x$ равны константе $C$. Тогда уравнение $P(x)-x-C=0$ - многочлен степени $n$ который имеет более $n$ корней. То есть, $P(x)+x\equiv C$. Но тогда $P(x)=C-x$ - многочлен степени 1, но по условию $n>1$. Противоречие.