Oh of course Well assume $ x_1\ge x_2\ge \dots \ge x_n$ and $ X\ge Y$, then make an induction : if the inequality is true for $ m - 1$, then we can prove for $ x = x_1 + x_2$ the following statement, which will solve our problem in matter of fact: $ X\sum_{j = 1}^{n} |x - y_j| - Y\sum_{i = 3}^{m} |x - x_i|\le X\sum_{j = 1}^{n} (|x_1 - y_j| + |x_2 - y_j|) -$ $ Y\left(\sum_{i = 3}^{m} (|x_1 - x_i| + |x_2 - x_i|) + |x_1 - x_2|\right)$ (*). First $ LHS = X\sum_{j = 1}^{n} |x - y_j| - Y\sum_{i = 3}^{m} |x - x_i| = \sum_{j = 1}^{n}\sum_{i = 1}^{m} x_i|x - y_j| - \sum_{j = 1}^{n}\sum_{i = 3}^{m} y_j|x - x_j|$ $ RHS = X\sum_{j = 1}^{n} (|x_1 - y_j| + |x_2 - y_j|) -$ $ Y\left(\sum_{i = 3}^{m} (|x_1 - x_i| + |x_2 - x_i|) + |x_1 - x_2|\right) = \sum_{j = 1}^{n}\sum_{i = 1}^{m} (x_i|x_1 - y_j| + x_i|x_2 - y_j|)$ $ - \sum_{j = 1}^{n}\sum_{i = 3}^{m}\left(y_j|x_1 - x_i| + y_j|x_2 - x_i|) + y_j|x_1 - x_2|\right)$ and now using the inequality $ |xx_i - y_jx_i| - |y_jx - y_jx_i|\le$ $ x_i|x_1 - y_j| + x_i|x_2 - y_j| - y_j|x_1 - x_i| - y_j|x_2 - x_i|$ which follows by verifying all cases - $ x_1\ge x_2\ge y_j \cup x\ge y_j$ etc. , we will take what we need. $ \Rightarrow 2XY \sum_{i = 1}^m\sum_{j = 1}^n|x_i - y_j|$ $ - X^2 \sum_{i = 1}^n\sum_{j = 1}^n|y_i - y_j| - Y^2 \sum_{i = 1}^m\sum_{j = 1}^m|x_i - x_j|\ge$ $ 2XY \sum_{i = 2}^m\sum_{j = 1}^n|x'_i - y_j| - X^2 \sum_{i = 1}^n\sum_{j = 1}^n|y_i - y_j| - Y^2 \sum_{i = 2}^m\sum_{j = 1}^m|x'_i - x'_j|\ge 0$ by (*), where $ x'_2 = x_1 + x_2$ and $ x'_i = x_i$ for $ i\ge 3$...

Could you please show us where we can find $ \sum y_j |x_1-x_2|$?

Please ignore the previous post!

This is the shortest proof(not mine) for the hard problem I have to say this brilliant approach is owed to the official solution for a TST problem from Poland

Attachments:

hxy09 wrote: This is the shortest proof(not mine) for the hard problem I have to say this brilliant approach is owed to the official solution for a TST problem from Poland So this problem is from a Poland TST? If so, can you tell me which year? By the way, the solution you posted is very nice !

