For $n=2$ it is like: $|a+b| \geq 2(|a| + |b|)$ or (because I don't know how should I understand the sum on the left side) $2|a+b| \geq 2(|a| + |b)$ Both of these inequalities are not true.

For $n=2$ we have $|a+a|+|a+b|+|b+a|+|b+b| \geq 2(|a|+|b|)$ - you should take all permutations.

Oh, sorry.

Everything I can say is that : It's very nice problem.

Hungkhtn,I can prove the orginal inequality for $n=3,4$ and $3(\sum_{1 \leq i<j \leq n}|x_{i}+x_{j}|)\geq (n-1)\sum_{i=1}^n|x_{i}|$,but it's weaker than the orginal problem,so i can't solve this.Please Hungkhtn or Nima Ahmadi Pour,can youpost your solution?Thanks so much

My own solution is rather complicated, but I know there are other solutions that are simpler. Anyway here is my solution: We use induction on $n$. Easily we can verify that if $x_i=0$ for some $i$ then the result can be derived from case $n-1$. Now we will show that if $x_i=-x_j$ for some $i$ and $j$ then the result can be derived from the case $n-2$. First observer a small lemma: Lemma : $|x-y|+|x+y|\geq |x|+|y|$ Proof : By triangle inequality we have $|x-y|+|x+y|\geq 2|x|$ and $|x-y|+|x+y|\geq 2|y|$. Adding these two and dividing by two we get the result. Now suppose that $x_1=-x_2$. Now by lemma we have the following inequalities: \[ |x_1+x_i|+|x_2+x_i|\geq |x_1|+|x_i| (3\leq i\leq n) \] \[ |x_i+x_1|+|x_i+x_2|\geq |x_2|+|x_i| (3\leq i\leq n) \] And we obviously have : \[ |x_1+x_2|=0 , |x_2+x_1|=0 , |x_1+x_1|=2|x_1| , |x_2+x_2|=2|x_2| \] And from the induction hypothesis for $n-2$ we have : \[ \sum_{i,j=3}^n |x_i+x_j|\geq (n-2)\sum_{i=3}^n |x_i| \] By adding all the above inequalities/equalities we have \[ \sum_{i,j=1}^n |x_i+x_j|\geq n\sum_{i=1}^n |x_i| \] which is what we wanted. Now we may assume that no $x_i$ is zero and for no $i,j$ we have $x_i+x_j=0$. Now take the function $f$ to be $\sum_{i,j=1}^n |x_i+x_j|-n\sum_{i=1}^n |x_i|$. Now assume that we add some $x_i$ a small value $\epsilon$. Then some terms in $f$ will increase by $\epsilon$ and some will decrease and some do not change. (Count the term $|x_i+x_i|$ twice) But since we have that no term in $f$ is zero, if rather than increasing $x_i$ by $\epsilon$ we decrease it by $\epsilon$ the terms in $f$ that were increasing will decrease and the ones that were decreasing will increase. So we can either increase $x_i$ by $\epsilon$ or decrease it such that $f$ is not increased (At this point $f$ behaves like a linear function in $x_i$) Also note that value of $\epsilon$ can be increased until one of the terms in $f$ become zero, but then value of $f$ is by the above arguments, non-negative and so we have the results. So assume that $\epsilon$ can be increased to infinity without having any of the terms become zero. But we have this propery for every $x_i$ so there is no $x_i$ between two others, that is there are $a$ of $x_i$s equal to $t$ and $b$ others equal to $s$. ($a+b=n$) Supposing that $|t|<|s|$ ,just increase the $\epsilon$ for all $x_i$s equal to $t$ until we have $|t|=|s|$ or $t=0$. But if $t=0$ then we are done. So assume $t\neq 0$. But then $t=s$, or else we have $t=-s$ which can be derived from the case $x_i+x_j=0$. But then the inequality becomes like this : \[ 2n^2|t|\geq n^2|t| \] which is obviously true.

can't we just use karamata ineq for the convex function |x|

Albanian Eagle wrote: can't we just use karamata ineq for the convex function |x| Yes, we can (But only jensen is enough) It is one of my friends simple solutions (I told you before, others solutions are simpler). If we make the negative $x_i$s to become equal to their arithmetic mean, by jensen the left side will decrease, and the right side obviously doesn't change. So we do this for the negative ones, and then for the positive ones. Then the ineqality becomes in four varianles and it can be easily solved by hand.

My idea is the following: Use $|a_i+a_j|+|a_i-a_j|=2max(|a_i|,|a_j|)$, then we have to demonstrate $2\sum_{i,j=1}^n max(|a_i|,|a_j|)\geq n\sum |a_i|+\sum_{i,j=1}^n |a_i-a_j|$ Divide $a_i$ in two groups: $u$ numbers are positive, $v$ numbers are negative, $u+v=n$. Positive numbers we redenote $S^+_u\geq S^+_{u-1}\geq...\geq S^+_1\geq 0$ (arranging in order) Negative numbers we redenote $S^-_v\geq S^-_{v-1}\geq...\geq S^-_1\geq 0$ (arranging in order by modulo rule - inversing their sign). And also they are arranged as $S_n \geq S_{n-1}\geq ... \geq S_1\geq 0$ (full notation). It will be clear in futher steps. $\sum_{i,j=1}^n max(|a_i|,|a_j|)=2nS_n+(2n-2)S_{n-1}+...+2S_1$ $n\sum |a_i|=n(S_n+S_{n-1}+...+S_1)$ $\sum_{i,j=1}^n |a_i-a_j|=2v\sum_{i=1}^uS^+_i+2u\sum_{j=1}^vS^-_j+$ $+(2uS^+_u+2(u-2)S^+_{u-1}+...+(-2u)S^+_1)+(2vS^-_v+2(v-2)S^-_{v-1}+...+(-2v)S^-_1)$. (Last step considering combinations positive with negative, positive with positive, negative with negative numbers) Thus we have to prove: $4(nS_n+...+S_1)\geq n(S_n+...+S_1)+((2v+2u)S^+_u+(2v+2(u-2))S^+_{u-1}+...+(2v-2u)S^+_1)+((2u+2v)S^-_v+(2u+2(v-2))S^-_{v-1}+...+(2u-2v)S^-_1)$ $4(nS_n+(n-1)S_{n-1}+...+S_1)\geq 3nS^+_u+(3n-4)S^+_{u-1}+...+(n+2v-2u)S^+_1+3nS^-_v+(3n-4)S^-_{v-1}+...+(n+2u-2v)S^-_1$ Hence we have to prove that row $a=(4n, 4(n-1),...,4)$ is greater at least than row $b=(3n,3n,3n-4,3n-4,..., min(3n+2u-2v,3n+2v-2u))$ as the worst case. 1 case: take first $2k$ from each row: $4(n+..+n-2k+1)=4\cdot 2k\frac{n+n-2k+1}{2}=4k(2n-2k+1)$ $2(3n+(3n-4)+...+(3n-4k+4))=2k\frac{3n+3n-4k+4}{2}=2k(3n-k+1)$ and we want to prove $4k(2n-2k+1)\geq 2k(3n-2k+2)$ equaling $n\geq 2k$ - true. 2 case: take first $2k+1$ from each row: $4(n+..+(n-2k+1)+n-2k)=4\cdot 2k\frac{n+n-2k+1}{2}+4(n-2k)=4k(2n-2k+1)+4(n-2k)=4(2kn-2k^2+n-k)$ $2(3n+(3n-4)+...+(3n-4k+4)+(3n-4k))=2k\frac{3n+3n-4k+4}{2}+2(3n-4k)=2k(3n-2k+2)+2(3n-4k)=2(3kn-2k^2+3n-2k)$ wishing to demonstrate $4(2kn-2k^2+n-k))\geq 2(3kn-2k^2+3n-2k)$ equaling $n(k-1)\geq 2k^2-k$, true because of $n\geq 2k+1$ and the problem is solved.

