Let $x_1, ..., x_n$ ($n \ge 2$) be real numbers from the interval $[1, 2]$. Prove that $|x_1 - x_2| + ... + |x_n - x_1| \le \frac{2}{3}(x_1 + ... + x_n)$, with equality holding if and only if $n$ is even and the $n$-tuple $(x_1, x_2, ..., x_{n - 1}, x_n)$ is equal to $(1, 2, ..., 1, 2)$ or $(2, 1, ..., 2, 1)$.
Problem
Source: 2020 Macedonian National Olympiad
Tags: algebra, Inequality, absolute value, interval
31.08.2020 19:39
Solution 1: If we assume that for some $i \in$ {$1, ..., n$}, $x_i \ge x_{i + 1}$ (assuming the opposite yields the same result), then $|x_i - x_{i + 1}| \le \frac{1}{3}(x_i + x_{i + 1})$ is equivalent to $2x_{i + 1} \ge x_i$, which holds based on the interval bounds (as $LHS \ge 2 \cdot 1 = 2 \ge RHS$). Summing this for all $i \in {1, ..., n}$ yields the desired result, with equality holding for an even $n$ and for said $n$-tuples. Solution 2: Let $x_{n + 1} = x_1$. Let $(x_{i_1}, ..., x_{i_n})$ be a permutation of $(x_1, ..., x_n)$ such that $x_{i_1} \ge ... \ge x_{i_n}$. We can represent the $LHS$ as $q_1 \cdot x_1 + ... + q_n \cdot x_n$ where $q_i \in$ {$-2, 0, 2$} and $\sum\limits_{i=1}^n q_i = 0$ (if for some $i \in$ {$1, ..., n$}, $x_i = x_{i + 1}$, then we can arbitrarily choose whether to write $|x_i - x_{i + 1}|$ as $x_i - x_{i +1}$ or as $x_{i + 1} - x_i$). It is easy to check that the $LHS$ attains a maximum for $n = 2k$ when $q_{i_1}, ..., q_{i_k} = 2$ and $q_{i_{k + 1}}, ..., q_{i_n} = -2$, in which case we are left to prove that $2 \cdot \sum\limits_{j= k + 1}^n q_{i_j} \ge \sum\limits_{j=1}^k q_{i_j}$, which follows from the interval bounds (same as in the first solution), and a short discussion about how the coefficients in front of $x_i$ are obtained yields the desired equality case. If $n = 2k + 1$, then at least one coefficient must be zero for the sum to be zero, and it is easy to check that the maximum value for $LHS$ is obtained when $q_{i_1}, ..., q_{i_k} = 2$, $q_{i_{k + 1}} = 0$ and $q_{i_{k + 2}}, ..., q_{i_n} = -2$, in which case we are left to prove that $\frac{1}{2} \cdot x_{i_{k + 1}} + 2 \cdot \sum\limits_{j= k + 2}^n q_{i_j} \ge \sum\limits_{j=1}^k q_{i_j}$, which holds as proven in the case when $n = 2k$, with equality never being obtained due to the fact that $x_{i_{k + 1}} > 0$.