7
$\begingroup$

I recently came across the following property while setting up problems for a discrete mathematics course. It is not too hard to prove it by induction, but I am wondering whether there is more to it - that is, a somewhat deeper reason why this holds.

Take the set of integers from $1$ to $2n$ and split it into two disjoint subsets $A$ and $A^c$ of equal size $n$.

Then, consider the distance $|M_A-m_{A^c}|$ between $A$'s largest element $M_A$ and ${A^c}$'s smallest element $m_{A^c}$. Remove $M_A$ and $m_{A^c}$ from $A$ and ${A^c}$ respectively and iterate until both sets are empty.

Fact: The sum of all distances thus computed is equal to $n^2$, regardless of the choice of $A$.

Example:

$n=3$, $A=\left\lbrace 1,4,5 \right\rbrace$, $A^c=\left\lbrace 2,3,6 \right\rbrace$

$$|5-2|+|4-3|+|1-6|=9=3^2.$$

Question(s): are there deeper reasons for this to hold than a mere induction? Is this related to another combinatorial problem?

$\endgroup$
2

1 Answer 1

10
$\begingroup$

Here's a non-inductive proof that I think sheds some light on what's going on.

Let $a$ denote the number of elements of $A$ which exceed $n$. Since $A$ contains exactly $n-a$ numbers which are at most $n$, the remaining $a$ numbers which are at most $n$ must lie in $A^c$.

Thus, for the first $a$ selections, the largest element of $A$ exceeds the smallest element of $A^c$, so the distance $|M_A - m_{A^c}|$ is just $M_A - m_{A^c}$. After those $a$ selections, the situation reverses: the remaining elements of $A^c$ all exceed $n$ and the remaining elements of $A$ are all at most $n$, so the distance is just $m_{A^c} - M_A$. In both cases, the contribution to the sum of the distances is $x-y$, where $x > n$ and $y \leq n$.

Therefore, the sum of the distances is always $[(n+1) + \cdots + (2n)] - [1 + 2 + \cdots + n]$, which clearly simplifies to $n^2$.

$\endgroup$
3
  • 1
    $\begingroup$ Indeed, now that I see this that is possibly all there is to it. Thanks! $\endgroup$ Jan 25, 2018 at 17:26
  • $\begingroup$ @ArnaudMortier Thanks for posting this nice problem! It was fun to think about. $\endgroup$ Jan 25, 2018 at 17:35
  • $\begingroup$ [+1] Nice solution to this interesting issue ! $\endgroup$
    – Jean Marie
    Jan 26, 2018 at 17:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .