China National Team Selection Test

Proof Let $|{\alpha }_k|={\max }_{1\le i\le n}|{\alpha }_i|$. It is sufficient to prove that $$\underset{(k_1,\dots ,k_n)\in S_n}{\max }\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|=\underset{1\le i<j\le n}{\max }|x_j-x_i|=B,$$ $$|{\alpha }_n-{\alpha }_1|=\underset{1\le i<j\le n}{\max }|{\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{array}{rl}\underset{(k_1,\dots ,k_n)\in S_n}{\max }\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|.\end{array}\text{\hspace{1em}(1)}$$ Now suppose $|{\alpha }_n-{\alpha }_1|=x|{\alpha }_k|$. Using the Triangle Inequality, we obtain $0\le x\le 2$. So (1) becomes $$\underset{(k_1,\dots ,k_n)\in S_n}{\max }\left|\sum _{i=1}^n{x}_{k_i}{\alpha }_i\right|\ge \frac{1}{2}Bx|{\alpha }_k|.\text{\hspace{1em}(2)}$$ On the other hand, consider the vectors $${\gamma }_1=x_1{\alpha }_1+x_2{\alpha }_2+\cdots +x_{n-1}{\alpha }_{n-1}+x_n{\alpha }_n$$ $${\gamma }_2=x_2{\alpha }_1+x_3{\alpha }_2+\cdots +x_n{\alpha }_{n-1}+x_1{\alpha }_n$$ $${\gamma }_n=x_n{\alpha }_1+x_1{\alpha }_2+\cdots +x_{n-2}{\alpha }_{n-1}+x_{n-1}{\alpha }_n.$$ Then we have $$\begin{array}{rl}\underset{(k_1,\dots ,k_n)\in S_n}{\max }\left|\sum _{i=1}^n{x}_{k_i}{\alpha }_i\right|& \ge \underset{1\le i\le n}{\max }|{\gamma }_i|\\ & \ge \frac{1}{n}(|{\gamma }_1|+\cdots +|{\gamma }_n|)\\ & \ge \frac{1}{n}|{\gamma }_1+\cdots +{\gamma }_n|\\ & =\frac{A}{n}|{\alpha }_1+\cdots +{\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|.\stackrel{◯}{3}\end{array}$$ From (2) and (3), it follows that $$\begin{array}{rl}\underset{(k_1,\dots ,k_n)\in S_n}{\max }\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{array}$$