## A way to sort elements of a set.

For students of class 11-12 (age 16+)
Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

### A way to sort elements of a set.

Choose n numbers from the set $\{1;2;...;2n\}$ and sort them in that way: $a_1<a_2<...<a_n$ Sort the other n numbers so that $b_1>b_2>...>b_n$
Prove $|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|=n^2$

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

### Re: A way to sort elements of a set.

We claim:
$\sum_{i=1}^n |a_i-b_i|=2n+(2n-1)+....+(n+1)-n-(n-1)-(n-2)....-1=n^2$
Let $|a_i-b_i|=a_i-b_i$ for some $i$. Then $a_i>b_i>...>b_n$ and also $a_i>a_{i-1}>a_{i-2}>....>a_1$ it implies $a_i$ is greater than $(n-i+1)+(i-1)=n$ different elements from the set. It implies $a_i>n$. Thus we can prove that for $|a_i-b_i|=b_i-a_i$ that $b_i>n$ as then $b_i>a_i>a_{i-1}>...>a_1$ and $b_i>b_{i+1}>...>b_n$ same argument as before. It implies $max(a_i,b_i)>n$ hence $\sum_{i=1}^n |a_i-b_i|=(\sum_{i=n+1}^{2n} i)-(\sum_{j=1}^n j)=n^2$

done.
Cool problem Zan. Wecome to BDMO forum.
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

### Re: A way to sort elements of a set.

My teacher is very demanding. I've got many other unsolved problems.

*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

### Re: A way to sort elements of a set.

sourav das wrote:It implies $max(a_i,b_i)>n$ hence $\sum_{i=1}^n |a_i-b_i|=(\sum_{i=n+1}^{2n} i)-(\sum_{j=1}^n j)=n^2$
For each $(a_i,b_i)$ exactly one of them is greater than $n$, and thus we can say that, all of the numbers greater than $n$ has "$+$" sign, and all the numbers from $1$ to $n$ has "$-$" sign and thus the sum $\sum_{i=1}^n |a_i-b_i|$ has the value $(\sum_{i=n+1}^{2n} i)-(\sum_{j=1}^n j)=n^2$
Use $L^AT_EX$, It makes our work a lot easier!