Partitioning the integers into two subset Let $S=\{1,2,3,4,5,...2N\}$ be the set of the first $2N$ natural numbers. Partition the set into two subsets (each subset will have $N$ elements). Arrange one subset in increasing order and the other in decreasing order. If we Sum the absolute value of the difference of two corresponding elements, the answer is $N^2$. I've read an article online about this one but now I cannot find it. Can somebody show me a link about the statement above? or can somebody show me a proof? Does anybody know a more general statement related to the above? Thanks.
 A: Let's say we have some partition $A = \{a_1, a_2,\ldots,a_N\}, B = \{b_1, b_2,\ldots,b_N\}$ with $a_i<a_{i+1}$ and $b_i > b_{i+1}$ for all $i$, and set 
$$
S = \sum_{i = 1}^N |a_i-b_i|
$$
Because the $a_i$ are increasing, and the $b_i$ are decreasing, there is a number $k$ such that $a_i<b_i$ for all $i \leq k$ and $a_i>b_i$ for all $i > k$. That means we can rewrite $S$ as
$$
S = \sum_{i = 1}^k (b_i-a_i) + \sum_{i = k+1}^N(a_i-b_i)
$$
$$
= \sum_{i = 1}^k b_i + \sum_{i = k+1}^N a_i - \left(\sum_{i = 1}^k a_i + \sum_{i = k+1}^N b_i\right)
$$
Look at the sets $B' = \{b_i \in B\mid b_i > N\}$ and $A' = \{a_i \in A\mid a_i \leq N\}$. Once you see that they have the same size, it follows that that size is $k$. This means that all terms that are greater than $N$ appears on the left (with positive sign) and all terms less than or equal to $N$ appears on the right (with negative sign), regardless of the partition.
This makes it is easy to calculate the sum, because you can arrange it like this:
$$
(N+1) - 1 + (N+2) - 2 + \cdots + 2N - N = N + N + \cdots + N = N\cdot N
$$
