China National Team Selection Test

Proof Let $|\alpha_k| = \max_{1 \le i \le n} |\alpha_i|$. It is sufficient to prove that
$$\max_{(k_1, \dots, k_n) \in S_n} \left| \sum_{i=1}^{n} x_{k_i} \alpha_i \right| \ge \frac{AB}{2A+B} |\alpha_k|,$$
where $S_n$ is the set of all permutations of $(1, 2, \dots, n)$.

Without loss of generality, assume
$$|x_n - x_1| = \max_{1 \le i < j \le n} |x_j - x_i| = B,$$
$$|\alpha_n - \alpha_1| = \max_{1 \le i < j \le n} |\alpha_j - \alpha_i|.$$
For the two vectors
$$\beta_1 = x_1\alpha_1 + x_2\alpha_2 + \cdots + x_{n-1}\alpha_{n-1} + x_n\alpha_n,$$
$$\beta_2 = x_n\alpha_1 + x_2\alpha_2 + \cdots + x_{n-1}\alpha_{n-1} + x_1\alpha_n,$$
we have
$$\begin{aligned} \max_{(k_1, \dots, k_n) \in S_n} \left| \sum_{i=1}^{n} x_{k_i} \alpha_i \right| & \ge \max\{|\beta_1|, |\beta_2|\} \\ & \ge \frac{1}{2} (|\beta_1| + |\beta_2|) \\ & \ge \frac{1}{2} |\beta_1 - \beta_2| \\ & = \frac{1}{2} |x_1 \alpha_n + x_n \alpha_1 - x_1 \alpha_1 - x_n \alpha_n| \\ & = \frac{1}{2} |x_1 - x_n| \cdot |\alpha_1 - \alpha_n| \\ & = \frac{1}{2} B |\alpha_n - \alpha_1|. \tag{1} \end{aligned}$$
Now suppose $|\alpha_n - \alpha_1| = x |\alpha_k|$. Using the Triangle Inequality, we obtain $0 \le x \le 2$. So (1) becomes
$$\max_{(k_1, \dots, k_n) \in S_n} \left| \sum_{i=1}^{n} x_{k_i} \alpha_i \right| \ge \frac{1}{2} B x |\alpha_k|. \tag{2}$$
On the other hand, consider the vectors
$$\gamma_1 = x_1 \alpha_1 + x_2 \alpha_2 + \dots + x_{n-1} \alpha_{n-1} + x_n \alpha_n$$
$$\gamma_2 = x_2 \alpha_1 + x_3 \alpha_2 + \dots + x_n \alpha_{n-1} + x_1 \alpha_n$$
$$\gamma_n = x_n \alpha_1 + x_1 \alpha_2 + \dots + x_{n-2} \alpha_{n-1} + x_{n-1} \alpha_n.$$
Then we have
$$\begin{aligned} \max_{(k_1, \dots, k_n) \in S_n} \left| \sum_{i=1}^n x_{k_i} \alpha_i \right| &\ge \max_{1 \le i \le n} |\gamma_i| \\ &\ge \frac{1}{n} (|\gamma_1| + \dots + |\gamma_n|) \\ &\ge \frac{1}{n} |\gamma_1 + \dots + \gamma_n| \\ &= \frac{A}{n} |\alpha_1 + \dots + \alpha_n| \\ &= \frac{A}{n} \left| n\alpha_k - \sum_{j \ne k} (\alpha_k - \alpha_j) \right| \\ &\ge \frac{A}{n} \left( n \left| \alpha_k \right| - \sum_{j \ne k} \left| \alpha_k - \alpha_j \right| \right) \\ &\ge \frac{A}{n} \left( n \left| \alpha_k \right| - (n-1) \left| \alpha_n - \alpha_1 \right| \right) \\ &= \frac{A}{n} \left( n \left| \alpha_k \right| - (n-1)x \left| \alpha_k \right| \right) \\ &= A \left( 1 - \frac{n-1}{n} x \right) |\alpha_k|. \quad \textcircled{3} \end{aligned}$$
From (2) and (3), it follows that
$$\begin{aligned} \max_{(k_1, \dots, k_n) \in S_n} \left| \sum_{i=1}^n x_{k_i} \alpha_i \right| &\ge \max\left\{\frac{Bx}{2}, A\left(1 - \frac{n-1}{n}x\right)\right\} |\alpha_k| \\ &\ge \frac{\frac{Bx}{2} \cdot A \cdot \frac{n-1}{n} + A\left(1 - \frac{n-1}{n}x\right) \cdot \frac{B}{2}}{A \cdot \frac{n-1}{n} + \frac{B}{2}} |\alpha_k| \\ &= \frac{AB}{2A + B - \frac{2A}{n}} |\alpha_k| \\ &\ge \frac{AB}{2A + B} |\alpha_k|. \end{aligned}$$