MathLabs

Problem 2

Show that the inequality ∑i=1n∑j=1n∣xi−xj∣≤∑i=1n∑j=1n∣xi+xj∣\sum_{i=1}^n\sum_{j=1}^n\sqrt{|x_i-x_j|}\le\sum_{i=1}^n\sum_{j=1}^n\sqrt{|x_i+x_j|} holds for all real numbers x1,x2,…,xnx_1,x_2,\ldots,x_n.
Step 3 of 5: FF is piecewise concave, so it is minimized at a breakpoint
Previous stepNext step
In plain words

A piecewise concave function that blows up at both ends attains its minimum at one of its finitely many breakpoints.

F(t)→∞ as ∣t∣→∞F(t)\to\infty\ \text{as } |t|\to\infty
Detailed analysis

Each term ∣xi+xj+2t∣\sqrt{|x_i+x_j+2t|} is concave on each side of its zero, so F(t)F(t) is piecewise concave with finitely many breakpoints (where some xi+xj+2t=0x_i+x_j+2t=0), and F(t)→∞F(t)\to\infty as ∣t∣→∞|t|\to\infty; on each concave piece the minimum is attained at an endpoint, so the global minimum of FF occurs at one of these breakpoints, i.e. at t=−xit=-x_i for some ii (a diagonal term j=ij=i) or t=−xi+xj2t=-\tfrac{x_i+x_j}{2} for some i≠ji\ne j.