Iranian Mathematical Olympiad

a) First, note that for each $x\in \mathbb{N}$ there are at most a finite number of elements of $S$ with first coordinate $x$. Therefore, for each positive number $R$, there are at most a finite number of elements of $S$ with a first coordinate less than $R$. A same assertion is true for the second coordinate.

Suppose that the set of interesting equations that $S$ satisfies is not empty. Let $P_0(x)=Q_0(y)$ be the interesting equation with minimum degree among the interesting equations that are satisfied by an infinite subset of $S$ (by the degree of the equation $P(x)=Q(y)$, we mean $\mathrm{deg}(P(x)-Q(y))$ as a polynomial with two variables). Denote by $S_0$ the subset of $S$ that satisfies this equation.

Suppose that $P(x)=Q(y)$ is an arbitrary equation that $S$ satisfies. Referring to the division algorithm in polynomials with rational coefficients, there exist rational polynomials $A(x),B(x),C(x)$ and $D(x)$ such that $$\begin{gathered} P(x)=A(x)P_0(x)+B(x),\mathrm{deg}B<\mathrm{deg}{P}_0. \\ Q(y)=C(y)Q_0(y)+D(y),\mathrm{deg}D<\mathrm{deg}{Q}_0. \end{gathered}$$ Denote by $N$ the least common multiple of the denominators of the coefficients in the polynomials of the above equations. By multiplying these equations by $N$, we get $$\begin{gathered} NP(x)=A^{\prime }(x)P_0(x)+B^{\prime }(x)(\ast ) \\ NQ(y)=C^{\prime }(y)Q_0(y)+D^{\prime }(y) \end{gathered}$$ where $A^{\prime },B^{\prime },C^{\prime }$ and $D^{\prime }$ are polynomials with integer coefficients.

If $(x_0,y_0)\in S_0$, there are some integers $a$ and $b$ such that $P(x_0)=Q(y_0)=a$ and $P_0(x_0)=Q_0(y_0)=b$. By subtracting the two equalities in () we obtain $$(A^{\prime }(x_0)-C^{\prime }(y_0))b=B^{\prime }(x_0)-D^{\prime }(y_0).(\ast \ast )$$ On the other hand, we know that $\mathrm{deg}{B}^{\prime }=\mathrm{deg}B<\mathrm{deg}{P}_0$ and $\mathrm{deg}{D}^{\prime }=\mathrm{deg}D<\mathrm{deg}{Q}_0$. Therefore, there is a real number $R>0$ such that whenever $|x|,|y|>R$, $$|B^{\prime }(x)|<\frac{1}{2}|P_0(x)|,|D^{\prime }(y)|<\frac{1}{2}|Q_0(y)|.$$ Using () and the triangle inequality, if $|x_0|,|y_0|>R$ $$|A^{\prime }(x_0)-C^{\prime }(y_0)||b|=|B^{\prime }(x_0)-D^{\prime }(y_0)|\le |B^{\prime }(x_0)|+|D^{\prime }(y_0)|<\frac{1}{2}|b|+\frac{1}{2}|b|=|b|.$$ This implies that $A^{\prime }(x_0)=C^{\prime }(y_0)$ and $B^{\prime }(x_0)=D^{\prime }(y_0)$. We know that except for a finite number of elements of $S_0$, both coordinates of the elements are greater than $R$.

Therefore, the equation $B^{\prime }(x)=D^{\prime }(y)$ has infinitely many solutions in $S$. On the other hand, the degree of this equation is less than the degree of the equation $P_0(x)=Q_0(y)$. Hence $B^{\prime }$ and $D^{\prime }$ must be constant polynomials. It means that there exists some $c\in \mathbb{Z}$ such that $B^{\prime }(x)=D^{\prime }(y)=c$. Hence $$A^{\prime }(x)=\frac{NP(x)-c}{P_0(x)},C^{\prime }(y)=\frac{NQ(y)-c}{Q_0(y)}.$$ Now, if the equation $A^{\prime }(x)=C^{\prime }(y)$ is a new interesting equation, we can repeat the above steps for this new equation.

Continuing this process, we see that there is some polynomial $F$ with rational coefficients such that $P(x)=F(P_0(x))$ and $Q(x)=F(Q_0(x))$. This means that the interesting equation $P(x)=Q(y)$ has resulted from the interesting equation $P_0(x)=Q_0(y)$.

b) First, we prove a useful lemma.

Lemma 1. Let $P(x)\in \mathbb{Z}[x]$ be a monic polynomial and $d$ be a positive integer such that $d|\mathrm{deg}P$. Show that there exist a natural number $N$ and some polynomials $T(x)$ and $R(x)$ with integer coefficients such that $$NP(x)=(T(x){)}^d+R(x),$$ and for sufficiently large values of $x$, $$(T(x){)}^d\le NP(x)\le (T(x)+1{)}^d$$ Proof.* Suppose that $\mathrm{deg}P=dm$ for some $m\in \mathbb{N}$. First, we will find a polynomial $T_1(x)\in \mathbb{Q}[x]$ such that $\mathrm{deg}(P(x)-(T_1(x){)}^d)<(m-1)d$. To do this, assume that $$P(x)=x^{md}+a_{md-1}{x}^{md-1}+\cdots +a_{1}x+a_0.$$ We must find rational numbers $b_0,b_1,\dots ,b_{m-1}$ such that for each natural number $m(d-1)\le i\le md$, the coefficient of $x^i$ in $(x^m+b_{m-1}{x}^{m-1}+\cdots +b_1+b_0{)}^d$ be $a_i$. We can find $b_i$'s recursively as rational functions of $a_i$'s. Now, let $n$ be the least common multiple of denominators of the coefficients of $T_1$. Define $T_2(x)=n{T}_1(x)$, $N=n^d$ and $S_2(x)=NP(x)-(T_2(x){)}^d$. Obviously, $S_2(x),T_2(x)\in \mathbb{Z}[x]$ and $\mathrm{deg}{S}_2>(m-1)d$. If the leading coefficient of $S_2$ is positive, set $T(x)=T_2(x)$ and $R(x)=S_2(x)$. Otherwise, if the leading coefficient of $S_2$ is negative, set $T(x)=T_2(x)-1$ and $S(x)=NP(x)-(T(x){)}^d$. It is easy to check that these polynomials have the desired properties. $\square$

Suppose that $d=(\mathrm{deg}P,\mathrm{deg}Q)$ for some natural number $d$. Using the lemma, there exist some natural number $N$ and polynomials $U,V,T$ and $R$ with integer coefficients such that $$NP(x)=(T(x){)}^d+R(x),NQ(y)=(U(y){)}^d+V(y),$$ and for sufficiently large values of $x$ and $y$, $$(T(x){)}^d\le NP(x)<(T(x)+1{)}^d,(U(y){)}^d\le NQ(y)<(U(y)+1{)}^d.$$ Note that if $d>1$, the degree of the equation $T(x)=U(y)$ is less than the degree of the equation $P(x)=Q(y)$. Furthermore, from the previous inequalities we can deduce that every solution of $P(x)=Q(y)$ is a solution of $T(x)=U(y)$ and by part a these interesting equations are both resulted from a common interesting equation with a degree less than the degree of $P(x)=Q(y)$. This contradicts the assumption of $P(x)=Q(y)$ being primitive. Hence $(\mathrm{deg}P,\mathrm{deg}Q)=d=1$.