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\]
A way to sort elements of a set.
-
- 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.
$\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$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
Re: A way to sort elements of a set.
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.
My teacher is very demanding. I've got many other unsolved problems.
Re: A way to sort elements of a set.
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$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$
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: A way to sort elements of a set.
Thanks a lot!!!!