Un intrigante invariante similar a la distancia

Question

Hace poco me encontré con la siguiente propiedad mientras planteaba problemas para un curso de matemáticas discretas. No es muy difícil demostrarla por inducción, pero me pregunto si hay algo más, es decir, una razón algo más profunda por la que se cumple.

Tomemos el conjunto de enteros de $1$ à $2n$ y dividirlo en dos subconjuntos disjuntos $A$ y $A^c$ de igual tamaño $n$ .

A continuación, considere la distancia $|M_A-m_{A^c}|$ entre $A$ 's mayor elemento $M_A$ y ${A^c}$ 's el más pequeño elemento $m_{A^c}$ . Elimine $M_A$ y $m_{A^c}$ de $A$ y ${A^c}$ respectivamente e iterar hasta que ambos conjuntos estén vacíos.

Es un hecho: La suma de todas las distancias así calculadas es igual a $n^2$ independientemente de la elección de $A$ .

Ejemplo:

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

Pregunta(s): ¿hay razones más profundas para que esto se mantenga que una mera inducción? ¿Está relacionado con otro problema combinatorio?

Answer 1

He aquí una prueba no inductiva que creo que arroja algo de luz sobre lo que está pasando.

Sea $a$ denotan el número de elementos de $A$ que superan $n$ . Desde $A$ contiene exactamente $n-a$ números que sean como máximo $n$ el resto $a$ números que sean como máximo $n$ debe estar en $A^c$ .

Así, para la primera $a$ selecciones, el mayor elemento de $A$ supera el elemento más pequeño de $A^c$ por lo que la distancia $|M_A - m_{A^c}|$ es sólo $M_A - m_{A^c}$ . Después de esos $a$ selecciones, la situación se invierte: los elementos restantes de $A^c$ todos superan $n$ y el resto de elementos de $A$ son todas como máximo $n$ por lo que la distancia es $m_{A^c} - M_A$ . En ambos casos, la contribución a la suma de las distancias es $x-y$ donde $x > n$ y $y \leq n$ .

Por lo tanto, la suma de las distancias es siempre $[(n+1) + \cdots + (2n)] - [1 + 2 + \cdots + n]$ que se simplifica claramente en $n^2$ .