10
$\begingroup$

Start with the set of integers from $1$ up to $2n$, where $n$ is a natural number. Split this set into two disjoint subsets of equal size, say $\{a_1<a_2<\cdots<a_n\}$ and $\{b_1>b_2>\cdots>b_n\}$ (with the elements ordered WLOG). What is the value of the following expression in terms of $n$? $$|a_1-b_1|+|a_2-b_2|+\cdots+|a_n-b_n|$$


Source (link contains spoilers)

$\endgroup$
6
  • 1
    $\begingroup$ I don't think ordering the elements is WLOG. $\endgroup$ Commented Jan 2, 2022 at 14:14
  • 3
    $\begingroup$ @justforplaylists It's not WLOG for the final expression, of course, but it is WLOG for defining the sets: i.e. we define $a_1$ to be the smallest element, $a_2$ the next smallest, and so on. $\endgroup$ Commented Jan 2, 2022 at 14:16
  • $\begingroup$ Two disjoint and exhaustive subsets? If $n=10$, we could have $\{1,2\}$ and $\{19,20\}$, which gives $36$, or $\{1,2\}$ and $\{3,4\}$, which gives $2$. $\endgroup$ Commented Jan 3, 2022 at 5:40
  • 1
    $\begingroup$ I was trying to think of a more precise term than "split", and reading the answers I was reminded of the word "partition", which more clearly indicates exhaustion. $\endgroup$ Commented Jan 3, 2022 at 6:10
  • 2
    $\begingroup$ @Randal'Thor This is not WLOG but rather you are defining $a_i$ and $b_i$ in this way. $\endgroup$
    – WhatsUp
    Commented Jan 3, 2022 at 7:14

4 Answers 4

6
$\begingroup$

Jaap Sherpuis's comment hints at a perhaps more intuitive explanation.

We need to consider how many a's are $\le n$ and how many b's are $\gt n$.

Let's name $k$ the number of $a_i$'s that are $\le n$.
$a_1 \dots a_k$ occupy $k$ values from 1 to n, leaving $(n-k)$ holes.
These holes are filled by $(n-k)$ of the $b_j$'s. The remaining $b_j$ are $\gt n$.

So we have $a_1 \dots a_k \le n$ and $a_{k+1} \dots a_n \gt n$.
And we have $b_1 \dots b_k \gt n$ and $b_{k+1} \dots b_n \le n$.
This implies $a_i < b_i$ if and only if $i \le k$

From there we can compute

$|a_1-b_1|+|a_2-b_2|+\cdots+|a_n-b_n|$
$= |a_1-b_1|+\cdots+|a_k-b_k|+|a_{k+1}-b_{k+1}|+\cdots+|a_n-b_n|$
$= (b_1-a_1)+\cdots+(b_k-a_k)+(a_{k+1}-b_{k+1})+\cdots+(a_n-b_n)$

On the plus side you have all values $\gt n$ and on the minus side the values $\le n$
So the expression becomes:
$ = (n+1) + \cdots + 2n - (1 + \cdots + n) = n^2$

$\endgroup$
12
$\begingroup$

This is just an "optimised" version of Gareth's answer which I couldn't resist making. Please keep upvoting him and also prefer his answer over mine for acceptance.

For any index $i$ let us denote $M_i$ the larger of $a_i,b_i$ and $m_i$ the smaller. Then the given sum of absolute differences can be rewritten as

$\displaystyle\sum_i M_i - \sum_i m_i$

We will now prove that for any pair of indices $i,j$ we have $M_i>m_j$:

Proof:

Case 1, $i=j$: obvious from definition
Case 2, $i<j$: $M_i\ge b_i>b_j\ge m_j$
Case 3, $i>j$: $M_i\ge a_i>a_j\ge m_j$

It follows that all the $m_i$ are smaller than all the $M_i$. This is the same as saying

