Balkan Mathematical Olympiad Shortlist

Denote $S=(a_1-a_2{)}^2+(a_3-a_4{)}^2+\cdots +(a_{2n-1}-a_{2n}{)}^2$. We have $$\begin{array}{rl}S& =\sum _{i=1}^{2n}{i}^2-2(a_1{a}_2+a_3{a}_4+\cdots +a_{2n-1}{a}_{2n})\\ & =\frac{n(2n+1)(4n+1)}{3}-2(a_1{a}_2+a_3{a}_4+\cdots +a_{2n-1}{a}_{2n}).\end{array}$$ Next, observe that for each $j=1,2,\dots ,n$, one of the numbers $a_{2j-1},a_{2j}$ is greater than $n$, and the other is at most $n$. Indeed, suppose $a_{2j-1},a_{2j}\le n$. Then $a_1<a_3<\cdots <a_{2j-1}\le n$ and $a_{2n}<a_{2n-2}<\cdots <a_{2j}\le n$, yielding $j+(n-j+1)=n+1$ distinct positive integers not exceeding $n$, a contradiction. The case $a_{2j-1},a_{2j}>n$ is handled similarly. It follows that $a_1{a}_2+a_3{a}_4+\cdots +a_{2n-1}{a}_{2n}$ has form $1\cdot b_1+2\cdot b_2+\cdots +n\cdot b_n$, where $b_1,b_2,\dots ,b_n$ is some permutation of $n+1,n+2,\dots ,2n$. But it is known that such an expression will be maximal if and only if $b_1<b_2<\cdots <b_n$. Therefore, $$a_1{a}_2+a_3{a}_4+\cdots +a_{2n-1}{a}_{2n}\le 1(n+1)+2(n+2)+\cdots +n\cdot 2n=n\cdot \frac{n(n+1)}{2}+\frac{n(n+1)(2n+1)}{6}.(2)$$ From (1) and (2), we find $$S\ge \frac{n(2n+1)(4n+1)}{3}-n^2(n+1)-\frac{n(n+1)(2n+1)}{3}=n^3.(3)$$ By the above arguments, for equality to hold, there would have to exist indices $i,j,k$ (since $n\ge 3$) such that $\{a_{2i-1},a_{2i}\}=\{1,n+1\}$, $\{a_{2j-1},a_{2j}\}=\{2,n+2\}$ and $\{a_{2k-1},a_{2k}\}=\{3,n+3\}$. It is easy to check that this is impossible, given the assumptions on the permutation $a_1,a_2,\dots ,a_{2n}$. Therefore, equality cannot hold in (3) and $S>n^3$.