Prove that the value of the expression $|a_1-b_1|+|a_2-b_2|+\dots+|a_n-b_n|$ does not depend on the coloring.

Question

Now we have some $n$ of the number from the set $\{1,2,\dots,2n\}$ colored red and the rest of them are colored blue. Say $a_1<a_2<\dots<a_n$ are red and $b_1>b_2>\dots>b_n$ are blue. Prove that the value of the expression $$ E = |a_1-b_1|+|a_2-b_2|+\dots+|a_n-b_n| $$ does not depend on the coloring.

---

All I can do is to calculate this $E$ if we take $a_i=i$ and $b_i = 2n+1-i$ for all $i\leq n$. In this case we get \begin{align} E &= (n+1)+(n+2)+\dots+(2n) -1-2-\dots-n \\ &= n+n+\dots+n = n^2 \end{align} Clearly it wants us to prove that $E$ is invariant for such colorings. Does any one has any idea how to prove it. Strong assumption is that it should be done with induction.

Answer 1

Ahh, this is what I found right now. For every $k$ we have $$a_{k+1}-a_k >0 >b_{k+1}-b_k$$ so $$ a_{k+1}-b_{k+1}> a_k-b_k$$ This should kill the problem...?

Answer 2

This is not a complete proof but I think something like this should work!

Let's prove a more general statement for any $2n$ consecutive integers $E$ doesn't depend on coloring/partitioning. Proceed by induction on $n.$ The bases cases are trivial to check. Assume that the assert holds for $\leq n-1$ no matter if we choose all $a_i$s first or $b_i$s first.

Now note that, we have either $a_1=1$ or $b_n=1.$ Also either $b_1=2n$ or $a_n=2n$

Case 1. $a_1=1$ and $b_1=2n,$ then $E$ is $(2n-1) + \sum (...)$ so by hypothesis $E$ doesn't depend on the partition.

Case 2. $a_1=1$ and $a_n=2n,$ then $E$ is $(b_1 - 1 ) + \sum (...) + (2n - b_n) = (b_1 - b_n) + (2n-1) + \sum (...).$ By hypothesis, it only remains to show that $b_1 - b_n$ doesn't depend on coloring as well. We can also assume that we have selected $a_i$s first, then $b_i$ were determined uniquely if that help!

Other two cases are similar as well.