the $m_i$ must be a permutation of $1,...,n$ and the $M_i$ a permutation of $n+1,...,2n$

The sum is therefore

$\displaystyle\sum_{i=1}^n(n + i) -\sum_{i=1}^n i = \sum_{i=1}^n n = n^2$

and indeed independent of how the numbers are split into $a$ and $b$.

$\endgroup$
2
  • 1
    $\begingroup$ I don't think this is just an optimized version of my answer, although of course there's some overlap. And I think it's a very nice argument. I've upvoted it and would encourage anyone reading this to do likewise. (And if Rand chooses to accept this one rather than mine, then despite loopy walt's first sentence I think that would be an extremely reasonable decision.) $\endgroup$
    – Gareth McCaughan
    Commented Jan 2, 2022 at 20:14
  • $\begingroup$ There is a related principle used in some magic tricks. If you have one suit of cards in order Ace to King, and another suit in reverse order King to Ace, and combine those two piles using a single riffle shuffle, then the top thirteen cards will contain every card value exactly once, as will the bottom thirteen cards. $\endgroup$ Commented Jan 3, 2022 at 8:55
10
$\begingroup$

So, first of all, let's

do it one way and see what sum we get. Let the $a$s be (in order) $1,2,\ldots,n$ and the $b$s be (in order) $2n,2n-1,\ldots,n+1$. Then the differences are, in order, $2n-1,2n-3,\ldots,1$ whose sum is $n^2$.

In view of

the title, presumably this is always the answer.

But why? I offer first a rather routine, prosaic solution, the sort of thing someone who's done this sort of thing before knows they will be able to get to work. (This is the first solution I found.) Then something slicker. (This is the second solution I found.) Then a way to streamline the second part of the slicker argument. And then a way to streamline the first part, found not by me but by user loopy walt in comments. I prefer to leave all these things in, rather than just presenting the slickest version so far found, because that's a more honest representation of how things typically work in mathematics; see also this related 3blue1brown video about calculation versus slick insight.

Here is a prosaic solution; I suspect there is something better (and am thinking about that). We can turn any valid partition into any other by repeatedly performing operations of the form "find two consecutive numbers one of which is an $a$ and the other a $b$, and swap them". What happens when we do this? Suppose $a_i$ and $b_j$ are consecutive. Then none of the other order relations change when we switch them, so our new sequences in order are the same as the old except that $a_i'=b_j$ and $b_j'=a_i$. If $i=j$ then the expression we're interested in doesn't change at all. Otherwise, say that $i<j$. Then $b_j \simeq a_i<a_j$ where $\simeq$ means "differ by 1", and therefore $a_j>b_j$; and $a_i\simeq b_j<b_i$, and therefore $a_i<b_i$. So increasing $a_i$ by 1 and decreasing $b_j$ by 1 reduces $|a_i-b_i|$ by 1 and increases $a_j-b_j$ by 1, and vice versa if instead we decrease $a_i$ and increase $b_j$. In either case our expression doesn't change.

OK, now let's see if we can do something simpler.

We have all these intervals from $a_i$ to $b_i$. Every number $k$ from $1$ to $2n$ is an endpoint of exactly one of these intervals; I claim that the first $n$ are all left endpoints and the last $n$ are all right endpoints. Why? Well, colour all the $a$s amber and all the $b$s blue; suppose $k$ is amber; if $k=a_i$ then there are $i-1$ amber numbers to its left, hence $k-i$ blue numbers to its left, hence $n-k+i$ blue numbers to its right, the first of which is $b_{n-k+i}$. So $b_i$ is right of $a_i$ iff $i\leq n-k+i$, iff $k\leq n$. Likewise if $k$ is blue.

And now

our sum is just the sum over all $k$ of the number of these intervals it's in (counting 1/2 when it's exactly at an endpoint), which depends only on the number of left and right endpoints on either side of $k$, and we've just seen that this never changes.

