To show that $$|\sum_{i=1}^n b_ix_i|\leq\frac{x_{(n)}-x_{(1)}}{2}, \text{ where } \sum_{i=1}^n b_i = 0, \text{ and } \sum_{i=1}^n |b_i| = 1$$ where $x_{(1)}=\min{\{x_1,\cdots,x_n\}}$ and $x_{(n)}=\max{\{x_1,\cdots,x_n\}}$
Intuitively, it is clear that to maximize $|\sum_{i=1}^n b_ix_i|$ under the given restrictions, we have to assign the weight $+\frac{1}{2}$ (or $-\frac{1}{2}$) to $x_{(n)}$ and $-\frac{1}{2}$ (or $+\frac{1}{2}$) to $x_{(1)}$. But how do we show this analytically? Does Lagrangian helps here? Any help would be much appreciated. Thank you.
Applying a permutation to the sequences $\{x_i\}$ and $\{b_i\}$ we may assume that $x_1 \leq x_2 \leq ...\leq x_n$. We can re-write $\sum_{i=1}^{n} b_i x_i$ as $s_1 (x_1-x_2) +s_2(x_2 -x_3)+... +s_{n-1} (x_{n-1} -x_n) $ where $s_k=b_1+b_2+...+b_k$. ( I have used the property $\sum b_i=0$ here). It is enough now to show that $|s_k| \leq \frac 1 2$ for all $k$. Note that $\sum |b_i|=1$ implies that either $\sum_{i=1}^{k} |b_i|\leq \frac 1 2 $ or $\sum_{i=k+1}^{n} |b_i|\leq \frac 1 2 $. However, since $\sum b_i=0$ we have $s_k=b_1+b_2+...+b_k=-(b_{k+1}+...+b_n)$. It follows that $|s_k| \leq \frac 1 2$.