Soma das diferenças de dos elementos de dois conjuntos

Seja M = {1, 2, 3,..., 2n}, e M_1 = {a_1, a_2, ..., a_n} e M_2 = {b1, b_2, ..., b_n} subconjuntos de M tais que a_1 < a_2 < ... < a_n e b_1 > b_2 > ... > b_n. Se M_1 U M_2 = M and M_1 Ո M_2 =  Ø, prove que |a_1 - b_1| + |a_2 - b_2| + ... +|a_n - b_n| = n^2.

Sugestões: Use o fato de que {x,y} = {max{x,y}, min{x,y}} e que |x-y| = max{x,y}-min{x,y}$.

Provemos antes que |x - y| = max{x,y} - min{x,y}.
1. Se for x > y => x - y > 0 => |x-y| = x - y e max{x,y} - min{x,y} = x - y (x>y)
2. Se for x = y, o resultado é óbvio
3. Se for x < y => |x-y| = y - x = max{x,y} - min{x,y} (y > x)

Agora comece com o caso trivial:
a(1) a(2) ... a(n-1) a(n) || b(n) b(n-1) ... b(2) b(1) (em ordem 1, 2, ..., 2n).
Eu preciso que você note existir uma divisão entre os b's e os a's bem ao meio. Todos os a's são de 1 a n e todos os b's de n+1 a 2n. Os máximos vão ser necessariamente os à direita da linha divisória => soma dos máximos é (n+1)+(n+2)+...+2n e a soma dos mínimos é 1 + 2 + ... + n.
S = (n+1)+(n+2)+...+2n - 1 - 2 - ... - n = (1 + 2 + ... + 2n) - 2(1 + 2 + ... + n) = 2n(2n+1)/2 - n(n+1) = 2n² + n - n² - n = n²

Façamos daí operações. Pra construir outros conjuntos, eu só posso alternar um a com um b adjacentes, senão eu quebraria a(x) < a(y), x < y ou b(x) > b(y), x < y. Acontece que assim fazendo quando o b(k) estiver à esquerda, a(k) estará à direita. Vamos provar essa afirmação por absurdo.
Suponha, por exemplo, que b(k) esteja à direita => b(k-1), b(k-2), ..., b(1) estão todos à direita, logo k dos n espaços estão ocupados. Se a(k) estivesse na direita também, a(k+1), a(k+2), ... a(n) todos estarão à direita, ocupando então mais n-k+1. Ao todo, do lado direito estão ocupados k+n-k+1 = n+1 espaços no mínimo, o que é absurdo, porque à direita só tem n espaços, logo a(k) e b(k) estão em lados diferentes da linha divisória. Daí a cada par a(k) com b(k), um deles é um dos n+1, n+2, ..., 2n e o outro é um dos 1, 2, ..., n, isto é, efetivamente n+1, n+2, ..., 2n vão ser máximos e 1, 2, ..., n vão ser mínimos, de forma que S simplesmente não muda.