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

the sum is somehere between n and n^2, depending on the sequences A and B.  n is the minimum, since ai and bi must differ by at least 1 each.  And n^2 is the maximum because the condition on A and B both inreasing means ai and bi can differ by at most n. 

Posted by Josh70679 on 2005-07-12 16:51:52