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