Belarusian Mathematical Olympiad

Answer: all $(m,n)$ with odd $m$ and arbitrary $n$; or $(m,n)$ with even $m$ and even $n$. (Solution of A. Zhuk.)

1. Let $m$ be odd. Show that any positive $n$ is appropriate. Indeed, if $P(x)\equiv x$, then $Q(P(x))\not\equiv Q(x)$ for any $Q\in \mathbb{R}[x]$. If $P(x)\not\equiv x$, then $P(x)-x$ is a polynomial of odd degree, hence it has a real root, say, $a$. Then for any $n\in \mathbb{N}$ consider $Q(x)=(x-a{)}^n$. We have $Q(P(x))=(P(x)-a{)}^n$. Note that $P(x)-a=(P(x)-x+(x-a))\not\equiv (x-a)$. Hence $(P(x)-a{)}^n\not\equiv (x-a{)}^n=Q(x)$, as we need.

2. Now, let $m$ be even. First, show that $n$ cannot be odd. Set, for example, $P(x)=x^m+x+1$. Then $P(x)-x>0$ for any $x\in \mathbb{R}$. If $n$ is odd, then $Q(x)$ has real roots. Let $c$ be the largest real root of $Q$. That is $$Q(x)=b(x-c)\prod _{i=1}^k(x-a_i)\cdot \prod _{j=1}^l{q}_j(x),$$ where all $q_j(x)$ are monic quadratic polynomials with negative discriminants, $c\ge a_i$ for all $i=1,2,...,k$, $b\ne 0$. Then $$Q(P(c))=b(P(c)-c)\prod _{i=1}^k(P(c)-a_i)\cdot \prod _{j=1}^l{q}_j(P(c)).$$ Note that $P(c)-c>0$, $P(c)-a_i>c-a_i\ge 0$, $(\forall i=1,...,k)$, $q_j(P(c))>0$ $(\forall j=1,...,l)$, that is $Q(P(c))\ne 0$. Hence, $c$ is not a root of $Q(P(x))$, so $Q(P(x))\not\equiv Q(x)$.

Let now both $m$ and $n$ be even, $n=2k$. If $P(x)-x$ has a real root $a$, then, as above, we set $Q(x)=(x-a{)}^n$, and we are done. Let $P(x)-x$ has no real roots. Let $z$ and $\bar{z}$ be any complex-conjugate roots of $P(x)$, that is $P(x)-x$ is divisible by $p(x)=(x-z)(x-\bar{z})\in \mathbb{R}[x]$. Set $Q(x)=(p(x){)}^k$. Then $Q(P(x))=(p(P(x)){)}^k$. It suffices to prove that $p(P(x)):p(x)$. Note that $p(P(x))=p(P(x))-p(x)+p(x)$ and $$(p(P(x))-p(x)):(P(x)-x):p(x).$$ Therefore, $$Q(P(x))=(p(P(x)){)}^k:(p(x){)}^k=Q(x).$$