How to solve this problem ???

We're trying to maximize $$C_n=\sum_{i=1}^{n}(a_i-b_i)^2=\sum_{i=1}^{2n}i^2-2\sum_{i=1}^{n}a_ib_i=\frac{2n(2n+1)(4n+1)}{6}-2\sum_{i=1}^{n}a_ib_i$$, so we need to minimize $S:=\sum_{i=1}^{n}a_ib_i$. Lemma. The minimum of $S$ is achieved when none of the pairs $(a_i,b_i)$ are both greater than $n$. Proof. Assume not, then there are four numbers $i,j,k,l \in \{1,2,3,\dots,n\}$ such that $(n+i)(n+j)+lk$ appears in $S$, but we can replace these numbers with $(n+i)l+(n+j)k$ and decrease $S$ because $(n+i)(n+j-l)\geq k(n+j-l)$. $\blacksquare$ So, we can let $A=\{1,2,\dots ,n\}$ and $B=\{n+1,n+2,\dots ,2n\}$ and by rearrangement inequality we get that $$S\geq \sum_{i=1}^{n} i(2n+1-i)=\frac{n(n+1)(2n+1)}{3}$$. Hence, we have $C_n=\frac{2n(2n+1)(4n+1)}{6}-2S\leq \frac{n(2n+1)(2n-1)}{3}$.

I don't quite understand. We have to find the maximum value of the sum for each partition and then the smallest of those, don't we?

XbenX wrote: We're trying to maximize $$C_n=\sum_{i=1}^{n}(a_i-b_i)^2=\sum_{i=1}^{2n}i^2-2\sum_{i=1}^{n}a_ib_i=\frac{2n(2n+1)(4n+1)}{6}-2\sum_{i=1}^{n}a_ib_i$$, so we need to minimize $S:=\sum_{i=1}^{n}a_ib_i$. Lemma. The minimum of $S$ is achieved when none of the pairs $(a_i,b_i)$ are both greater than $n$. Proof. Assume not, then there are four numbers $i,j,k,l \in \{1,2,3,\dots,n\}$ such that $(n+i)(n+j)+lk$ appears in $S$, but we can replace these numbers with $(n+i)l+(n+j)k$ and decrease $S$ because $(n+i)(n+j-l)\geq k(n+j-l)$. $\blacksquare$ So, we can let $A=\{1,2,\dots ,n\}$ and $B=\{n+1,n+2,\dots ,2n\}$ and by rearrangement inequality we get that $$S\geq \sum_{i=1}^{n} i(2n+1-i)=\frac{n(n+1)(2n+1)}{3}$$. Hence, we have $C_n=\frac{2n(2n+1)(4n+1)}{6}-2S\leq \frac{n(2n+1)(2n-1)}{3}$. Oh，you did it in a wrong place ，you need to find where S max is，not the miniment。But your method is right ，and i think the ture result is n。

$n$ is even: $\frac{13n^{3}-4n}{12}$ $n$ is odd: $\frac{13n^{3}-n}{12}$

I don't know the time when the sum is minimized.

use karamata ineq.

Consruction: if n=2k+1,take A={1,2,...,k,3k+2,...,4k+2} and B={k+1,...,3k+1} if n=2k,take A={1,...,k,3k+1,...,4k} and B={k+1,...,3k} Proof: let c(k)=|a(k)-b(k)|，rearrange c(k) as d1≥d2≥...≥dn if n=2k+1,we can prove that {dk}＞{3k+1,3k,...,k+1} if n=2k,we have {dk}＞{3k-1,3k-1,3k-3,3k-3,...,k+1,k+1} (nontrivial but not hard)

I don't know why there isn't any full solution for this great problem! Nice and elegant integer inequality from 2019 RMMSL. XD Let $s_i = a_i + b_i$. Since $\sum{a_i^2} + \sum{b_i^2}$ is constant, we only need to find the maximum value of $\sum_{i = 1}^{n} a_ib_i$ where $A$ and $B$ are partitions of $[2n]$, and $|A| = |B| = n$. This is simply maximizing $\sum_{i = 1}^{n} s_i^2$. We claim that $|s_i - s_j| \le n$ for any $i < j$ both in the set $\{ 1, 2, \cdots, n\}$. This is because $|s_i - s_j| = |a_i - a_j + b_i - b_j|$. As $a_i \ge a_1 + i - 1$ and $a_j \le a_n - n + j$, we have $a_i - a_j \ge a_1 - a_n + (n-1) + (i - j)$. Also, $b_i - b_j \ge j - i$. Therefore, we have that $|s_i - s_j| \le n$. Now, we forget about our original definition of $s_i$, and just focus on the fact that $s_i$ are integers that satisfies $|s_i - s_j| \le n$ with $\sum_{i = 1}^{n} s_i = n(2n+1)$. As $|s_i - s_j| \le n$, we can set an integer $t$ so that $s_i \in [t, t+n]$ for any $i$. As the function $x \mapsto x^2$ is convex, we can force for some $s_i < s_j$, changing $(s_i, s_j)$ into $(s_i - 1, s_j + 1)$ makes the value $\sum_{i = 1}^{n} s_i^2$ larger. If there are two $i, j$ such that $a < s_i < s_j < a+n$, then we can force $s_i = a$ or $s_j = a+n$ so that the sum gets larger. Hence, we can see that only one value can lie in the interval $(t, t+n)$. The remaining job is just tedious calculation, which I will omit. Now, we proved that (I actually did the calculation) $\sum s_i^2$ is maximized when the sequence of $s_i$ consists of $\lfloor n/2 \rfloor$ number of $\left \lfloor \dfrac{3n}{2} \right \rfloor$ and $\lceil n/2 \rceil$ number of $\left \lceil \dfrac{5n}{2} \right \rceil$. Then, we can easily construct $A$ and $B$ so that $s_i$ becomes the prementioned sequence. Hence, we can calculate $C_n$, which turns out to be$$\sum_{i=1}^{n}{(a_i - b_i)^2} \ge \dfrac{2n(2n+1)(4n+1)}{3} - \left \lfloor \dfrac{n}{2} \right \rfloor \cdot \left \lfloor \dfrac{3n}{2} \right \rfloor^2 - \left \lceil \dfrac{n}{2} \right \rceil \cdot \left \lceil \dfrac{5n}{2} \right \rceil^2$$