China Mathematical Olympiad

Proof I We need the following lemma.
Lemma For any real number $\alpha$ and positive number $n$, we have
$$\sum_{i=1}^{n-1} [i\alpha] \le \frac{n-1}{2} [n\alpha]. \qquad \textcircled{1}$$
The lemma is obtained by summing inequalities
$$[i\alpha] + [(n-i)\alpha] \le [n\alpha]$$
for $i = 1, 2, \dots, n-1$.

Return to the original problem. We will prove it by induction. For $n = 1$, it is obviously true.
Assume that for $n = k$, it is also true. Now consider $n = k + 1$. Let $a_i = x_i + \frac{2}{k}x_{i+1}$, $b_i = y_i + \frac{2}{k}y_{i+1}$ for $i = 1, 2, \dots, k$. Then we have $a_1 \le a_2 \le \dots \le a_k$, $b_1 \ge b_2 \ge \dots \ge b_k$ and $\sum_{i=1}^k ia_i = \sum_{i=1}^k ib_i$. By induction we get $\sum_{i=1}^k a_i[i\alpha] \ge \sum_{i=1}^k b_i[i\alpha]$.

In addition, $x_{k+1} \ge y_{k+1}$. Otherwise, if $x_{k+1} < y_{k+1}$, we have
$$x_1 \le x_2 \le \dots \le x_{k+1} < y_{k+1} \le \dots \le y_2 \le y_1.$$
This contradicts $\sum_{i=1}^{k+1} ix_i = \sum_{i=1}^{k+1} iy_i$. So we have
$$\begin{aligned} \sum_{i=1}^{k+1} x_i[i\alpha] - \sum_{i=1}^k a_i[i\alpha] &= x_{k+1} \left\{ \left[ (k+1)\alpha \right] - \frac{2}{k} \sum_{i=1}^k [i\alpha] \right\} \\ &\ge y_{k+1} \left\{ \left[ (k+1)\alpha \right] - \frac{2}{k} \sum_{i=1}^k [i\alpha] \right\} \\ &= \sum_{i=1}^{k+1} y_i[i\alpha] - \sum_{i=1}^k b_i[i\alpha]. \end{aligned}$$
$$\text{That means } \sum_{i=1}^{k+1} x_i[i\alpha] \ge \sum_{i=1}^{k+1} y_i[i\alpha].$$
By induction, we complete the proof for any integer $n > 0$.

Proof II Define $z_i = x_i - y_i$ for $i = 1, 2, \dots, n$, we have $z_1 \le z_2 \le \dots \le z_n$ and $\sum_{i=1}^n iz_i = 0$. We only need to prove that
$$\sum_{i=1}^{n} z_i[i\alpha] \ge 0. \qquad \textcircled{2}$$
Let $\Delta_1 = z_1, \Delta_2 = z_2 - z_1, \dots, \Delta_n = z_n - z_{n-1}$. Then $z_i = \sum_{j=1}^i \Delta_j$ ($1 \le i \le n$), and
$$0 = \sum_{i=1}^{n} iz_{i} = \sum_{i=1}^{n} i \sum_{j=1}^{i} \Delta_{j} = \sum_{j=1}^{n} \Delta_{j} \sum_{i=j}^{n} i.$$
So we have
$$\Delta_1 = - \sum_{j=2}^{n} \Delta_j \sum_{i=j}^{n} i / \sum_{i=1}^{n} i. \qquad \textcircled{3}$$
Then
$$\begin{aligned} \sum_{i=1}^{n} z_i[i\alpha] &= \sum_{i=1}^{n} [i\alpha] \sum_{j=1}^{i} \Delta_j = \sum_{j=1}^{n} \Delta_j \sum_{i=j}^{n} [i\alpha] \\ &= \sum_{j=2}^{n} \Delta_j \sum_{i=j}^{n} [i\alpha] - \sum_{j=2}^{n} \Delta_j \left( \sum_{i=j}^{n} i / \sum_{i=1}^{n} i \right) \sum_{i=1}^{n} [i\alpha] \\ &= \sum_{j=2}^{n} \Delta_j \sum_{i=j}^{n} i \cdot \left( \sum_{i=j}^{n} [i\alpha] / \sum_{i=j}^{n} i - \sum_{i=1}^{n} [i\alpha] / \sum_{i=1}^{n} i \right). \end{aligned}$$
Then, in order to prove $\textcircled{2}$ we only need to prove that for any $2 \le j \le n$, the following inequality holds
$$\sum_{i=j}^{n} [i\alpha] / \sum_{i=j}^{n} i \ge \sum_{i=1}^{n} [i\alpha] / \sum_{i=1}^{n} i. \qquad \textcircled{4}$$
But
$$\begin{aligned} \textcircled{4} & \Leftrightarrow \sum_{i=j}^{n} [i\alpha] / \sum_{i=j}^{n} i \ge \sum_{i=1}^{j-1} [i\alpha] / \sum_{i=1}^{j-1} i \\ & \Leftrightarrow \sum_{i=1}^{n} [i\alpha] / \sum_{i=1}^{n} i \ge \sum_{i=1}^{j-1} [i\alpha] / \sum_{i=1}^{j-1} i. \end{aligned}$$
Then we only need to prove, for any $k \ge 1$,
$$\sum_{i=1}^{k+1} [i\alpha] / \sum_{i=1}^{k+1} i \ge \sum_{i=1}^{k} [i\alpha] / \sum_{i=1}^{k} i,$$
that is equivalent to prove
$$\begin{aligned} & [(k+1)\alpha] \cdot k/2 \ge \sum_{i=1}^{k} [i\alpha] \\ & \Leftrightarrow \sum_{i=1}^{k} \left( [(k+1)\alpha] - [i\alpha] - [(k+1-i)\alpha] \right) \ge 0. \end{aligned}$$
Note that, $[x+y] \ge [x]+[y]$ holds for any real numbers $x, y$, hence $\textcircled{4}$ holds. The proof is complete.