The numbers from 1 to 2n are separated into two lists of n numbers each, A and B; elements are ordered so a₁<a₂<...<a_n and b₁>b₂>...>b_n.

How much is |a₁-b₁|+|a₂-b₂|+...+|a_n-b_n|?

First, consider |a-b|
It is equal to a-b or b-a depending on which is bigger.

Next, consider the set of integers from 1 to 2n.  We can divide these numbers into two sets, the set from 1 to n, and the set from n+1 to 2n.  Call the first set X, and the second set Y.

When we divide the whole set into set A and B, the number of X's elements in A will be equal to the number of Y's elements in B, and vice versa.  A will be ordered such that all X's elements come first, and B will be ordered such that all Y's elements come first.  The result is that each X is matched with a Y, and each Y with an X when comparing the ordered sets A and B.

Example:
A: X,X,X,X,Y,Y
B: Y,Y,Y,Y,X,X

Since all Y are greater than all X, the evaluation of |a₁-b₁|+|a₂-b₂|+...+|a_n-b_n| is equal to the sum of all the elements in Y minus all the elements in X.

A quick calculation shows that this is equal to nē.

Calculations, if you're interested:
let f(x)=x(x+1)/2 (the sum of all integers 1 to x)
|a₁-b₁|+|a₂-b₂|+...+|a_n-b_n| = f(2n) - 2f(n)
 = n(2n+1) - n(n+1)
 = n(2n+1-n-1)
 = nē

Posted by Tristan on 2005-07-12 23:05:07