Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi everyone

I saw a question on Mathoverflow asking for some applications of pigeonhole principle, among the answers I saw a problem set which was proposed by Prof. Richard Stanley and in this problem set there was a question which I am interested on it, here it is: Consider these two sequences $a_1< a_2 < \cdots < a_n$ and $b_1 >b_2 > \cdots >b_n$ such that $$\{a_1,\cdots a_n,b_1\cdots b_n\}=\{1,2,\cdots 2n\}$$ show that $$\sum_i|a_i-b_i|=n^2$$

I have no idea how to do this. Perhaps someone can give a hint? I try to consider some cases but the answer was long and boring, I think there is a nice trick.

share|improve this question
2  
This is what I would do: find a group acting transitively on these collections; find a simple set of generators; show that the sum in question is invariant under the action of the generators. –  Daniel Litt Apr 20 '11 at 17:25
    
First $b_1 > b_2 >...>b_n$ and then $a_1,...,a_n,b_1,...,b_n = 1,2...2n$. If $b_i = n+i$, as the latter suggests, then $b_i < b_{i+1}$ which seems to contradict the first requirement. I don't follow here. –  user10891 Apr 20 '11 at 18:01
1  
Use double backslashes with curly braces, that should do the trick. –  user10891 Apr 20 '11 at 18:54
9  
It's called Proizvolov's identity, in case you wish to google. –  darij grinberg Apr 20 '11 at 21:09
6  
This is a puzzle, what is it doing here? Should be on math.stackexchange, not mathoverflow. –  Gerry Myerson Apr 21 '11 at 0:20
show 3 more comments

closed as off topic by Gerry Myerson, Yemon Choi, Ryan Budney, S. Carnahan Apr 21 '11 at 5:12

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

Consider the sum $S = \sum (a_i + b_i ) + \sum |a_i - b_i|$. The first term evaluates to $n(2n+1)$. The second term is unknown. Claim: $S$ is equivalent to $2\sum_{n+1}^{2n} i = n(3n+1)$ which implies the result you want.

It is easy to see that $S$ is equivalent to twice the sum of $\sum \max(a_i,b_i)$. Using the pigeonhole principle you can show that $\max(a_i,b_i) > n$.

share|improve this answer
    
It is wonderful, very nice solution. Just let me mention, I think to prove $\sum \max(a_i,b_i)=\sum_{n+1}^{2n}i$ we need to show more than $\max(a_i,b_i)>n$. I guess we need to show when $a_i\leq n$ (respectively $b_i\leq n$) then $b_i> n$ (respectively $a_i>n$) since we want to be sure $n+1\leq l\leq 2n$ appears on $\sum \max(a_i,b_i)$. But as you mentioned pigeonhole principle ensure us that this would be the case. –  Math Apr 20 '11 at 18:44
4  
$\max(a_i,b_i)>n$ is enough. Then the sequence $\max(a_i,b_i)$ consists of different elements of $n+1,\dots,2n$, so it is a permutation of $n+1,\dots,2n$, so its sum is $n(3n+1)/2$ as claimed. Wonderful solution indeed. –  GH from MO Apr 20 '11 at 18:57
add comment

I'll expand slightly on Dan's suggestion.

Any such pair of sequences $(\{a_{i}\}, \{b_{j}\})$ can be obtained from the pair of sequences $(\{i\}, \{2n+1-j\})$ by finitely many iterations of the following operation.

For some $i$ and some $j$ with $a_{i} = k, b_{j} = k+1$, set $a_{i} = k+1, b_{j} = k$.

Now just check that the claim holds for the pair of sequences $(\{i\}, \{2n+1-j\})$, and that the operation I described leaves the sum invariant.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.