# An intriguing distance-like invariant

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?

• math.stackexchange.com/questions/2574639/… May 30, 2018 at 8:57
• @ChristianF Ah nice. Interesting that someone had noticed that property before, but still without connection with another combinatorial problem. Jun 4, 2018 at 21:20

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$.