37th Iranian Mathematical Olympiad

We firstly prove that there exists an index $i$ such that $\mathrm{deg}{P}_i(x)=\mathrm{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 $\mathrm{deg}P(x)$ and $\mathrm{deg}{P}_i(x)>\mathrm{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)\ne 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)<\cdots <P(k{N}_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(k{N}_0)$. Therefore, we at most have $t{N}_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 $\mathrm{deg}{P}_i(x)=\mathrm{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}d\ge 2,$$ $$P_i(x)=x^d+b_{d-1}{x}^{d-1}+\cdots +b_0,$$ then, $$\begin{array}{rl}{x}^d-y^d& =b_{d-1}{y}^{d-1}+\cdots +b_0-(a_{d-1}{x}^{d-1}+\cdots +a_0)\\ ⟹|x^d-y^d|& \le c\sum _{i=1}^{d-1}|x{|}^i+|y{|}^i\le cd(x^{d-1}-y^{d-1})\\ ⟹\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{array}$$ 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 $\mathrm{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)⟹P_i(x+1)-P_i(x)\le c$$ for infinitely many $x$. So, $P_i(x)$ should be linear and we're done. ■