Japan 2013 Final Round

We will show that smallest possible value for $m$ is $2n^2-1$. If we let $a_k=2k^2-1$ for $k=1,2,\dots ,n$, then we see that $$\frac{a_k^2+a_{k+1}^2}{2}=\frac{(2k^2-1{)}^2+(2(k+1{)}^2-1{)}^2}{2}=(2k^2+2k+1{)}^2$$ are all complete squares for each $k=1,2,\dots ,n-1$, and we have $m=a_n=2n^2-1$ in this case. So, we will show that if there exists a sequence $a_1,a_2,\dots ,a_n$ satisfying the two conditions of the problem, then $m\ge 2n^2-1$ must hold. To do this it is enough to show that $a_k\ge 2k^2-1$ holds for each $k=1,2,\dots ,n$. For this purpose, let us first show the following lemma.

Lemma. Let $k$ be a positive integer. Then, for any pair of positive integers $x$, $y$ satisfying $2k^2-1\le x<y<2(k+1{)}^2-1$, the number $\frac{x^2+y^2}{2}$ is not a perfect square.

Proof. If $x$ and $y$ have different even-odd parity, then the assertion of the lemma is obvious since $\frac{x^2+y^2}{2}$ is not even an integer in this case. So, let us assume that $x$ and $y$ have the same even-odd parity. Then we see that the following inequalities hold: $$\begin{array}{rl}\frac{x^2+y^2}{2}-{\left(\frac{x+y}{2}\right)}^2& ={\left(\frac{y-x}{2}\right)}^2>0,\\ y-x\le (2(k+1{)}^2-2)-(2k^2-1)& =4k+1,\\ x\ge 2k^2-1,y\ge x+2\ge 2k^2+1.& \end{array}$$ Since $y-x$ is an even number, the second inequality above can be sharpened to $y-x\le 4k$. Consequently, we have $$\begin{gathered} {\left(\frac{x+y}{2}+1\right)}^2-\frac{x^2+y^2}{2}=x+y+1-{\left(\frac{y-x}{2}\right)}^2 \\ \ge (2k^2-1)+(2k^2+1)+1-(2k{)}^2=1>0. \end{gathered}$$ We can thus conclude that $${\left(\frac{x+y}{2}\right)}^2<\frac{x^2+y^2}{2}<{\left(\frac{x+y}{2}+1\right)}^2.$$ This shows that $\frac{x^2+y^2}{2}$ lies strictly in between two adjacent perfect squares, and therefore, it cannot be a perfect square, proving the assertion of the Lemma.

Let us now show the assertion that $a_k\ge 2k^2-1$ holds for each $k=1,2,\dots ,n$, using induction on $k$. The assertion is obvious for $k=1$. So, suppose $a_l\ge 2l^2-1$ is satisfied for a positive integer $l$. If we have $a_{l+1}<2(l+1{)}^2-1$, then by taking $x=a_l$ and $y=a_{l+1}$ in the Lemma, we get a contradiction to the fact that $\frac{a_l^2+a_{l+1}^2}{2}$ is a perfect square. Thus we must have $a_{l+1}\ge 2(l+1{)}^2-1$, completing the induction. Therefore, we have $a_k\ge 2k^2-1$ for each $k=1,2,\dots ,n$, and in particular, $m=a_n\ge 2n^2-1$. This shows that the minimum value of $m$ we seek is $2n^2-1$.