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 ].\stackrel{◯}{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 \cdots \le a_k$, $b_1\ge b_2\ge \cdots \ge b_k$ and ${\sum }_{i=1}^{k}i{a}_i={\sum }_{i=1}^{k}i{b}_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 \cdots \le x_{k+1}<y_{k+1}\le \cdots \le y_2\le y_1.$$ This contradicts ${\sum }_{i=1}^{k+1}i{x}_i={\sum }_{i=1}^{k+1}i{y}_i$. So we have $$\begin{array}{rl}\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{array}$$ $$\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 \cdots \le z_n$ and ${\sum }_{i=1}^{n}i{z}_i=0$. We only need to prove that $$\sum _{i=1}^n{z}_i[i\alpha ]\ge 0.\stackrel{◯}{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}i{z}_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.\stackrel{◯}{3}$$ Then $$\begin{array}{rl}\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{array}$$ Then, in order to prove $\stackrel{◯}{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.\stackrel{◯}{4}$$ But $$\begin{array}{rl}\stackrel{◯}{4}& \iff \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\\ & \iff \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{array}$$ 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{array}{rl}& [(k+1)\alpha ]\cdot k/2\ge \sum _{i=1}^k[i\alpha ]\\ & \iff \sum _{i=1}^k\left([(k+1)\alpha ]-[i\alpha ]-[(k+1-i)\alpha ]\right)\ge 0.\end{array}$$ Note that, $[x+y]\ge [x]+[y]$ holds for any real numbers $x,y$, hence $\stackrel{◯}{4}$ holds. The proof is complete.