Balkan Mathematical Olympiad Shortlist

Denote $S = (a_1 - a_2)^2 + (a_3 - a_4)^2 + \dots + (a_{2n-1} - a_{2n})^2$. We have
$$\begin{aligned} S &= \sum_{i=1}^{2n} i^2 - 2(a_1a_2 + a_3a_4 + \dots + a_{2n-1}a_{2n}) \\ &= \frac{n(2n+1)(4n+1)}{3} - 2(a_1a_2 + a_3a_4 + \dots + a_{2n-1}a_{2n}). \end{aligned}$$
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 < \dots < a_{2j-1} \le n$ and $a_{2n} < a_{2n-2} < \dots < 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_1a_2 + a_3a_4 + \dots + a_{2n-1}a_{2n}$ has form $1 \cdot b_1 + 2 \cdot b_2 + \dots + 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 < \dots < b_n$. Therefore,
$$a_1a_2+a_3a_4+\dots+a_{2n-1}a_{2n} \le 1(n+1)+2(n+2)+\dots+n \cdot 2n = n \cdot \frac{n(n+1)}{2} + \frac{n(n+1)(2n+1)}{6}. \quad (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. \quad (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$.