Unique Monic Polynomials

Note first that for all $x$ , $(-x-1)^2+(-x-1)=x^2+x.$ So $(f(-x-1))^2+f(-x-1)=f((-x-1)^2+(-x-1))=f(x^2+x)= (f(x))^2+f(x)$ Therefore, $\left( f(x)-f(-x-1)\right)\cdot \left( f(x)+f(-x-1)+1\right)=0$ The product of non-zero polynomials is non-zero, so either $f(-x-1)=f(x)$ for all $x$ or $f(x)+f(-x-1)+1=0$ for all $x$ .

In the latter case, plug in $x=-\frac{1}{2}$ and get $f(-\frac{1}{2})= -\frac{1}{2}.$ Then plug in $x=-\frac{1}{2}$ into the original identity for $f(x^2+x)$ to get $f(-\frac{1}{4})=-\frac{1}{4}$ . Then plug in $x=-\frac{1}{4}$ into the same identity and get $f(-\frac{3}{16})=-\frac{3}{16}...$ Continuing this, we get $f(x_i)=x_i$ for an infinite sequence $x_i$ , with $x_{i+1}=x_i^2+x_i$ . It is easy to see that all $x_i$ are from $-1$ to $0$ and the sequence is increasing. Therefore $f(x)=x$ for infintely many $x$ , thus $f(x)=x$ for all $x$ . This polynomial obviously satisfies the conditions of the problem.

In the former case, consider polynomial $g(x)=f(x-\frac{1}{2})$ . The equation rewrites as $g(x)=g(-x)$ . This implies that all coefficients of $g$ for odd powers of $x$ are zero, so $g(x)=h(x^2)$ for some polynomial $h$ . Therefore $f(x)=g(x+\frac{1}{2})=h(x^2+x+\frac{1}{4})$ , so $f(x)=p(x^2+x)$ for some polynomial $p.$ Rewriting the original identity in terms of $p$ , we get $p((x^2+x)^2+(x^2+x))= (p(x^2+x))^2+p(x^2+x)$ So for all $t$ that can be expressed as $t=x^2+x$ , we get $p(t^2+t)=(p(t))^2+p(t)$ . Since there are infinitely many such $t$ , this identity is true for all $t$ . So the polynomial $p$ satisfies the same conditions (notice that it is monic as well). The degree of $p$ is half the degree of $f$ . This reduction cannot continue forever, and the only way it can stop is if we arrive at the polynomial $f(x)=x$ . This implies that all polynomials satisfying the conditions of the problem are from the sequence $f_i(x)$ defined as follows: $f_0(x)=x;\ f_{i+1}(x)=f_{i}(x^2+x),\ i=0,1,2,...$ Note that the degree of $f_i$ (the $i$ -th composite power of $x^2+x$ ) is $2^i$ . Therefore the degree of $f_i$ is less than $1000$ for $i=0,1,...,9$ , which gives $10$ as the answer.

Let there exist a function f(x) satisfying the conditions. Consider the function $g(x)=f(f(x))$ . Note that $g(x^2+x)=f(f(x^2+x))=f(f(x)^2+f(x))=f(f(x))^2+f(f(x))=g(x)^2+g(x)$ . Also note that as f(x) is monic, g(x) is also monic. Therefore, if f(x) satisfies the given conditions, so does f(f(x)).

$f(x)=x$ clearly satisfies the conditions.

Note that if $P(x) = P(y)$ whenever $Q(x) = Q(y)$ , then there exists a polynomial R such that $P(x) = R(Q(x))$ . Therefore, the set ${f(x), f(f(x)), f(f(f(x)), ...}$ gives all solutions. As the degree must be less than 1000, and there exists exactly one solution for each degree that is a power of 2, our answer is $\lceil \log_{2} 1000 \rceil=11$