# pigeonhole principle [closed]

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.

• 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
• Use double backslashes with curly braces, that should do the trick. – user10891 Apr 20 '11 at 18:54
• It's called Proizvolov's identity, in case you wish to google. – darij grinberg Apr 20 '11 at 21:09
• This is a puzzle, what is it doing here? Should be on math.stackexchange, not mathoverflow. – Gerry Myerson Apr 21 '11 at 0:20

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$.

• 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
• $\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

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.