Pigeonhole principle in finite sequence Let $a_1<a_2<\dots<a_n, \ b_1>b_2>\dots>b_n$ and $\{a_1, \dots,a_n, b_1,..,b_n\}=\{1,2,\dots, 2n\}$. Show that $$\sum \limits_{i=1}^{n}|a_i-b_i|=n^2.$$
This nice problem from problem solving seminar of MIT. 
Hint: Pigeonhole principle. 
It would be interesting to look at the solution.
 A: Here is a possible proof.
Note that:
$$\forall i=1,..,n$$
$$a_i\in[1,n]\implies b_i\geq n+1$$
$$a_i\geq n+1\implies b_i\leq n$$
Indeed, suppose that $a_i,b_i\in[1,n]$ thus we have:


*

*$i$ numbers $\leq a_i$

*$n-i+1$ numbers $\leq b_i$


then there are:


*

*$i+n-i+1=n+1$ "pigeons" for "n" holes that's a contradiction.


In a similar way we can show that it can't be that $a_i,b_i\in [n+1,2n]$.
Therefore:
$$\sum \limits_{i=1}^{n}|a_i-b_i|=n+1+n+2+...+2n-(1+2+...+n)=n+n+...+n=n^2\quad \square$$
A: Let $$E =\sum \limits_{i=1}^{n}|a_i-b_i|$$
For every $k$ we have $$a_{k+1}-a_k >0 >b_{k+1}-b_k$$
so $$ a_{k+1}-b_{k+1}> a_k-b_k$$
If each $a_k-b_k >0$ then we have $a_i = n+i$ and $b_i = i$ for each $i$ so $E = n^2$ 
If each $a_k-b_k <0$ then we have $b_i = n+i$ and $a_i = i$ for each $i$ so $E = n^2$ 
Now suppose there is $k$ such that $a_i-b_i <0$ for each $i\leq k$ and $a_i-b_i > 0$ for each $i>k$. Then $$\{a_1,a_2,...a_k,b_{k+1},...,b_n\}= \{1,2,...,n\}$$ and $$\{b_1,b_2,...b_k,a_{k+1},...,a_n\}= \{n+1,n+2,...,2n\}$$ so $$ E=(b_1-a_1) +...(b_k-a_k)+(a_{k+1}-b_{k+1})+...+(a_n-b_n)=n^2$$ 
