We do a weighting trick. Let $\pi$ denote a permutation $(\pi(1), \pi(2), \dots, \pi(n))$, and let $\sum_{\pi}$ sum over all permutations of $\{1, \dots, n\}.$ Assume that $|\vec{\alpha_1}| \ge 1.$ Then it suffices to show the problem with the RHS replaced with $\frac{AB}{2A+B}.$ Consider the following equation. \[ \left(\sum_\pi |w_\pi| \right) \max_{\pi} \left| \sum_{i = 1}^n x_{\pi(i)} \vec{\alpha_i} \right| \ge \sum_{\pi} |w_{\pi}| \left| \sum_{i = 1}^n x_{\pi(i)} \vec{\alpha_i} \right| \ge \left| \sum_\pi w_\pi \sum_{i = 1}^n x_{\pi(i)} \vec{\alpha_i} \right| = \left| \sum_{i = 1}^n \vec{\alpha_i} \sum_\pi w_\pi x_{\pi(i)} \right| \]for some real weights $w_\pi$ for all permutations $\pi.$ Now choose the weights $w_{\pi}$ such that \[ \sum_\pi w_\pi x_{\pi(i)} = \begin{cases} 1 \textnormal{ if } i = 1 \\ 0 \textnormal{ otherwise} \\ \end{cases}. \]Substituting this in, we have that \[ \max_{\pi} \left| \sum_{i = 1}^n x_{\pi(i)} \vec{\alpha_i} \right| \ge \left(\sum_\pi |w_\pi| \right)^{-1}, \]so our goal is now to minimize $\sum_\pi |w_\pi|$ given the previous system of equations. My next claim is a duality claim. Let $c_1, \dots, c_n$ be real numbers. Then we know that \[ \sum_{i = 1}^n c_i \sum_\pi w_\pi x_{\pi(i)} = c_1 \implies \sum_\pi |w_\pi| \ge \frac{|c_1|}{\max_\pi \left| \sum_{i = 1}^n c_i x_{\pi(i)}\right|} . \]Essentially, by the duality of linear programming, one can show that equality holds, i.e. \[ \min \sum_\pi |w_\pi| = \max_{\substack{c_1, \dots, c_n \in \mathbb{R} \\ \sum |c_i| > 0}} \frac{|c_1|}{\max_{\pi} \left|\sum_{i = 1}^n c_i x_{\pi(i)}\right|} . \]So we have reduced it to an optimization problem on the right hand side of the equation. The denominator can be one of two things, by using the rearrangement inequality. Assume without loss of generality that $x_1 \le \dots \le x_n$, and $\sum x_i > 0.$ Also assume that $c_1 \le \dots \le c_n$, and instead we show that \[ \max_{\substack{c_1, \dots, c_n \in \mathbb{R} \\ \sum |c_i| > 0}} \frac{ \max_i |c_i|}{\max_{\pi} \left|\sum_{i = 1}^n c_i x_{\pi(i)}\right|} \le \frac{2A+B}{AB}. \]This statement has to be true, because it is the same as the original problem, except with the vectors $\alpha_i$ replaced by real numbers $c_i$! So we have strictly simplified the problem. Now, looking at the denominator, it equals \[ \max\left(\sum c_i x_i, -\sum c_i x_{n+1-i}\right), \]because $x_1 \le \dots \le x_n$ and $c_1 \le \dots \le c_n.$ Lemma 1: If $c_n > 0$ and $c_1 \le 0$, we are done. This is because \[ \sum c_i x_i-\sum c_i x_{n+1-i} = \sum_{i = 1}^{n/2} (c_{n+1-i} - c_i)(x_{n+1-i}-x_i) \ge (c_n - c_1)B \ge \max_i |c_i| B. \]Therefore, \[ \max\left(\sum c_i x_i, -\sum c_i x_{n+1-i} \right) \ge \frac{B}{2} \max_i |c_i| \ge \frac{AB}{2A+B} \max_i |c_i|, \]as desired. Lemma 2: If $0 < c_1 \le \dots \le c_n$, we are also done. It suffices to consider the case where are $c_i$ are positive by symmetry. Also assume WLOG that $c_n = 1$, so $\max_i |c_i| = 1.$ We want to show that \[ \max\left(\sum c_i x_i, -\sum c_i x_{n+1-i} \right) \ge \frac{AB}{2A+B}. \]Consider a real $0 \le d \le 1.$ Consider the sum \[ d\sum c_i x_i - (1-d) \sum c_i x_{n+1-i} = \sum c_i (dx_i - (1-d)x_{n+1-i}). \]I will show that the last expression will be at least $\frac{AB}{2A+B},$ which will finish. Note that the sequence $\{dx_1 - (1-d)x_n, dx_2 - (1-d)x_{n-1}, \dots, dx_n - (1-d)x_1\}$ is an increasing sequence. Since we have no restrictions on $c_1, \dots, c_{n-1}$ other than they are between in the range $[0, 1]$, we can smooth them to all be the same value, since we want to minimize the previous quantity. After we smooth to $c_1 = \dots = c_{n-1}$, we can then smooth all of them to equal $0$ or $1$, as the expression is linear in those variables. Therefore, \[ \sum c_i (dx_i - (1-d)x_{n+1-i}) \ge \min((2d-1)\sum x_i, dx_n - (1-d)x_1) = \min((2d-1)A, (x_1+x_n)d - x_1). \]ow we make our choice of $d$. A good choice is $2d-1 = \frac{B}{2A+B} \implies d = \frac{A+B}{2A+B}.$ Then clearly $0 \le d \le 1.$ To show that $\min((2d-1)A, (x_1+x_n)d - x_1) \ge \frac{AB}{2A+B}$, it suffices to show that \[ (x_1+x_n)\frac{A+B}{2A+B} - x_1 \ge \frac{AB}{2A+B} \]\[ \frac{A+B}{2A+B}x_n - \frac{A}{2A+B}x_1 \ge \frac{AB}{2A+B} \]\[ (A+B)x_n - Ax_1 \ge AB = A(x_n-x_1) \Leftrightarrow Bx_n \ge 0, \]which is true as we assumed that $\sum x_i > 0 \implies x_n > 0$. So we're done. Remark: There must be an easier way... I think the beginning manipulation was all fairly roundabout, so I am hoping that there is a more direct solution.

