Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

It is readily checked that the polynomials in the above sequence all satisfy the condition in the statement.

Conversely, let $f$ be a polynomial with complex coefficients satisfying the condition
$$1 + f(X^n + 1) = (f(X))^n. \qquad (1)$$
To begin, we show that, if $f(0) = 0$, then $f = -X$ and $n$ must be odd. To prove this, consider the sequence defined by $x_0 = 0$ and $x_{k+1} = x_k^n + 1$, $k \ge 0$. Clearly, $f(x_{k+1}) = (f(x_k))^n - 1$, $k \ge 0$, and $f(x_1) = -1$.

If $n$ is odd, induct on $k$ to prove that $f(x_k) = -x_k$, $k \ge 0$. This is clearly true if $k = 0, 1, 2$. For the induction step, use (1) to get $f(x_{k+1}) = (-x_k)^n - 1 = -(x_k^n+1) = -x_{k+1}$. With reference again to the monotonicity of the $x_k$, we conclude that $f = -X$.

Finally, consider the case $f(0) \ne 0$. Let $\omega$ be a primitive $n$-th root of unity and use (1) to deduce that $(f(X))^n = (f(\omega X))^n$, so $f(X) = \omega^m f(\omega X)$ for some non-negative integer $m < n$. Since $f(0) \ne 0$, identification of the constant terms yields $\omega^m = 1$, so $m = 0$, for $\omega$ is primitive. Hence $f(X) = f(\omega X)$ and identification of coefficients shows that $f(X)$ is a polynomial in $X^n$ with complex coefficients. Alternatively, but equivalently, $f(X) = g(X^n + 1)$ for some polynomial $g$ with complex coefficients. Since $g$ also satisfies (1), the conclusion now follows recursively.

Alternative solution – case $f(0) = 0$.
Use (1) repeatedly to obtain $f(1) = -1$, $f(2) = (-1)^n - 1$, $f(2^n + 1) = ((-1)^n - 1)^n - 1$, and deduce thereby that
$$|f(2^n + 1)| \le 2^n + 1. \quad (2)$$
We now take time out to show that the roots of $f$ all lie in the disc $|z| < 2$ in the complex plane. To this end, let $\alpha_0$ be a root of $f$ of maximal absolute value. Since the absolute value of the leading coefficient of $f$ is 1, (1) yields
$$\prod_{\alpha \text{ is a root of } f} |\alpha_0^n + 1 - \alpha| = 1. \quad (3)$$
Suppose, if possible, that $|\alpha_0| \ge 2$. If $\alpha$ is a root of $f$, then
$$|\alpha_0^n + 1 - \alpha| \ge |\alpha_0|^n - 1 - |\alpha| \ge 2|\alpha_0| - 1 - |\alpha| = (|\alpha_0| - 1) + (|\alpha_0| - |\alpha|) \ge |\alpha_0| - 1 \ge 1.$$
Since $f(0) = 0$, at least one of the factors of the product in (3) is $|\alpha_0^n + 1| \ge |\alpha_0|^n - 1 \ge 2^n - 1 \ge 3$, so the product is at least 3 — in contradiction with (3).

Back to the problem, write (2) in the form
$$\prod_{\alpha \text{ is a root of } f} |2^n + 1 - \alpha| \le 2^n + 1. \quad (2')$$
By the preceding, if $\alpha$ is a non-zero root of $f$, then $|2^n + 1 - \alpha| \ge 2^n - 1 - |\alpha| > 2^n - 3 \ge 1$, so, if the multiplicity of 0 exceeds 1 or $f$ has a non-zero root, then the product in (2') exceeds $2^n + 1$ and we reach a contradiction. Consequently, $f = aX$, where $a$ is a complex number of absolute value 1, and (1) forces $a = -1$ and $n$ odd.