Well not all of us can be a genius who comes up with above brilliant approach... Relax the condition in the problem statement such that the $x_{i}$ and $y_{j}$ are nonnegative real numbers. Let $P(x_1, x_2, \cdots, x_m, y_1, y_2, \cdots, y_n)$ denote the desired inequality. Let $A = \sum_{i = 1}^{m}\sum_{j = 1}^{n}|x_{i} - y_{j}|$, $B = \sum_{j = 1}^{n}\sum_{l = 1}^{n}|y_{i} - y_{l}|$, and $C = \sum_{i = 1}^{m}\sum_{k = 1}^{m}|x_{i} - x_{k}|$. We will write $(x)$ and $(y)$ to denote the numbers $x_1, x_2, \cdots, x_m$ and $y_1, y_2, \cdots, y_n$ respectively. Notice that if $m = 0$ or $n=0$, the LHS and the RHS of the desired inequality are both equal to zero. In what follows, we induct on $m+n$. Lemma 1. If $x_m = 0$, we can delete $x_m$ to yield an equivalent desired inequality. In other words, $P(x_1, x_2, \cdots, x_m, y_1, y_2, \cdots, y_n)$ is implied by $P(x_1, x_2, \cdots, x_{m-1}, y_1, y_2, \cdots, y_n)$ if $x_m = 0$. Proof. Note that $P(x_1, x_2, \cdots, x_{m-1},y_1, y_2, \cdots, y_n)$ is the following: \[2XY(A-Y) \ge X^2B+Y^2(C-2X).\]This is easily seen to be equivalent to $2XYA \ge X^2B + Y^2C$. $\blacksquare$ Time for the key idea of the proof. Lemma 2. Suppose there are $d \ge 3$ distinct values present among the numbers $(x),(y)$. Then we can find nonnegative reals $x_1', x_2', \cdots, x_m', y_1', y_2', \cdots, y_n'$ (henceforth abbreviated $(x'), (y')$) such that either there are at most $d-1$ distinct values present among them, or at least one of them is equal to zero, and such that $P((x'),(y'))$ implies $P((x),(y))$. Proof. Let $a<b<c$ be three distinct values present among the numbers $(x),(y)$. Let $r_1, s_1$ denote the number of times $a$ appears among $(x)$, respectively $(y)$. Define $r_2, s_2, r_3, s_3$ similarly using $b$ and $c$ respectively. Partition $(x)$ into four disjoint multisets $(x)^a, (x)^b, (x)^c, (x)^0$ such that $(x)^a, (x)^b, (x)^c$ contains those $x_i$ which are equal to $a$, $b$, $c$ respectively. The set $(x)^0$ contains those $x_i$ which are not equal to any of $a,b,c$. Partition $(y)$ into four sets $(y)^a, (y)^b, (y)^c, (y)^0$ similarly. It is possible to find real numbers $u,v,w$, not all zero, such that $r_1u+r_2v+r_3w = s_1u+s_2v+s_3w = 0$. Now we fix a real number $\epsilon$ and define the set $(x')^a$ to be equal to $(x)^a + u\epsilon$; i.e. the multiset consisting of every element of $(x)^a$ increased by $u\epsilon$. Define $(x')^b, (x')^c$ similarly using $v$ and $w$. Finally take $(x')$ as the multiset consisting of $(x')^a, (x')^b, (x')^c, (x)^0$. We can let $(x')$ consist of numbers $x_1', x_2', \cdots, x_m'$, with the same labeling as the $x_i$'s. (For each $x_i$, its index $i$ follows it through the partitioning process and then through the recombining process.) Define $(y')$ and the $y_j'$'s similarly. The punch line is that the inequality $P((x'),(y'))$ is linear in $\epsilon$, as long as the relative ordering of all the $x_i$ and $y_j$ is the same as the relative ordering of all the $x_i'$ and $y_j'$. Indeed, $X,Y$ are constant with respect to $\epsilon$ because we chose $r_1u + r_2v + r_3w = s_1u + s_2v + s_3w = 0$. Furthermore, $A,B,C$ behave like linear combinations of the $x_i'$ and $y_j'$, so the LHS and RHS of $P((x'),(y'))$ are both linear functions in $\epsilon$. Hence we can smooth $\epsilon$ to one of its extremes in order to obtain a tighter inequality. $\epsilon$ reaches an extremum precisely when one of the $x_i'$ or $y_j'$ is equal to zero, or when $(xy')^a, (xy')^b, (xy')^c, (xy)^0$ are no longer disjoint. (Here $(xy')^a$ means the multiset consisting of the elements of $(x')^a$ and also the elements of $(y')^a$.) $\blacksquare$ By repeatedly applying Lemma 2, and by repeatedly deleting any $x_i$ or $y_j$ that is equal to zero, it suffices to prove $P((x),(y))$ where there are at most two distinct values present among the numbers $(x), (y)$. (We already took care of the case $m = 0$ or $n = 0$.) If there is only one value present among the numbers $(x), (y)$, then all the $x_i$ and $y_j$ are equal. Hence $A = B = C = 0$ and $P((x),(y))$ is trivially true. Assume that $a<b$ are the values present among the numbers $(x), (y)$, and let $r_1, r_2$ be the number of indices $i$ such that $x_i = a$, respectively $x_i = b$. Define $s_1, s_2$ similarly. We calculate $X = r_1a + r_2b$, $Y = s_1a + s_2b$, and $A = (r_1s_2 + r_2s_1)(b-a)$, $B = 2s_1s_2(b-a)$, $C = 2r_1r_2(b-a)$. Our inequality $P$ becomes $XY(r_1s_2 + r_2s_1) \ge X^2s_1s_2 + Y^2r_1r_2$, which factors as \[0 \ge (Xs_1 - Yr_1)(Xs_2 - Yr_2).\]This rewrites as \[0 \ge (b(r_2s_1-r_1s_2))(a(r_1s_2 - r_2s_1)),\]which is obviously true. $\blacksquare$