4
$\begingroup$

Let $a_1<a_2<\dots<a_n, \ b_1>b_2>\dots>b_n$ and $\{a_1, \dots,a_n, b_1,..,b_n\}=\{1,2,\dots, 2n\}$. Show that $$\sum \limits_{i=1}^{n}|a_i-b_i|=n^2.$$

This nice problem from problem solving seminar of MIT.

Hint: Pigeonhole principle.

It would be interesting to look at the solution.

$\endgroup$
5
$\begingroup$

Here is a possible proof.

Note that:

$$\forall i=1,..,n$$

$$a_i\in[1,n]\implies b_i\geq n+1$$

$$a_i\geq n+1\implies b_i\leq n$$

Indeed, suppose that $a_i,b_i\in[1,n]$ thus we have:

  • $i$ numbers $\leq a_i$
  • $n-i+1$ numbers $\leq b_i$

then there are:

  • $i+n-i+1=n+1$ "pigeons" for "n" holes that's a contradiction.

In a similar way we can show that it can't be that $a_i,b_i\in [n+1,2n]$.

Therefore:

$$\sum \limits_{i=1}^{n}|a_i-b_i|=n+1+n+2+...+2n-(1+2+...+n)=n+n+...+n=n^2\quad \square$$

$\endgroup$
  • $\begingroup$ Everything is fine but how did you get that the last sum is equal to $n+1+n+2+\dots+2n-(1+2+\dots+n)$ ? $\endgroup$ – ZFR Dec 20 '17 at 17:52
  • $\begingroup$ By pigeonhole you show that $a_i $and $b_i$ can't be simutanously in $(1,n)$ or $(n+1,2n)$ thus $\sum |a_i-b_i|=(n+1)+(n+2)+...2n-(1+2+...+n)$ $\endgroup$ – gimusi Dec 20 '17 at 17:57
  • $\begingroup$ by $(1,n)$ you mean $\{1,2,\dots,n\}$? $\endgroup$ – ZFR Dec 20 '17 at 18:00
  • 1
    $\begingroup$ @RFZ yes of course! $\endgroup$ – gimusi Dec 20 '17 at 18:01
  • 1
    $\begingroup$ I got your solution! I will mark it as the best answer and +1! Thanks a lot :) $\endgroup$ – ZFR Dec 20 '17 at 18:05
4
$\begingroup$

Let $$E =\sum \limits_{i=1}^{n}|a_i-b_i|$$

For every $k$ we have $$a_{k+1}-a_k >0 >b_{k+1}-b_k$$ so $$ a_{k+1}-b_{k+1}> a_k-b_k$$

If each $a_k-b_k >0$ then we have $a_i = n+i$ and $b_i = i$ for each $i$ so $E = n^2$

If each $a_k-b_k <0$ then we have $b_i = n+i$ and $a_i = i$ for each $i$ so $E = n^2$

Now suppose there is $k$ such that $a_i-b_i <0$ for each $i\leq k$ and $a_i-b_i > 0$ for each $i>k$. Then $$\{a_1,a_2,...a_k,b_{k+1},...,b_n\}= \{1,2,...,n\}$$ and $$\{b_1,b_2,...b_k,a_{k+1},...,a_n\}= \{n+1,n+2,...,2n\}$$ so $$ E=(b_1-a_1) +...(b_k-a_k)+(a_{k+1}-b_{k+1})+...+(a_n-b_n)=n^2$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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