Here's mine. I think it's too short, maybe I'm wrong, but... maybe not \[ \{a_1,a_2,...,a_n\}=\{b_1,b_2,...,b_r\}\cup \{-c_1,-c_2,...,-c_s\} \] (devide set $\{a_1,a_2,...,a_n\}$ to negative and non-negative groups). With $r+s=n,b_i \ge 0,c_j \ge 0$. Denote \[ R=\sum_{i=1}^r b_i,S=\sum_{j=1}^s c_j \] So the inequality can be rewrite as follow \[ 2\sum_{i=1}^r\sum_{j=1}^s|a_i-b_j| \ge (s-r)(R-S) \] Assume that $s \ge r$, so we can suppose that $R \ge S$. In this case, notice that \[ \sum_{i=1}^r\sum_{j=1}^s|a_i-b_j| \ge\sum_{i=1}^r(sa_i-S)=sR-rS \] So we need to prove \[ 2(sR-rS ) \ge (s-r)(R-S) \] But it's immediately true because $s \ge r$ and $R \ge S$.

Nima Ahmadi Pour wrote: Yes, we can (But only jensen is enough) How do we exactly use Jensen? Anyway, the natural idea is your first idea, with the linear functions. I couldn't solve it for $x_i+x_j=0$, so thanks. Hungkthn, I think it's $2\sum_{i=1}^r\sum_{j=1}^s|a_i-b_j| \ge (s-r)(R+S)$, but I may be wrong.

