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

(In reply to thoughts by Josh70679)

I thought it read that both sequences were increasing.  To remedy, I'll solve the problem as written ;). 

I Posit that for each i, ai ¡Ü n if bi > n, and vice versa.  Suppose ai ¡Ü n.  this means there are at least i a's ¡Ü n, which in turn means there can be at most (n-i) b's ¡Ü n.  Since B is decreasing, this means bi must be > n.  Conversely, if ai > n, then there are at least (n-i+1) a's > n, which means there are at most i-1 b's > n, which forces bi ¡Ü n.

This means each (ai, bi) pair gives us the difference between one of (1, 2, ... , n) and one of (n+1, n+2, ... , 2n), so the total sum for any A and B under the given constraints is   

• n^2 = [(n+1) + (n+2) + ... + (2n)] - [1 + 2 + ... + n].

Posted by Josh70679 on 2005-07-12 17:35:37