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.
Best Answer
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$.