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.

Unread post by Zan » Fri Jun 08, 2012 8:54 pm

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.

Unread post by sourav das » Thu Jun 21, 2012 7:45 pm

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. :D
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.

Unread post by Zan » Fri Jun 22, 2012 1:06 am

Thank you for your reply. But could you explain the last conclusion, please?
My teacher is very demanding. I've got many other unsolved problems. :-D

User avatar
*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.

Unread post by *Mahi* » Fri Jun 22, 2012 9:26 pm

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$
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

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

Re: A way to sort elements of a set.

Unread post by Zan » Sat Jun 23, 2012 7:24 pm

Thanks a lot!!!!

Post Reply