@above, Beautiful ! Just, one case is missed which is $(2k,1)$, but it does not work because the polynomial $P(x+a)-(P(x)+a)$ has odd degree ( $Q(x)=x+a$ ).

Here is a more analytic way to handle math90's second case. Let $P(x) = x^m$ and $Q(x) = x^n + a$ for any $a > 0$ satisfying $\left(\tfrac{a}{2}\right)^m > a$ (e.g. $a = 3$). We must prove that $(P \circ Q) - (Q \circ P)$ has no roots in $\mathbb{R}.$ Compute \[ P(Q(x)) - Q(P(x)) = (x^n + a)^m - x^{mn} - a = f(x^n), \]where $f: \mathbb{R} \mapsto \mathbb{R}$ is given by \[ f(x) = (x + a)^m - x^m - a. \]Thus, it suffices to show that $f$ has no roots in $\mathbb{R}.$ Suppose by way of contradiction that $f$ has a root $s \in \mathbb{R}.$ As $f$ is a polynomial of even degree, it must have another root $t \in \mathbb{R}.$ If $s = t$ then $f'(t) = 0$; otherwise, we can assume WLOG $s < t$, so by the Mean Value Theorem, there exists a root of $f'$ in $(s, t).$ In either case, we have found a root of $f'$ that is $\le t.$ Then since \[ f'(x) = m(x + a)^{m - 1} - mx^{m - 1} \]has only one real root at $x = -\tfrac{a}{2}$, we must have $t \ge -\tfrac{a}{2}.$ We will show that this is impossible by proving that $f(x) > 0$ for all $x \ge -\tfrac{a}{2}.$ If $x \ge 0$, then \[ f(x) = (x + a)^m - x^m - a \ge (x^m + a^m) - x^m - a = a^m - a > 0. \]If $-\tfrac{a}{2} \le x < 0$, then \[ f(x) = (x + a)^m - x^m - a \ge \left(\frac{a}{2}\right)^m - x^m - a > -x^m > 0. \]Therefore $f(x) > 0$ for all $x \ge -\tfrac{a}{2}$, which contradicts $f(t) = 0.$

Fun problem If $(m,n) = (1,2m)$ then $p(q(x))-q(p(x))$ the degree is odd and have root. If $(m,n) = (1,1)$ then we can suppose $p(x)=ax+b$ and $q(x)=cx+d$ . Then we can find a, b, c, d for which this equation has no solution. Most of the behavior of a polynomial is determined by its constant term. Then we can suppose $p(x)=x^m+c$ and $q(x) = x^n$ . Then $$(x^m+c)^n-(x^n)^m-c > 0$$( ) In ( ) if $m$ be even then it is easy to see our problem is solved . In ( ) if $m$ be odd then we can let $X=x^m$ . then $f(x) = (X+c)^n-X^n-c$ and we know $deg(f(x)) = 2k$.Now we have to check the extremes of our function . Obviously, if all extremums of the function are greater than zero, then our function does not have a root . $$f^{'}(x) = n(X+c)^{n-1}-nX^{n-1}$$. And we want to check this ! : $$n(X+c)^{n-1}=nX^{n-1} \to (X+c)^{n-1}=X^{n-1}$$. It mean $X+c=X$ or $X+c=-X$ . Then we can see $c=0$ or $X=-\frac{c}{2}$ . So we understand that our function becomes zero only at one point . So either it doesn't have a root or it has $2$ roots . If we put $X=-\frac{c}{2}$ in $f(x)$ then our phrase is $2(\frac{c}{2})^n-c$ . ( ) In ( ) if $\lim_{c \to +\infty }$ we can see our phrase is possitive . Then $f(x) > 0 $ and my polynomial don't have any root .

HuangZhen wrote: Find out all the integer pairs $(m,n)$ such that there exist two monic polynomials $P(x)$ and $Q(x)$ ,with $\deg{P}=m$ and $\deg{Q}=n$,satisfy that $$P(Q(t))\not=Q(P(t))$$holds for any real number $t$. Nice problem you have

I claim that $\boxed{(m, n) \in \mathbb{N}^2 \slash \{(1, 1), (1, 2k), (2k, 1) \} }$ are the only possible solution pairs. Indeed when $(m, n) = (1, 1)$ we have that $P \circ Q = Q \circ P$ for every real value. Now if $m = 1$, then observe that $P(Q(x)) - Q(P(x)) = 0$ when the degree of $Q$ is even, (as then the equation is odd), and likewise when $n = 1$ a symmetric argument may ensue. Assume then that $m, n > 1$. I claim that we are then able to find suitable $P, Q$ for which $P \circ Q \neq Q \circ P$ for all real values. We first split into two separate cases: Case 1: (At least one of $m, n$ even). Then let $P(x) = x^m$ and $Q(x) = x^n + k$ with $k \geq 3$. Now let $R(x) = P(Q(x)) - Q(P(x))$. We show that these values of $P, Q$ give that $R(x) > 0$ for every real value $x$: \begin{align*} R(X) &= P(Q(x)) - Q(P(x)) \\ &= (x^n + k)^m - x^{nm} - k \\ &= \binom{m}{1}x^{n(m - 1)}k^1 + \binom{m}{2}x^{n(m - 2)}k^2 \cdots + k^m - k \\ &> 0. \text{ }\square \end{align*} Case 2: (Both $m, n$ are odd). Let $P$ and $Q$ be the same functions from the first case. We assume by way of contradiction that as here $R(x)$ is even, that $R(x)$ contains at least two arbitrary roots (multiplicities excluded, else we have an actual root). Let these roots be $a, b$. Then we must have that there is some $t \in (a, b)$ for which $R'(t) = 0$: \[R'(x) = m(x^n + k)^{m - 1}(nx^{n - 1}) - nm(x^{nm - 1}) = 0 \implies x^n = -\frac{k}{2} \implies x = - \sqrt[n]{\frac{k}{2}}. \]Now we show that $R(t) > 0$ for all $t \geq -\sqrt[n]{\frac{k}{2}}$, which would provide us with our contradiction. Subcase 1: ($t \geq 0$). Then \begin{align*} R(t) &= (t^n + k)^m - t^{nm} - k \\ &\geq t^{nm} + k^m - t^{nm} - k \\ &= k^m - k \\ &> 0. \text{ } \bigstar \end{align*} Subcase 2: $\left(t \in \left[ -\sqrt[n]{\frac{k}{2}}, 0 \right) \right)$. Then \begin{align*} R(t) &= (t^n + k)^m - t^{nm} - k \\ &\geq \left(\frac{k}{2}\right)^m - \left(-\frac{k}{2}\right)^m - k\\ &= 2 \left(\frac{k}{2}\right)^m - k \\ &>0. \text{ } \bigstar \square \end{align*} Therefore as $R(x) > 0$ and $R(x)$ has two roots, we obtain a contradiction, as desired. $\blacksquare$