Or (a basically-equivalent replacement for the foregoing paragraph):

our sum is just the sum of all the right endpoints minus the sum of all the left endpoints, which is to say $\bigl[(n+1)+\cdots+2n\bigr]-\bigl[1+\cdots+n\bigr]=n^2$.

This is definitely slicker than the first proof above, but I would be unsurprised to find that one can streamline things further.

In comments, loopy walt suggests another way to do the first bit:

i.e., proving that $1,...,n$ are left endpoints and $n+1,...,2n$ are right endpoints. Consider the interval whose endpoints are $a_i,b_i$. We'll prove that its right-hand endpoint is $>n$. Note that $a_i$ is bigger than $i-1$ smaller $a$s, and $b_i$ is bigger than $n-i$ smaller $b$s. So whichever of them is larger is bigger than the other one (1), and $i-1$ smaller $a$s, and $n-i$ smaller $b$s, all of those sets being disjoint; hence bigger than at least $1+i-1+n-i=n$ other numbers; hence it's $>n$.

(To my mind this is neater than my argument but more rabbit-out-of-hat-ish.)

$\endgroup$
6
  • $\begingroup$ Correct answer and reasonable proof, but there's a(nother) surprising fact that makes the proof even simpler. $\endgroup$ Commented Jan 2, 2022 at 14:27
  • $\begingroup$ As mentioned in the answer, I am currently looking for slicker proofs and have some plausible ideas of where to look. There is something of an analogy with a famous question about coins, but that pathway doesn't seem like it really produces something much simpler so far. $\endgroup$
    – Gareth McCaughan
    Commented Jan 2, 2022 at 14:29
  • $\begingroup$ How about: ai is larger than i-1 elements (a1,...,a{i-1}), bi is larger than n-i elements (b{i+1},...,bn). The larger of ai and bi is larger than the other one and both these sets, that is 1 + i-1 + n-i elements. $\endgroup$
    – loopy walt
    Commented Jan 2, 2022 at 15:30
  • $\begingroup$ ... and possibly other things too, but at least n elements, which means that all the right endpoints are >= n+1, and as there are n right endpoints that tells us what they all are? Yeah, that works. $\endgroup$
    – Gareth McCaughan
    Commented Jan 2, 2022 at 15:34
  • $\begingroup$ The last spoilertag is the kind of argument I was thinking of. Nice example of a surprising non-obvious mathematical fact. $\endgroup$ Commented Jan 2, 2022 at 17:48
4
$\begingroup$

This problem doesn't really have anything to do with the integers from 1 to 2n. Fix any set consisting of 2n real numbers (repetitions allowed); then split them into a_1 <= a_2 <= .... <= a_n and b_1 >= b_2 >= ... >= b_n. Then the sum |a_1 - b_1| + |a_2 - b_2| + ... + |a_n - b_n| is constant, that is, it doesn't depend on the partition.

$\endgroup$
3
  • $\begingroup$ Nice generalisation, and I suppose the same proof works in this case too, but can you edit your answer to include a quick proof of this fact? $\endgroup$ Commented Jan 3, 2022 at 4:48
  • $\begingroup$ @Randal'Thor Since the loopy walt's answer (up to the words "It follows that all the $m_i$ are smaller than all the $M_i$") does not use the fact that the numbers given are integers from 1 to 2n, if we replace $1\leqslant2\leqslant\dots\leqslant2n$ with any numbers $q_1\leqslant q_2\leqslant\dots\leqslant q_{2n}$, the assertion about the constant sum still holds (and it will be equal $\sum_{i=1}^n q_{n+i} - \sum_{i=1}^n q_i$). $\endgroup$
    – trolley813
    Commented Jan 3, 2022 at 6:47
  • 1
    $\begingroup$ @trolley813 I know how the proof would go, I'm just asking pmw to include it so that this answer is self-contained. $\endgroup$ Commented Jan 3, 2022 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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