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

Now we have some $n$ of the number from the set $\{1,2,...,2n\}$ colored red and the rest of them are colored blue. Say $a_1<a_2<...<a_n$ are red and $b_1>b_2>...>b_n$ are blue. Prove that the value of the expression $$E=|a_1-b_1|+|a_2-b_2|+...+|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 $$E = (n+1)+(n+2)+...+(2n) -1-2-...-n = n+n+...n = n^2$$ 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.

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

• This is a comment, not a solution! – Ehsan M. Kermani Nov 3 '17 at 20:35
• Is it, perhaps some comment is more than pure solution. – Aqua Nov 3 '17 at 20:39

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.

• I do understand case 1 but i don't follow the case 2. Could you elaborate it? – Aqua Nov 5 '17 at 8:17
• @JohnWatson I rephrased case 2, if that helps. – Ehsan M. Kermani Nov 5 '17 at 21:19