I wonder they have copied the problem from Iranian first TST 2006 Just look at this Problem We know that $\sum_{i,j}|x_i+x_j|\geq n\sum_{i=1}^{n}|x_i|$. So $2\sum_{i<j}|x_i+x_j|+2\sum_{i=1}^{n}|x_i|\geq n\sum_{i=1}^{n}|x_i|$, and everything is done. And easily equality is done iff $n$ is even and half of the numbers are $k$ and the other half are eqaul to $-k$. Also the solution is easy suppose $r$ of the numbers are positive and $n-r$ of them are negative then with the inequality $|x|+|y|\geq |x+y|$ everything is done.

Omid Hatami wrote: I wonder they have copied the problem from Iranian first TST 2006 Actually it wasn't copied. It was suggested from another problem (which might be the same with the one suggested in the Iranian TST). For those wondering: no, this is not from the ISL 2005

Valentin I think it was suggested by my problem with complex numbers.

Cezar Lupu wrote: Valentin I think it was suggested by my problem with complex numbers. I'm not sure, but I think it was not from your problem, but rather from another problem given at Putnam ...

Ok. I see. I thought it was inspired from my problem, because I haven't seen it in shortlist.

In the Iranian TST problem was designed by Mohsen Jamali (designer of problem 6 IMO 2004) which hes aid he got this problem from an analytic problem.

bump for a full solution

We'll prove the equivalent inequality $\sum_{1\leq i, j\leq n} |x_i+x_j|\geq n\sum\limits_{i=1}^{n} |x_i|$ instead by induction on $n$. The base cases are trivial, and for the induction step, fix $x_1$ to $x_{n-1}$ and set $x_n=x$ as a variable. We're interested in finding the minimum of the function: \[f(x) = 2\sum\limits_{i=1}^{n-1} |x+x_i| - (n-2)|x|.\]Notice that $f$ is a piecewise linear function and $\lim_{x\to -\infty} f(x)=\lim_{x\to +\infty} f(x) =+\infty$. Hence we're looking for a global minimum that must occur at a point where at least one of the moduli is zero. Indeed, assume that this is not the case and a minimum value is only achieved when all of the moduli are nonzero. Then consider the changes $x\to x+\epsilon$ and $x\to x-\epsilon$ for small enough $\epsilon$ such that none of the expressions change their sign. Then $f(x+\epsilon)+f(x-\epsilon)=2f(x)$, but as $f(y)\geq f(x)$ for all $y\in\mathbb{R}$, this implies that $f(x+\epsilon)=f(x-\epsilon)=f(x)$. We may now pick the $\epsilon$ with smallest $|\epsilon|$, such that one of the expressions $x+x_i\pm\epsilon$, $x\pm \epsilon$ becomes zero, and all other expressions keep their sign, which would result in an analogous minimum value, but this time we've guaranteed one of the expressions in the moduli is zero. This implies that either $x_n=0$, in which case we proceed by induction on the remaining variables, or $x_n+x_i=0$ for some $1\leq i\leq n-1$. In the second case, let $x_n=x$, $x_{n-1}=-x$, and use the induction hypothesis for $x_1, x_2, \ldots, x_{n-2}$. After subtracting $4|x|$ and dividing by $2$ we want to show: \[\sum\limits_{i=1}^{n-2} |x_i+x|+|x_i-x| \geq (n-2)|x|+\sum\limits_{i=1}^{n-2} |x_i|.\]However, for every index $i$, clearly $|x_i+x|+|x_i-x|\geq |x|+|x_i|$ as $|x|+|x_i|=|x_i+x|$ or $|x|+|x_i|=|x_i-x|$ depending on the signs of the variables, so we're done.

Here is also an alternative solution: Arrange the numbers $x_1, x_2,\ldots, x_n$ as: \[a_1\leq a_2\leq \ldots \leq a_r\leq 0 \leq b_1 \leq b_2\leq \ldots \leq b_p\]where $r+p=n$ and $r\geq p$. (If $r < p$, replace each number with its negative). Also let $A=|a_1|+ |a_2| + \ldots + |a_r|$ and $B = |b_1| + |b_2] + \ldots + |b_p|$. Then the inequality is equivalent to\begin{align*} &\sum\limits_{1\leq i,j\leq n} |x_i+x_j| \geq n\sum\limits_{i=1}^{n} |x_i| \\ \iff & 2rA+2pB+2\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{p} |a_i+b_j|\geq (r+p)(A+B) \\ \iff & 2\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{p} |a_i+b_j|\geq (r-p)(B-A). \end{align*}Assume that $B \geq A$ as otherwise there's nothing to prove and notice that from the triangle inequality, $|b_j + a_i| \geq |b_j| - |a_i|$. Summing over $i$ for a fixed $j$ yields \[\sum\limits_{i=1}^{r} |b_j+ a_i|\geq r|b_j|- A.\]Now summing these over $j$ implies that \[\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{p} |a_i+b_j|\geq rB-pA.\]What remains to be shown is that \[2(rB-pA)\geq (r-p)(B-A)\iff rA+pB+rB\geq 3pA\]which is obvious as $r\geq p\geq 0$ and $B\geq A\geq 0$, so $rA\geq pA$, $pB\geq pA$, and $rB\geq pA$.

Let $X$ and $Y$ be two iid discrete random variables, each of which takes values $x_1,x_2,\dots,x_n$ with probability $1/n$. The problem, in fact, says that $$E[|X+Y|]\ge E[|X|].$$Actually, this is true for any two iid random variables, not necessary discrete. Here is why. From $|x+y|+|x-y|\ge 2\max(|x|,|y|)\ge |x|+|y|$ we get $$E[|X+Y|+|X-Y|]\ge E[|X|]+E[|Y|]=2E[|X|].$$Therefore $$E[|X+Y|]+E[|X-Y|]\ge 2E[|X|].$$Now, it's known that $$E[|X+Y|]\ge E[|X-Y|]$$for any two iid random variables - here is a nice mathoverflow entry or also here. This finally yields, $$E[|X+Y|]\ge E[|X|].$$