IMO Team Selection Test

Firstly, we will prove one useful statement: Lemma. If $x_1,x_2,\dots ,x_{n-1}\in \mathbb{R}$ are such that $x_1+x_2+\cdots +x_{n-1}=0$, then $$x_1+|x_1-x_2|+|x_2-x_3|+\cdots +|x_{n-2}-x_{n-1}|+x_{n-1}\ge 0$$ (1) Proof. It is clear that if $x_1+x_{n-1}\ge 0$ the inequality (1) is true. If $x_1+x_{n-1}<0$, then there exists $i$, $2\le i\le n-2$ such that $x_i>0$. From the properties of absolute value we have $$\begin{array}{rl}& |x_1-x_2|+|x_2-x_3|+\cdots +|x_{n-2}-x_{n-1}|\ge |x_1-x_i|+|x_i-x_{n-1}|\\ & =|x_i-x_1|+|x_i-x_{n-1}|\ge x_i-x_1+x_i-x_{n-1}=2x_i-x_1-x_{n-1}\ge \\ & \ge -x_1-x_{n-1}\end{array}$$ From where (1) follows. Since there are no other cases, we get that (1) is true, which concludes the proof of the lemma.

If we now use the equality $|a-b|=a+b-2\min \{a,b\}$, the inequality (1) is equivalent to the inequality $$\begin{array}{r}{x}_1+x_1+x_2-2\min \{x_1,x_2\}+x_2+x_3-2\min \{x_2,x_3\}+\cdots +x_{n-2}+x_{n-1}-2\min \{x_{n-2},x_{n-1}\}+x_{n-1}\ge 0\\ x_1+x_2+\cdots +x_{n-1}\ge \min \{x_1,x_2\}+\min \{x_2,x_3\}+\cdots +\min \{x_{n-2},x_{n-1}\}\\ 0\ge \min \{x_1,x_2\}+\min \{x_2,x_3\}+\cdots +\min \{x_{n-2},x_{n-1}\}.\end{array}\text{\hspace{1em}(2)}$$ Now, let $x_1,x_2,\dots ,x_{n-1}\in \mathbb{R}$ be arbitrary real numbers (their sum need not be equal to 0). If we homogenize this sequence, $$x_1-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i,x_2-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i,\dots ,x_{n-1}-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i,$$ then we have $$x_1-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i+x_2-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i+\cdots +x_{n-1}-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i=\sum _{i=1}^{n-1}{x}_i-\frac{n-1}{n-1}\sum _{i=1}^{n-1}{x}_i=0.$$ Therefore, for this sequence the conditions of the lemma as well as inequality (2) are fulfilled. If we use the equality $$\min \left\{x_j-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i,x_{j+1}-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i\right\}=\min \{x_j,x_{j+1}\}-\frac{1}{n-1}\sum _{i=1}^{n-1}{x}_i,$$ and we substitute it in (2), we get the inequality $$\frac{n-2}{n-1}\sum _{i=1}^{n-1}{x}_i\ge \min \{x_1,x_2\}+\min \{x_2,x_3\}+\cdots +\min \{x_{n-2},x_{n-1}\}(3)$$ Now we return to the proof of the problem statement. Without loss of generality we can assume that $a_n=\min \{a_1,a_2,\dots ,a_{n-1},a_n\}$. If, otherwise, $a_i=\min \{a_1,a_2,\dots ,a_{n-i-1},a_n\}$ for some $i$, $1\le i\le n-1$ then we consider the sequence $b_1=a_{i+1},\dots ,b_{n-i}=a_n,b_{n-i+1}=a_{i-1},\dots ,b_n=a_i$. Therefore, if we choose $x_i=a_i$, for $i=1,2,\dots ,n-1$, by substituting in (3), we get $$\begin{array}{c}\frac{n-2}{n-1}\sum _{i=1}^{n-1}{a}_i\ge \min \{a_1,a_2\}+\min \{a_2,a_3\}+\cdots +\min \{a_{n-2},a_{n-1}\}.\text{ But from the condition }\\ a_1+a_2+\cdots +a_{n-1}=-a_n,\text{ we get}\end{array}$$ $$\frac{n-2}{n-1}{a}_n\ge \min \{a_1,a_2\}+\min \{a_2,a_3\}+\cdots +\min \{a_{n-2},a_{n-1}\}.$$ From the equalities $a_n = \min\{a_{n-1}, a_n\}$ and $a_n = \min\{a_n, a_1\}$, we get 2a_n - \frac{n-2}{n-1} a_n \geq \min\{a_1, a_2\} + \min\{a_2, a_3\} + \dots + \min\{a_{n-2}, a_{n-1}\} + \min\{a_{n-1}, a_n\} + \min\{a_n, a_1\} $$i.e.$$ \frac{n}{n-1} \min\{a_1, a_2, \dots, a_n\} \geq \min\{a_1, a_2\} + \min\{a_2, a_3\} + \dots + \min\{a_n, a_1\}, $$ Q.E.D.