I recently came across the following property while setting up problems for a discrete mathematics course. It is not too hard to prove it by induction, but I am wondering whether there is more to it - that is, a somewhat deeper reason why this holds.
Take the set of integers from $1$ to $2n$ and split it into two disjoint subsets $A$ and $A^c$ of equal size $n$.
Then, consider the distance $|M_A-m_{A^c}|$ between $A$'s largest element $M_A$ and ${A^c}$'s smallest element $m_{A^c}$. Remove $M_A$ and $m_{A^c}$ from $A$ and ${A^c}$ respectively and iterate until both sets are empty.
Fact: The sum of all distances thus computed is equal to $n^2$, regardless of the choice of $A$.
Example:
$n=3$, $A=\left\lbrace 1,4,5 \right\rbrace$, $A^c=\left\lbrace 2,3,6 \right\rbrace$
$$|5-2|+|4-3|+|1-6|=9=3^2.$$
Question(s): are there deeper reasons for this to hold than a mere induction? Is this related to another combinatorial problem?
Here's a non-inductive proof that I think sheds some light on what's going on.
Let $a$ denote the number of elements of $A$ which exceed $n$. Since $A$ contains exactly $n-a$ numbers which are at most $n$, the remaining $a$ numbers which are at most $n$ must lie in $A^c$.
Thus, for the first $a$ selections, the largest element of $A$ exceeds the smallest element of $A^c$, so the distance $|M_A - m_{A^c}|$ is just $M_A - m_{A^c}$. After those $a$ selections, the situation reverses: the remaining elements of $A^c$ all exceed $n$ and the remaining elements of $A$ are all at most $n$, so the distance is just $m_{A^c} - M_A$. In both cases, the contribution to the sum of the distances is $x-y$, where $x > n$ and $y \leq n$.
Therefore, the sum of the distances is always $[(n+1) + \cdots + (2n)] - [1 + 2 + \cdots + n]$, which clearly simplifies to $n^2$.