Iranian Mathematical Olympiad

We firstly prove that there exists an index $i$ such that $\deg P_i(x) = \deg P(x)$ and $P(x) = P_i(y)$ for infinitely many $x, y \in \mathbb{N}$.
Assume to the contrary. Let the degree of $P_{t+1}(x), \dots, P_n(x)$ be equal to $\deg P(x)$ and $\deg P_i(x) > \deg P(x)$ for all $i \in \{1, 2, \dots, t\}$.
Consider a sufficiently large $N_0$ such that:
1) $P(x)$ is increasing for all real numbers $x > N_0$.
2) $P(x) \neq P_i(y)$ for all positive integers $t+1 \le i \le n$ and $x, y$.
3) $P_i(x) > P(kx)$ for all positive integers $1 \le i \le t$, all real numbers $x > N_0$, and a fixed number $k > t$.
4) $P_i(x)$ is increasing for all positive integers $1 \le i \le t$ and every $x > N_0$.
Then, let's assume that
$$P(N_0 + 1) < \dots < P(kN_0).$$
We know every one of them is in the form of $P_i(y)$. Where $1 \le i \le t$ and $y$ is a natural number.
If we have $P(N_0 + i) = P_j(x_i)$ for some $j$, then we have $x_i \le N_0$. So, we at most have $N_0$ numbers in form of $P_j(y)$ between $P(N_0 + 1), \dots, P(kN_0)$. Therefore, we at most have $tN_0$ numbers between them. And since $k > t$, it gives us a contradiction.
So we must have an index $i$ such that the equation $P(x) = P_i(y)$ has infinitely many solutions and $\deg P_i(x) = \deg P(x)$. We want to prove that if $P(x) = P_i(y)$, then $|x - y|$ has a fixed upper bound.
Without loss of generality, assume that the leading coefficient of $P(x) - P_i(x)$ is positive. Then, assume a sufficiently large $N_1$ such that $P(x), P_i(x)$ and $P(x) - P_i(x)$ are increasing for all real numbers $x > N_1$. Then, if $x, y > N_1$, $P(x) = P_i(y)$, we have $x \ge y$ since $P(x) \ge P_i(x) \ge P_i(y)$. If we take a sufficiently large $x$ we can find out that $y$ becomes large as well. Then if

$$P(x) = x^d + a_{d-1}x^{d-1} + \cdots + a_0 \quad d \ge 2,$$
$$P_i(x) = x^d + b_{d-1}x^{d-1} + \cdots + b_0,$$
then,
$$\begin{align*} x^d - y^d &= b_{d-1}y^{d-1} + \cdots + b_0 - (a_{d-1}x^{d-1} + \cdots + a_0) \\ \implies |x^d - y^d| &\le c \sum_{i=1}^{d-1} |x|^i + |y|^i \le cd (x^{d-1} - y^{d-1}) \\ \implies \frac{|x^d - y^d|}{x^{d-1} + y^{d-1}} &= \frac{x^d - y^d}{x^{d-1} + y^{d-1}} \le cd. \end{align*}$$
And we have
$$x - y \le \frac{x^d - y^d}{x^{d-1} + y^{d-1}} \le cd.$$
So, $x - y \le cd$. Therefore, there exists a number $k$ such that $x - y = k$ for infinitely many times.
Then we get $P(x) = P_i(x - k)$ for infinitely many $x$ and we're done.
The case that $\deg P(x) = 1$ is trivial and if $P(x) - P_i(x) = c$, then we'll have $P(x) = P_i(y)$ and $P_i(y) - P_i(x) = c$. Consider sufficiently large $x, y$ such that $P_i(x)$ is increasing. If $x \ne y$,
$$P_i(y) \ge P_i(x+1) \implies P_i(x+1) - P_i(x) \le c$$
for infinitely many $x$. So, $P_i(x)$ should be linear and we're done. ■