Iranian Mathematical Olympiad

Denote by $A = \{a^n \mid n = 1, 2, \dots\}$ and $B = \{b^n \mid n = 1, 2, \dots\}$. Let us assume $P$ and $Q$ are non-constant. Otherwise all the pairs $(a, b)$ would be the solution. We claim that if $\frac{\log a}{\log b} \in \mathbb{Q}$ then $a, b$ satisfies the problem's condition. If $\frac{\log a}{\log b} = \frac{r}{s}$ where $r, s$ are even integers, let $P(x) = x^r, Q(x) = x^s$ then, $P(t) \in A$ if and only if $t^r = a^n$ thus, $t^s = b^n$, yielding $Q(t) \in B$.

Now, if $\frac{\log a}{\log b}$ is irrational but there are polynomials $P, Q$ then there must exist $M$ such that $P(x), Q(x)$ are strictly increasing on $[M, +\infty)$. If $t > M$ satisfies the statement of the problem, then $P(t) = a^n$ for some positive integer $n$ and $Q(t) = b^m$ for some positive integer $m$. Thus, there would be $t_1 > t$ such that $P(t_1) = a^{n+1}$ and then $Q(t_1) = b^{m+N}$. If $N > 1$ then there is some $z$ such that $Q(z) = b^{m+1}$ and hence, $P(z)$ must be a power of $a$ between $a^n, a^{n+1}$, a contradiction. Hence, $N = 1$.

Analogously, we obtain a sequence $(t_k)$ such that $P(t_k) = a^{n+k}$ as well as $P(t_k) = b^{m+k}$. Notice that $\lim_{x \to +\infty} \frac{\log P(x)}{\log Q(x)} = \frac{\deg P}{\deg Q}$. Then,
$$\frac{\log a}{\log b} = \lim_{k \to +\infty} \frac{\log a^{n+k}}{\log b^{m+k}} = \lim_{t_k \to +\infty} \frac{\log P(t_k)}{\log Q(t_k)} = \frac{\deg P}{\deg Q}.$$
Remark. It is clear that $t_k$ tends to infinity and also $P$ and $Q$ would be positive for all large enough $x$. ■