Sum of difference moduli vs. sum of modulus differences

Question

This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself.

Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, define a real $f_k\left(x_1,x_2,...,x_n\right)$ as the sum

$\sum\limits_{T\subseteq\left\lbrace 1,2,...,n\right\rbrace ;\\ \ \left|T\right|=k} \left|\sum\limits_{t\in T}x_t - \sum\limits_{t\in\left\lbrace 1,2,...,n\right\rbrace \setminus T} x_t\right|$.

We mostly care about the case of $n$ even and $k=\frac n 2$; in this case, $f_k\left(x_1,x_2,...,x_n\right)$ is a kind of measure for the dispersion of the reals $x_1$, $x_2$, ..., $x_n$ (more precisely, of their $\frac n 2$-element sums).

Now my conjecture is that if $n$ is even and $k=\frac n 2$, then

$f_k\left(x_1,x_2,...,x_n\right)\geq f_k\left(\left|x_1\right|,\left|x_2\right|,...,\left|x_n\right|\right)$

for any reals $x_1$, $x_2$, ..., $x_n$.

I think I have casebashed this for $n=4$ and maybe $n=6$; I don't remember anymore - it's too long ago. Sorry. I still have no idea what to do in the general case, although my attempts at big-$n$ counterexamples weren't of much success either.

Answer 1

Hi, Darij!

This is actually quite simple (and also much more appropriate for AoPS than for MO). The idea is to show that for every $t$, the expression $\sum_T|t+D_T|$, where $D_T$ is your difference, goes down if you replace all $x_k$ by their absolute values ($t=0$ is your claim). The base $n=2$ is rather trivial and boils down to the inequality $|t-a|+|t+a|=2\max(|t|,|a|)\ge 2\max(|t|,|b|)=|t-b|+|t+b|$ when $|a|\ge |b|$. Now, assume that we know the statement for $n$ and want to show it for $n+2$. The trick is to choose a random pair of indices $i,j$ and notice that the full sum is just the average over such choices of $\sum_T(|t+x_i-x_j+D_T|+|t+x_j-x_i+D_T|)$ where $T$ runs over all $n/2$ element subsets of the set of remaining indices. Now, applying the statement with $n=2$ for fixed $T$, we see that we can replace $x_i$ and $x_j$ with their absolute values and our sum (with fixed $i,j$) will go down in each term. After that, we replace everything else by the absolute values using the induction assumption and, again, the sum will go down. But now we are completely done: we showed that for each fixed $i,j$, the sum goes down when we replace everything by the absolute value, so it is true after averaging as well.

The whole thing is just a textbook case of the "inventor's paradox". Strange that you haven't figured it out...