Sorry, I don't understand what $\sum_{i,j}^n |x_i+x_j|$ means. Help!

$\sum_{i,j=1}^n |x_i+x_j|$ means that the sum runs over all pairs $(i, j)$, where $i, j \in \{1, ..., n\}$.

perfect_radio wrote: Nima Ahmadi Pour wrote: Yes, we can (But only jensen is enough) How do we exactly use Jensen? Just note that $|x+a|$ is a convex function and also sum of some convex functions is also convex. So if we take out the terms on the left such that they are like $|a+b|$ where $a$ is negative and $b$ is positive then these terms can be grouped like this $\sum_{x_i\in \mathbb R^-}(|x_i+a_1|+|x_i+a_2|+\ldots+|x_i+a_k|)$. Also note that sum of other terms does not change by putting the mean of negative ones instead of them. So now by jensen its pretty simple.

Now take the function $f$ to be $\sum_{i,j=1}^n |x_i+x_j|-n\sum_{i=1}^n |x_i|$. Now assume that we add some $x_i$ a small value $\epsilon$. Then some terms in $f$ will increase by $\epsilon$ and some will decrease and some do not change. (Count the term $|x_i+x_i|$ twice) But since we have that no term in $f$ is zero, if rather than increasing $x_i$ by $\epsilon$ we decrease it by $\epsilon$ the terms in $f$ that were increasing will decrease and the ones that were decreasing will increase. So we can either increase $x_i$ by $\epsilon$ or decrease it such that $f$ is not increased (At this point $f$ behaves like a linear function in $x_i$) Also note that value of $\epsilon$ can be increased until one of the terms in $f$ become zero, but then value of $f$ is by the above arguments, non-negative and so we have the results. So assume that $\epsilon$ can be increased to infinity without having any of the terms become zero. But we have this propery for every $x_i$ so there is no $x_i$ between two others, that is there are $a$ of $x_i$s equal to $t$ and $b$ others equal to $s$. ($a+b=n$) Supposing that $|t|<|s|$ ,just increase the $\epsilon$ for all $x_i$s equal to $t$ until we have $|t|=|s|$ or $t=0$. But if $t=0$ then we are done. So assume $t\neq 0$. But then $t=s$, or else we have $t=-s$ which can be derived from the case $x_i+x_j=0$. But then the inequality becomes like this : \[ 2n^2|t|\geq n^2|t| \] which is obviously true.[/quote] Hi I have read your solution can you explain this side, I could not understand . Becaouse you have used function that I could not understand

Smth similar was give in Romanian TST. For this one. Order the numbers $a_1<a_2...<a_n$, and assume that $a_1+a_n\ge 0$. It can be shown easily that decreasing, all numbers $\ge -a_1$ until they become $-a_1$ the ineq eventually sharpens. Hence we can assume that $a_1+a_n=0$. Now use an induction hypotesis for the middle $n-2$ terms.

It was exactly the same problem xirti... Actually, our problem was far worse from an aesthetic view.

I didn't remember it very well ...So, another problem apearing in more than one country at TST....

xirti wrote: I didn't remember it very well ...So, another problem apearing in more than one country at TST.... No this is not a shortlist problem. The author (Dr. Mohsen Jamali) said it was not. I think in the post of the other similar problem (the romanian one) it is explained more. P.S. : Abdurashidjon, I don't know where you don't understand, please explain more.

