An Arbitrary sum?

[BMAD]

The first 2n positive integers are arbitrarily divided into two groups of n numbers each. The numbers in the first group are sorted in ascending order: a₁ < a₂ < ... < a_n; the numbers in the second group are sorted in descending order: b₁ > b₂ > ... > b_n.

Find, with proof, the value of the sum |a₁ − b₁| + |a₂ − b₂| + ... + |a_n − b_n|.

The table below is generated at random, in two stages. Firstly, a value of n in the range 2..20 is chosen at random. Then, n numbers in the range 1..2n are chosen at random. These numbers are sorted to form the sequence a_i; the remaining numbers are sorted to form the sequence b_i. For each i, the value |a_i − b_i| is calculated, and the sum is given.

Here are some generated random table . Use the tables to formulate a conjecture about each pair, (a_i, b_i.) Prove your conjecture, and hence find the value of the sum.

Edited April 9, 2013 by BMAD

[BMAD]

It wouldn't let me paste my random tables so here you go...

[vinay.singh84]

Pairing the two lists are in reverse order ensures that each number from the lower half is matched with a number from the upper half. That is, each pair will consist of a number (1 to n) and a number (n+1 to 2n).
As the differences are being added the end value will be

SUM(n+1 : 2n) - SUM (1 : n)

((2n/2)(2n+1) - (n/2)(n+1)) - (n/2)(n+1))

(2n/2)(2n+1) - (2)(n)(n+1)/2

(n)(2n+1) - (n)(n+1)

2n²+n - (n²+n)

2n²+n - n²-n

n²

Edited April 9, 2013 by vinay.singh84

[witzar]

Suppose {a_1, a_2, ..., a_n} contains k numbers <=n. This means that {b_1, b_2, ..., b_n} contains (n-k) numbers <=n. Sequences (a_i) and (b_i) are sorted ascending/descending, so

a_i <= n < b_i for i =1, ..., k
and
a_i > n >= b_i for i = k+1, ..., n.
Therefore
|a_i - b_i| = b_i - a_i for i=1, ..., k
and
|a_i - b_i| = a_i - b_i for i = k+1, ..., n.
This shows that
S = |a_1 - b_1| + ... + |a_n - b_n| = s_1*1 + s_2*2 + ... + s_{2n}*2n
where
s_i = -1 for i=1, ..., n
and
s_i = +1 for i=n+1, ..., 2n.
Therefore
S = -1-2-...-n + (n+1)+(n+2)+...+(n+n) = -(1+2+...+n) + n*n + (1+2+...+n) = n*n.