Hungary OL 1996

[rsoldo]

Let $P(x)$ be a polynomial of the $n$-th degree with real coefficients. Prove that the equation $P(P(P(x)))=0$ cannot have a root multiplicite of $n^3-n^2+1.$

[Null]

Кратный корень порядка $n^3-n^2+1$?

[Dendr]

Голова сейчас не очень соображает, поэтому больше набросок "с нуля", чем доказательство.

Для $n=1$ у нас получается линейная зависимость все равно, поэтому о кратности речи не идет, значит, неявно предполагается, что $n>1$

(Оффтоп)

Если $P(x)$ порядка $n$, то $Q(x)=P(P(P(x)))$ - порядка $n^3$. Допустим, один из его корней $x_0$ имеет кратность $k=n^3-n^2+1$.
Тогда $Q(x)=(x-x_0)^k\cdot \prod\limits_{i=1}^{n^2-1}(x-x_i)$, где $x_i \ne x_0 \forall i>0$

Соответственно, $\forall m<k: \left.\frac{d^m}{dx^m}Q(x)\right|_{x=x_0}=0$, а $\left.\frac{d^k}{dx^k}Q(x)\right|_{x=x_0}\ne0$. Выясним, как выглядят производные $Q(x)$:
$Q'(x)=P'(P(P(x)))\cdot P'(P(x))\cdot P'(x)$
По предположению, у этого многочлена $x_0$ есть корень $x=x_0$ кратности $k-1=n^3-n^2$. Но $P'(x)$ - многочлен порядка $n-1$, $P'(P(x))$ - порядка $n(n-1)$, поэтому их произведение - многочлен порядка $n^2-1<n^3-n^2$: сократив обе части неравенства на $n-1$, получаем $n+1<n^2$, что верно для $n\ge2$.
Таким образом (в нашем предположении), $P'(P(P(x_0)))=0$. Обозначив $y_0=P(P(x_0))$, получим следующее наблюдение: $P(y_0)=0, P'(y_0)=0$, откуда исходный многочлен должен иметь вид $P(x)=(x-y_0)^2\cdot P_1(x)$.
Отсюда сразу следует, что при многочлен второй степени может быть записан только как $P(x)=c(x-a)^2$, значит, $Q(x)=c(c(c(x-a)^2-a)^2-a)^2$. Очевидно и без решения, что корни этого многочлена имеют четную кратность, то есть кратность $2^3-2^2+1=5$ недостижима.

Если $n>2$, смотрим дальше. Вторая производная $Q(x)$:
$Q''(x)=P''(P(P(x)))\cdot (P'(P(x))\cdot P'(x))^2+P'(P(P(x)))\cdot (P'(P(x))\cdot P'(x))'$
У этого выражения есть корень $x=x_0$, кратность которого равна $k-2$.
Отделяя второе слагаемое, замечаем, что оно (см. пред. абзац) равно нулю при этом $x$. Ясно, что кратность этого корня (у отдельного слагаемого) не меньше $k-2$. Значит, равно нулю и первое, с кратностью $k-2=n^3-n^2-1$. $(P'(P(x))\cdot P'(x))^2$ - многочлен порядка $2(n^2-1)$, что меньше $n^3-n^2-1$ при $n\ge3$, то есть $P''(y_0)=0$, и мы приходим к тому, что $P(x)=(x-y_0)^3\cdot P_2(x)$. Рассуждая так же, как и выше, получаем, что при $n=3$ кратности корней $Q(x)$ должны делиться нацело на $3$, то есть ни одна не может быть равна $3^3-3^2+1=19$.

Продолжая дифференцировать $Q(x)$, приходим последовательно к условиям $Q^{(m)}(x_0)=P^{(m)}(y_0)\cdot(P'(P(x_0))\cdot P'(x_0))^m=0$, причем корень $x=x_0$ порядка $k-m$. Повторяем до тех пор, пока $k-m>m(n^2-1)$, или $n+\frac{1}{n^2}>m+1$, т.е. $m\le n-1$, и каждый раз можем записать, что $P^{(m)}(y_0)=0$ для всех $m=0, 1, ..., n-1$, откуда следует, что $P(x)=C(x-y_0)^{n}$.

Получается: из того, что у многочлена $P(P(P(x)))$ есть корень $x_0$ кратности $n^3-n^2+1$ (и выше), следует, что сам многочлен имеет вид $P(x)=C(x-a)^n$. Но тогда кратность корня $x_0$ обязана делиться на $n$, то есть $1|n$, или $n=1$, но этот случай не рассматривается.

[rsoldo]

Official hint:
The left side of the equation is a polinom and it is enough to examine its roots. Denote the roots of the polynomial $P(X)$ with $x_1,x_2,...,x_n.$ We are looking at the product:

$$(P(P(x))-x_1)\cdot (P(P(x))-x_2)\cdots(P(P(x))-x_n).$$

Sorry: Problems with the Hungarian prevented me for doing more.

[TOTAL]

rsoldo в сообщении #1598410 писал(а):

Official hint:

"cannot have a root multiplicite of $n^3-n^2+1.$"
Пожалуйста, вот это другими словами объясните. Что надо доказать?

[maxal]

rsoldo, идея понятна - дальше в купе с принципом Дирихле следует, что $P(x)=(x-a)^n+b$ для некоторых $a,b$...

[Руст]

Многочлен $P(x)=x^n$, $P(P(P(x)))=x^{n^3}$ имеет корень кратности $n^3$.

[maxal]

Руст и что? $n^3\ne n^3-n^2+1$