I'm sorry for writing on old topic, but I've found short and elementary proof, so I want to post it. If all numbers have the same sign, inequality is trivial because $LHS=2n\sum |x_i| \ge n\sum |x_i|=RHS$. Since inequality is symmetric and it doesn't change when we invert all signs, we can wlog suppose that there exist $\frac{n}{2} \le k <n$ such that $x_1 \ge... \ge x_k \ge 0>x_{k+1} \ge ... \ge x_n$. If $a$ and $b$ have the same sign, then $|a+b|=|a|+|b|$, so we have: $\sum_{i,j=1}^{n} |x_i+x_j|= \sum_{i,j=1}^{k} |x_i+x_j| + \sum_{i,j=k+1}^{n} |x_i+x_j| + 2\sum_{i=1}^{k}\sum_{j=k+1}^{n} |x_i+x_j| \\ =2k\sum_{i=1}^{k} |x_i|+2(n-k)\sum_{i=k+1}^{n} |x_i|+ 2\sum_{i=1}^{k}\sum_{j=k+1}^{n} |x_i+x_j|$ Since $2k \ge n$, it remains to prove: $(2k-n)\sum_{i=1}^{k} |x_i|+2\sum_{i=1}^{k}\sum_{j=k+1}^{n} |x_i+x_j| \ge (2k-n)\sum_{i=k+1}^{n}|x_i|$ But using trialngle inequality for each $j=k+1,...,n$, we have: $|x_i|+|x_j+x_i| \ge |x_j| \; \; (1)$ for some $i=1,2,...,n$. Since there are $(2k-n)\cdot k$ elements in $(2k-n)\sum_{i=1}^{k} |x_i|$, and for each $j=k+1,...,n$ there are $2k$ summands of the type $|x_i+x_j|$ in $2\sum_{i=1}^{k}\sum_{j=k+1}^{n} |x_i+x_j|$, we can see that for every $j$ we can find $2n-k$ sums of the type $(1)$ on the LHS to prove last inequality. Hence, inequality is proved. $\blacksquare$

Suppose $g(n)=\sum_{i=/j=1}^{n} |x_i+x_j|-n\sum_{i=1}^{n}|x_i|$ , note what we’ve to show is, $g(n)\geq 0$ for all $n\in\mathbb N$. Now $WLOG$ suppose $0\leq x_1\leq x_2\leq x_3...\leq x_p$ and $x_{p+1}=-y_{p+1}<0,....,x_n=-y_n<0$. Also suppose $y_i\in\ [x_{f(y)},x_{f(y)+1}]$. So for a fixed $i$ that is $y_i(2f(i)-p)+(\sum x_i)-2(x_1+x_2+...x_{f(i)})$. So finally $g(n)= \sum [y_i(2f(i)-p)+(\sum x_i)-2(x_1+x_2+...x_{f(i)})]$. So, $g(n)=\sum x(n-p)-p(y_{p+1}+y_{p+2}+....y_n)+2\sum (y_if(i)-(x_1+x_2+...+x_{f(i)}))$. Now let’s keep $f(i)$’s as well as those $x$’s constant. Not consider a $y_t$ and keep others fixed. Note it’s coefficient is a fixed natural number. So depending on coefficient either $g(n)$ is increasing or not so. So certainly minimum must occur either at $y_t=x_{f(t)}$ or $y_t=x_{f(t)+1}$ , or basically say at end points. Now so basically we need to look the case where $y_i$’s are nothing but permutations of those positive $x_i$’s . Now for some $y_m=x_i$, keeping other $x_i$’s fixed we get $g(n)=(2i-1-p)x_i+c$ for some constant $c$. Now note if $i\geq \frac{p+1}{2}$ then $g(n)$ is increasing so minimum at $i=[\frac{p+1}{2}]$ similarly for other case again minimum occurs at that point. So now we can , we need to check the case all negative quantities are equal. But also similarly we would also had to check when all those positives are equal. So now problem is though for $n$ variables but among them some are $+a$ while rest are $-b$, and this is just an easy case chase, so done.

I love hungkhtn's solution best!