Iranian Mathematical Olympiad

Lemma. If $P$ is a polynomial with integer coefficients and a square leading coefficient which for infinitely many numbers $n$, $P(n)$ is a square number, then there exists a $Q\in \mathbb{Z}[x]$ which $$P(x)=Q(x{)}^2$$ Assume $P(x)$ has the following representation $$P(x)=c_n{x}^n+c_{n-1}{x}^{n-1}+\cdots +c_0$$ According to the assumptions, there exists an integer number $c$ which $$c^2=c_n⟹P(x)=c^2{x}^n+c_{n-1}{x}^{n-1}+\cdots +c_0$$ Set $k=a{s}^2+2s$. $$ak+1=a(a{s}^2+2s)+1=a^2{s}^2+2as+1=(as+1{)}^2$$ Since $ak+1$ is a square number by the assumption one of the numbers $a_{i}k+1$ must be a square. For every integer $1\le i\le n$ define polynomial $P_i(s)$ by the following equation. $$P_i(s)=a_i(a{s}^2+2s)+1=a{a}_i{s}^2+2a_{i}s+1(1)$$ So $P_i(s)$ is a square for an integer $i$. Now put $s,s+1,\dots ,s+n$ in these polynomials. By applying pigeonhole principle two of these $i$'s are equal so $P_i(s+t),P_i(s+k)$ are square numbers for some $0\le t,k\le n$. If $s$ goes to infinity, for each $s$ there is a triple $(i,j,k)$, which $P_i(s+t),P_i(s+k)$ are square numbers. Since there are only finite number of these triples so there are infinite numbers $s$ such that they have same triples. Define polynomial $P$ such that $$P(s)=P_i(s+t)P_i(s+k).$$ Since $P_i(s+t),P_i(s+k)$ are squares so $P(s)$ is a square number too. Also because $P_i(s+t),P_i(s+k)$ are polynomials of degree 2 with the same leading coefficient $a{a}_i$ then $P(s)$ is a polynomial of degree 4 with a square leading coefficient. The lemma suggests that there exists a polynomial of degree 2 such that $$P(x)=Q(x{)}^2$$ also $$P(x)=P_i(x+t)P_i(x+k)$$ by putting together $$P_i(x+t)P_i(x+k)=Q(x{)}^2.$$ Let $D(x)$ be the greatest common divisor of $P_i(x+t),P_i(x+k)$ so $$P_i(x+t)=D(x)A(x{)}^2,P_i(x+k)=D(x)B(x{)}^2$$ Notice that $P_i(x+t),P_i(x+k)$ are polynomials of degree 2 so either of $A,B$ are constant or of degree one. If they are constant $P_i(x+t),P_i(x+k)$ should be a multiple of each other but they have same leading coefficients then they are equal which is a contradiction because we chose different $t,k$. So $D$ should be a constant but for infinite integers $s$, $D(s)A(s{)}^2$ is a square number so for some $s$, which $A(s)\ne 0$ because $a,a_i$ are positive integers and then $P_i$ can't be zero. $$\begin{array}{rl}D& =d^2⟹P_i(x+t)=(dA(x){)}^2,P_i(x+k)=(dB(x){)}^2\\ ⟹(mx+p{)}^2& =P_i(x)\stackrel{(1)}{=}a{a}_i{x}^2+2a_{i}x+1\end{array}$$ so $p^2=1$. If $p=-1$ take $$(-mx-p{)}^2=(mx+p{)}^2$$ so without loss of generality, take $p=1$ $$a{a}_i{x}^2+2a_{i}x+1=(mx+1{)}^2$$ by comparing coefficients $$a{a}_i=m^2,2a_i=2m$$ from the last equation $a_i=m$ so by putting this into the first equation $$a{a}_i=a_i^2\underset{a_i\ne 0}{\stackrel{a_i\ne 0}{\Rightarrow }}a=a_i$$ then $$a\in \{a_1,a_2,\dots ,a_n\}$$ and we are done.

---

Alternative solution.

As the first solution take $k=a{s}^2+2s$. So for an integer $i$, $P_i(s)$ is a square number. i.e. $$P_i(s)=a_i(a{s}^2+2s)+1=a{a}_i{s}^2+2a_{i}s+1$$ is a square. $$(a_{i}s+1{)}^2=a_i^2{s}^2+2a_{i}s+1$$ by subtracting these two equalities $$\begin{array}{rl}{P}_i(s)-(a_{i}s+1{)}^2& =(a{a}_i{s}^2+2a_{i}s+1)-(a_i^2{s}^2+2a_{i}s+1)=a_i(a-a_i)s^2\\ implies{P}_i(s)-(a_{i}s+1{)}^2& =a_i(a-a_i)s^2\end{array}(2)$$ By the assumption there is a positive integer $n_i$ which $$n_i^2=P_i(s)$$ so by putting this in (2) $$a_i(a-a_i)s^2=P_i(s)-(a_{i}s+1{)}^2=n_i^2-(a_{i}s+1{)}^2=(n_i-a_{i}s-1)(n_i+a_{i}s+1)$$ Let $s$ be a prime number. Assume that $a\ne a_i$. By the equality $s^2$ divides the right hand side. $$s^2\mid (n_i-a_{i}s-1)(n_i+a_{i}s+1)$$ If $s$ divides both of the numbers in the parentheses $$s\mid n_i-a_{i}s-1,s\mid n_i+a_{i}s+1$$ By subtracting $$s\mid 2a_{i}s+2⟹s\mid 2$$ So $s$ only divides one of these numbers and by assuming $a-a_i\ne 0$ $$s^2\le \max (n_i-a_{i}s-1,n_i+a_{i}s+1)\underset{a_i\ge 0}{\stackrel{a_i\ge 0}{\Rightarrow }}{s}^2\le n_i+a_{i}s+1$$ Notice that the right hand side is approximately a polynomial of degree one in terms of $s$ and it's a contradiction $$\begin{array}{rl}{s}^2& \le n_i+a_{i}s+1=\sqrt{a{a}_i{s}^2+2a_{i}s+1}+a_{i}s+1\\ implies{s}^2-a_{i}s-1& \le \sqrt{a{a}_i{s}^2+2a_{i}s+1}\end{array}$$ For large enough prime number $s$ the left hand side is a positive integer so by taking square of both sides. $$(s^2-a_{i}s-1{)}^2\le a_i{s}^2-2a_{i}s-1⟹(s^2-a_{i}s-1{)}^2-a_i{s}^2-2a_{i}s-1\le 0$$ This inequality says that a polynomial of degree four with a positive leading coefficient is a negative number for infinite prime numbers which is a contradiction. Notice that there are only $n$ possibilities for $i$ so for infinite prime numbers there is an integer $i$ that these equalities hold. ■