Sum of $2n$ numbers arbitrarily grouped into $2$ groups of $n$

Question

The first $2n$ natural numbers are arbitrarily divided into $2$ groups of $n$ each. The first group (named $a$) is arranged $a_1<\ldots<a_n$. The second group ($b$) is arranged $b_1>\ldots>b_n$. Find, with proof, the sum $|a_1-b_1| + \ldots + |a_n-b_n|$. Or more compactly $$\sum_{i=1}^n |a_i-b_i|$$

(Guess: Arbitrarily means any possible group of $n$ numbers. The modulus can't be removed because any sum can be a negative number.)

Some pattern (not sure how to create a table here)

n=1, sum=1,

n=2, sum=4, diff=3

n=3, sum=9, diff=5

n=4, sum=16, diff=7

n=5, sum=25, diff=9

---

I'm not a mathematician, and am just looking for some help about to start thinking on the problem. Don't solve it (but if it is solved anywhere I appreciate the link).

Answer 1

Suppose we color the two groups of number red and green, respectively.

We can reach any distribution of colors by starting with "$1$ to $n$ red and $n+1$ to $2n$ green", and then some number of times interchange the colors of two neighboring numbers.

If you can prove that a single interchange will never change your sum-of-differences, you will have proved that the sum doesn't depend on the coloring, and that you can compute that sum from the initial color distribution.

Answer 2

Try the following approach:

1. Experiment -- you may notice that the sum of the absolute differences always seems to be n^2

2. Take the simplest case, where the first n numbers are in the first group and the second n are in the second group. Then the sum of the elements of the first group will be 1/2*n*(n+1), and the sum of the elements of the second group will be n/2*(3n+1) and the difference (which is the same as the differences of the absolute values of the ordered set as all members of the first group are less than all members of the second) is just n^2

3. Show that taking any subset of the first group as in 2 above, and swapping with any equivalent-sized subset of the second group does not alter the sum of the differences of the absolute values since the ordering always leads to the smaller ones being subtracted from larger ones, which means that all numbers end up having the same sign as in calculation 2.

Answer 3

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