$p(q(t)) \neq q(p(t))$ for every $t$, find all degrees of monic polynomials 
Find all the positive numbers $m, n$ for which there exist some monic polynomials $p$ and $q$, for which $\deg p = m$ and $\deg q = n$, while $f \circ g$ and $g \circ f$ have no intersection points.

Source: Taiwanese TST for IMO 1991
Attempt: Monic polynomial of degree $1$ composition is commutative (easy to observe that $(x + \alpha) + \beta = (x + \beta) + \alpha$). Therefore, case $m = n = 1$ could not be valid.
Again, if we have $n = 1$, and $q(x) = x + \gamma$, we will find that:
$$\deg(p(x + a) - p(x) - a) = \deg p - 1 = m - 1$$
Which is odd if $m$ even, meaning that $p(q(t)) - q(p(t))$ will have at least one solution. (Complex roots are always paired/conjugates, an odd degree polynomial has an odd number of roots, including multiplicity, so there is at least one real root / solution to every odd degree polynomial).
So pairs like (2k, 1) and, by symmetry, $(1, 2k)$ are excluded.
My conjecture is that all the others $(m, n) \in \mathbb{N}^2$ have a solution (some monic polynomials $p$ and $q$ that have no solution). For at least one of $m$, $n$ even, I've found the solutions $x^m$ and $x^n + \mathcal{C}$. Their difference of compositions would be, by applying Newton binomial expansion, a sum of even powers multiplied with binomial coefficients, therefore always strictly positive, so I've found the example. However, no clue for both polynomials of odd degree.
 A: Why not just plug in the general case like you did when n=m=1.
Let
$$
p(x)=x^m+\alpha_{m-1} x^{m-1} + \cdots + \alpha_1 x + \alpha_0, \\q(x)=x^n+\beta_{n-1} x^{n-1} + \cdots + \beta_1 x + \beta_0,
$$
then
$$
p(q(x))-q(p(x))\\
=(x^n+\beta_{n-1} x^{n-1} + \cdots + \beta_0)^m +\alpha_{m-1}(x^n+\beta_{n-1} x^{n-1} + \cdots + \beta_0)^{m-1}+\cdots+\alpha_1(x^n+\beta_{n-1} x^{n-1} + \cdots  + \beta_0) +\alpha_0
-(x^m+\alpha_{m-1} x^{m-1} + \cdots + \alpha_1 x + \alpha_0)^n - \beta_{n-1}(x^m+\alpha_{m-1} x^{m-1} + \cdots + \alpha_1 x + \alpha_0)^{n-1}-\cdots -\beta_0.
$$
There exist some $\alpha_{m-1}$ and $\beta_{n-1}$ such that the coefficient of $x^{mn-1}$ is not zero, i.e. $m\beta_{n-1}-n\alpha_{m-1}\neq0$.  Therefore,
$$
\deg(p(q(t))-q(p(t)))=mn-1,
$$
and $p(q(t))-q(p(t))=0$ has at least one real root when $mn-1$ is odd and $m\beta_{n-1}-n\alpha_{m-1}\neq0$.
Edit:
However, we can select the coefficients to make $m\beta_{n-1}-n\alpha_{m-1}=0$, and since $mn-1$ is odd, then
$$
\deg(p(q(t))-q(p(t)))=mn-2 \quad \text{is even},
$$
and $p(q(t))-q(p(t))=0$ can have no real root.
Thus except when $(m, n) = (1,1),(1,2k),(2k,1)$, there exist some monic polynomials $p$ and $q$, such that $p(q(t))≠q(p(t))$
for every real number $t$.
