Pigeonhole principle in finite sequence

Question

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.

Answer 1

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

Answer 2

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