11.9. A polynomial $P(x)$ with real coefficients has degree $10^{5}$, and its leading coefficient is 1. Find the smallest possible degree of the polynomial

$$
R(x)=P\left(x^{1000}+1\right)-P(x)^{1000}
$$

(I. Bogdanov)
Answer. $99 \cdot 10^{6}$.

First solution. Let $n=1000, k=100$, that is, the degrees of the polynomials $P$ are $n k$.

Lemma. There exists a unique polynomial $P$ of degree $n k$ (with leading coefficient 1) such that the degree of the resulting polynomial $R$ will be less than $n k(n-1)$.

Proof. Write our polynomial as

$$
P(x)=x^{n k}+p_{1} x^{n k-1}+p_{2} x^{n k-2}+\ldots+p_{n k}
$$

Denote $F(x)=P\left(x^{n}+1\right)$ and $G(x)=P(x)^{n}$; these are polynomials of degree $n^{2} k$ with leading coefficient 1.

In the polynomial $F(x)$, the coefficient $p_{j}$ participates only in terms of degree not greater than $n(n k-j)$. Therefore, for any $i=1,2, \ldots, n k$, the coefficient of $x^{n^{2} k-i}$ in the polynomial $F(x)$ depends only on the coefficients $p_{j}$ for $j \leqslant i / n<i$. On the other hand, the coefficient of the same degree in $G(x)$ is $n p_{i}+A$, where $A$ depends only on the coefficients $p_{j}$ for $j<i$. If we want the degree of $R$ to be less than $n k(n-1)$, then these coefficients must be equal; this equality gives a unique expression for $p_{i}$ in terms of $p_{1}, p_{2}, \ldots, p_{i-1}$ (in particular, $p_{1}$ is found uniquely). Therefore, from these equalities, the coefficients of the polynomial $P(x)$ are found one by one.

Now it is sufficient to present a polynomial $P(x)$ such that the degree of $R$ will be less than $n k(n-1)$ - by the lemma, it is unique, and it will give the minimum degree of $R$. Let $P(x)=\left(x^{n}+1\right)^{k}$. Then the polynomial

$$
\begin{aligned}
& R(x)=\left(\left(x^{n}+1\right)^{n}+1\right)^{k}-\left(x^{n}+1\right)^{n k}= \\
& \quad=k \cdot\left(x^{n}+1\right)^{n(k-1)}+C_{k}^{2}\left(x^{n}+1\right)^{n(k-2)}+\ldots
\end{aligned}
$$

has degree only $n^{2}(k-1)<n k(n-1)$. Therefore, the smallest possible degree of $R$ is $n^{2}(k-1)=99 \cdot 10^{6}$.

Remark. In the solution above, the desired polynomial is "guessed". This can be done by considering a sufficiently "small" case (for example, $k=2$). Another way to find the required polynomial is visible in the following solution.

Second solution. Using the same notation $n$ and $k$ as in the first solution. We will assume that

$$
\operatorname{deg} R<n^{2} k-n k
$$

(later we will see that this is possible; therefore, for the polynomial $R$ of minimum degree, it can be assumed).

Suppose that the polynomial $P(x)$ has a monomial of degree not divisible by $n$; let $a_{s} x^{s}$ be such a monomial of the highest degree. Then the coefficient of the polynomial $R$ at $x^{n k(n-1)+s}$ is $-n a_{s}$, which contradicts ( $(*)$.

Thus, under the assumption (*), the degrees of all monomials in $P(x)$ are divisible by $n$; in other words, there exists a polynomial $Q$ such that $P(x)=Q\left(x^{n}\right)$. Then

$$
R(x)=P\left(x^{n}+1\right)-P(x)^{n}=Q\left(\left(x^{n}+1\right)^{n}\right)-Q\left(x^{n}\right)^{n}
$$

that is, $R(x)=R_{1}\left(x^{n}\right)$, where

$$
R_{1}(y)=Q\left((y+1)^{n}\right)-Q(y)^{n}
$$

with $\operatorname{deg} Q=k<n$, and the assumption (*) means that $\operatorname{deg} R_{1}<n k-k$.

Consider the polynomial $R_{2}(x)=R_{1}(x-1)=Q\left(x^{n}\right)-Q(x-$ $-1)^{n}$ (then $\operatorname{deg} R_{2}=\operatorname{deg} R_{1}$ ). Analogously to the reasoning above, suppose that $Q(x-1) \neq x^{k}$, that is, there are monomials in the polynomial $Q(x-$ - 1) other than $x^{k}$; let $b_{t} x^{t}$ be such a monomial of the highest degree. Then in the polynomial $R_{2}(x)$ there is a monomial $-n b_{t} x^{n k-k+t}$, which contradicts the inequality $\operatorname{deg} R_{2}<n k-k$. Therefore, $Q(x-1)=x^{k}$, and then $Q(x)=(x+1)^{k}$ and $P(x)=$ $=\left(x^{n}+1\right)^{k}$. We arrive at the same example as in the first solution (and see that in this case the degree of $R$ indeed satisfies $(*)$ ).

Comment. The points listed below for various advancements do not add up to each other.

Only a correct example of a polynomial $P$ is given, for which $\operatorname{deg} R=n^{2}(k-1)$, without proving its optimality - 3 points.

It is only proved that in the optimal polynomial $P$ there are no monomials of degree not divisible by $n$ (the optimality condition can be replaced by reasonable assumptions about the degree of $R$, as in the second solution) - 1 point.

It is only proved that there is exactly one polynomial $P$ that satisfies the condition under which $\operatorname{deg} R<n k(n-1)-$ 2 points.