mathocean97 wrote: Essentially, by the duality of linear programming, one can show that equality holds, i.e. \[ \min \sum_\pi |w_\pi| = \max_{c_1, \dots, c_n \in \mathbb{R}} \frac{|c_1|}{\max_{\pi} \left|\sum_{i = 1}^n c_i x_{\pi(i)}\right|} . \]So we have reduced it to an optimization problem on the right hand side of the equation. The denominator can be one of two things, by using the rearrangement inequality. (Finish to come) Can you show me the last step,plz

Any other solution for this problem?

WLOG assume that $ \left | x_n - x_1 \right| = \max_{1\leq i<j\leq n} \left| x_j-x_i \right| = B, $ $ \left| \vec{\alpha_n} - \vec{\alpha_1} \right| = \max_{1\leq i<j\leq n} \left| \vec{\alpha_j} - \vec{\alpha_i} \right| $ and let \begin{align*} \vec{\beta} = x_1 \vec{\alpha_1} + x_2 \vec{\alpha_2} + \dots + x_{n-1} \vec{\alpha_{n-1}} + x_n \vec{\alpha_n} \\ \vec{\gamma} = x_n \vec{\alpha_1} + x_2 \vec{\alpha_2} + \dots + x_{n-1} \vec{\alpha_{n-1}} + x_1 \vec{\alpha_n} &. \end{align*}Then $$ \mathbf{M} = \max_{\substack{\{ k_1, \dots, k_n \} \\ = \{ 1, 2, \dots, n \}} } \left | \sum_{i=1}^{n}x_{k_i}\vec{\alpha_i} \right | \geq \frac{1}{2} \left( \left| \vec{\beta} \right| + \left| \vec{\gamma} \right| \right) \geq \frac{1}{2} \left| \vec{\gamma} - \vec{\beta} \right| = \frac{B}{2} \left| \vec{\alpha_n} - \vec{\alpha_1} \right|. $$ Let $ \left| \vec{\alpha_k} \right| = \max _{1\leq i\leq n}\left|\vec{\alpha_i} \right| $ ($ k \in \mathbb{N}, 1 \leq k \leq n $) and $ \left| \vec{\alpha_n} - \vec{\alpha_1} \right| = t \left| \vec{\alpha_k} \right| $ ($ t \in \mathbb{R}, 0 \leq t \leq 2 $), then we get $$ \mathbf{M} \geq \frac{Bt}{2} \left| \vec{\alpha_k} \right| \qquad \qquad \qquad (\dagger). $$ On the other hand, let $ \vec{\varsigma_i} = x_i \vec{\alpha_1} + x_{i+1} \vec{\alpha_2} + \dots + x_n \vec{\alpha_{n-i+1}} + x_1 \vec{\alpha_{n-i+2}}+ \dots + x_{i-1} \vec{\alpha_n}, $ then $$\mathbf{M} \geq \frac{1}{n} \sum_{i=1}^{n} \left| \vec{\varsigma_i} \right| \geq \frac{1}{n} \left| \sum_{i=1}^{n} \vec{\varsigma_i} \right| = \frac{A}{n} \left| n\vec{\alpha_k} - \sum_{j \neq k} \left( \vec{\alpha_k} - \vec{\alpha_j} \right)\right|, $$so $$ \mathbf{M} \geq \frac{A}{n} \left( n \left| \vec{\alpha_k} \right| - \sum_{j \neq k} \left| \vec{\alpha_k} - \vec{\alpha_j} \right| \right) \geq \frac{A}{n} \left( n \left| \vec{\alpha_k} \right| - \left( n-1 \right) \left| \vec{\alpha_n} - \vec{\alpha_1} \right| \right) = \left( A - \frac{\left(n-1\right) At }{n} \right) \left| \vec{\alpha_k} \right| \qquad (\ddagger). $$Combining $ (\dagger) $ and $ (\ddagger) $ we conclude that $$ \mathbf{M} \geq \max \left\{ \frac{Bt}{2}, \left( A - \frac{\left(n-1\right) At }{n} \right) \right\} \left| \vec{\alpha_k} \right| \geq \left( \frac{\frac{Bt}{2} \cdot \frac{\left(n-1\right)A}{n} + \left( A - \frac{\left(n-1\right) At }{n} \right) \cdot \frac{B}{2}}{\frac{\left(n-1\right)A}{n} + \frac{B}{2}} \right) \left| \vec{\alpha_k} \right|. $$i.e. there exists a permutation $ \left( k_1, \dots, k_n \right ) $ of the numbers $ \left(1, \dots, n \right ) $ such that $$ \left |\sum_{i=1}^{n} x_{k_i}\vec{\alpha_i}\right | \geq \frac{AB}{\frac{2\left(n-1 \right)}{n}A+B} \max_{1\leq i\leq n}\left|\vec{\alpha_i}\right|. $$