See http://en.wikipedia.org/wiki/Proizvolov%27s_identity

If $a_{i}\leq n$ then $a_{i}-b_{i}<0$ Proof: Let $a_{i}-b_{i}>0$ $b_{i}$ is bigger then $n-i$ integers $ b_{i}>b_{i+1}>...>b_{n} $ $a_{i}$ is bigger then $i$ integers $ a_{1}<...a_{i}<a_{i} $ And there are no integer which are the same. So $a_{i}-b_{i}>n-i+i=n$ which means $a_{i}>n$ Contradiction. We can prove that $a_{i}-b_{i}>0$ if $b_{i}\leq n$. The same way. So $W= |a_{1}-b_{1}|+|a_{2}-b_{2}|+...+|a_{n}-b_{n}|=\frac{((n+1)+2n)n}{2}-\frac{n(n+1)}{2}=n^2$

. So $W= |a_{1}-b_{1}|+|a_{2}-b_{2}|+...+|a_{n}-b_{n}|=\frac{((n+1)+2n)n}{2}-\frac{n(n+1)}{2}=n^2$[/quote][/quote] ?????????cant understand

Indeed the "proof" above (on top of some benign typos) does not hit the essential point; it fails to give a way to evaluate those absolute values expressions, because in principle we may have both $a_i,b_i$ on the same side of $n$, and it offers no way to evaluate that difference. In fact, if $a_i \leq n$ we may say more than just $b_i>a_i$, to wit, that $b_i > n$. This is because otherwise there will be at least $i$ of the $a$'s and $n-i+1$ of the $b$'s, in total $i + (n-i+1) = n+1$ distinct positive integers of values at most $n$, absurd. Similarly, if $b_i\leq n$ it follows $a_i > n$. Now each absolute value expression may be evaluated - it is the difference between a number greater than $n$ and one at most $n$, so $W$ evaluates to $\sum_{k=n+1}^{2n} k - \sum_{k=1}^n k = n^2$. See a detailed proof (and a Java applet) at http://www.cut-the-knot.org/Curriculum/Games/ProizvolovGame.shtml.

thanks for the link

RaleD wrote: Numbers $1,2, ..., 2n$ are partitioned into two sequences $a_1<a_2<...<a_n$ and $b_1>b_2>...>b_n$. Prove that number \[W= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\] is a perfect square. other solution. we have $\left| {x + y} \right| + \left| {x - y} \right| = 2\max \left\{ {x,y} \right\}$ $ \Rightarrow {\rm{W}} = \sum\limits_{i = 1}^n {2\max \left\{ {{a_i};{b_i}} \right\}} - \left( {\sum\limits_{k = 1}^{2n} k } \right)$ Next we prove $\max \left\{ {{a_i};{b_i}} \right\} > n$ Indeed, we have if $\exists i \in \left\{ {1,2,...,n} \right\}:\max \left\{ {{a_i};{b_i}} \right\} \le n \Rightarrow {a_1} < {a_2} < ... < {a_i} \le n,\,n \ge {b_i} > ... > {b_n}$ but $\left| {\left\{ {i|i \in Z,1 \le i \le n} \right\}} \right| = n$ so $\max \left\{ {{a_i};{b_i}} \right\} > n\Rightarrow {\rm{W}} = \sum\limits_{j = n + 1}^{2n} {2j} - \sum\limits_{i = 1}^{2n} i = {n^2}$

RaleD wrote: Numbers $1,2, ..., 2n$ are partitioned into two sequences $a_1<a_2<...<a_n$ and $b_1>b_2>...>b_n$. Prove that number \[W= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\] is a perfect square. Claim: Atleast one of the $a_i,b_i \ge n+1$ and the other one is $ \le n$ . The proof of this is simple (Just do a contradiction) Now , we make two sets $A$ and $B$ such that $A = \{n+1,n+2 \cdots 2n \} $ and $B = \{1,2,\cdots , n \}$ or $A$ . Now , $|a_i - b_i| = \max{a_i,b_i} - \min{a_i,b_i}$ . From the claim, $\max{a_i,b_i} \ge n+1$ and $\min{a_i,b_i} \le n$ Thus $\sum |a_i-b_i| = \sum \max{a_i,b_i} - \sum \min{a_i,b_i} = S(A)-S(B)$ where $S(X)$ denote sum of elements of set $X$ . Thus $\sum |a_i-b_i| = \frac{2n(2n+1)}{2} - 2 \cdot \frac{n(n+1)}{2} = n^2 \Box$

Let $A = \{a_1,a_2,\dots,a_n\}$ and $B = \{b_1,b_2,\dots,b_n\}$. We define "swap" as interchanging elements from $A$ to $B$ or vice versa such that the sum $W$ stays the same and if $a_i$ and $b_j$ are interchanged then the ordering of the elements still holds. We claim that the list of following moves will gives us our desired result. WLOG, let $a_1 = 1$, then consider the following: $\bullet$ Let $a_2 = i$, then $i - 1 \in B$. Let, $b_j = i-1$, then note that if we interchange $a_2$ and $b_j$, the ordering still holds and the sum remains the same. That is, swap is preserved. Let the new sequence after this swap be $A'=\{a'_1,a'_2,\dots,a'_n\}$ and similar for $B'$ too. Note that after performing swap, the new $a_2$ is reduced by $1$. Similarly we can swap $i - 1$ and $i - 2$ and so on until $a'_2 = 2$ $\bullet$ Repeat this until, $a'_3 = 3, a'_4 = 4$ and so on until $a'_n = n$. Due to ordering, $b'_1 = 2n, b'_2 = 2n-1$ and so on until $b'_n = n+1$. Ergo, as swap preserves the sum, we know \[W= |a'_1-b'_1|+|a'_2-b'_2|+...+|a'_n-b'_n| =|1-2n| + |2 - 2n+1|+\dots+|n-n-1| = 1 + 3 + 5 + \dots + 2n-1 = n^2\]. as desired.

Hi, I tried really hard and I was so close to solving this problem! I made the claim that swapping two elements from $A$ and $B$ does not change $W$, but I couldn't prove it. To prove this, @above states: Quote: Note that if we interchange $a_2$ and $b_j$, the ordering still holds and the sum remains the same. That is, swap is preserved. This is just stating it and doesn't really prove it. Could someone please give a formal proof of this?