Expanding and using the fact that $\sum_i y_i^2=\sum_i z_i^2$, we are left to prove that $\sum_i x_iy_i\geq \sum x_iz_i$ But this is exactly the content of the Rearrangement inequality - given $x_1\geq x_2\geq \ldots \geq x_n$, the sum $\sum_i x_iy_i$ is maximal iff $y_1\geq y_2\geq \ldots \geq y_n$

The problem has been posed in Tokyo University entrance exam 1987. Can someone give a more explanation for Japanese high school students who don't know learn rearrangement inequalityl?

The inequality is literally equivalent to the rearrangement inequality. So pick your favorite proof of it.

orl wrote: We consider two sequences of real numbers $ x_{1} \geq x_{2} \geq \ldots \geq x_{n}$ and $ \ y_{1} \geq y_{2} \geq \ldots \geq y_{n}.$ Let $ z_{1}, z_{2}, .\ldots, z_{n}$ be a permutation of the numbers $ y_{1}, y_{2}, \ldots, y_{n}.$ Prove that $ \sum \limits_{i = 1}^{n} ( x_{i} - \ y_{i} )^{2} \leq \sum \limits_{i = 1}^{n}$ $ ( x_{i} - z_{i})^{2}.$ \[ \sum_{i = 1}^{n} (x_i - y_i)^2 \leq \sum_{i = 1}^{n} (x_i - z_i)^2\] \[ \sum_{i = 1}^{n}x_i ^2 + \sum_{i = 1}^{n} y_i ^2 - 2\sum_{i = 1}^{n} x_i y_i \leq \sum_{i = 1}^n x_i ^2 + \sum_{i = 1}^n z_i - 2\sum_{i = 1}^n x_i z_i\] Since the sequence $ \left(z_n\right)$ is a rearrangement of the sequence $ \left(y_n \right)$ then $ \sum_{i = 1}^n y_i ^2 = \sum_{i = 1}^n z_i ^2$ We just need to prove that: \[ x_1 y_1 + x_2 y_2 + ... + x_n y_n \geq x_1 z_1 + x_2 z_2 + ... + x_n z_n\] The last inequality is true by Rearrangement inequality because the sequences $ (x_n)$ and $ (y_n)$ are increasing (similarly sorted)

Even though Tokyo University applicants except IMO perticipants woudn't know Rearrange Inequality,so could anyone prove the inequality without using directly Rearrangement Inequality?

kunny wrote: Even though Tokyo University applicants except IMO perticipants woudn't know Rearrange Inequality,so could anyone prove the inequality without using directly Rearrangement Inequality?

I also think as yours. Aren't there any solutions to prove the inequality? If so, the proof of Inequality is difficult for Japanese High School Students. Don't you think so? Could I see the official solution?

kunny wrote: I also think as yours. Aren't there any solutions to prove the inequality? If so, the proof of Inequality is difficult for Japanese High School Students. Don't you think so? Could I see the official solution? I think it is so difficult to show them, but you may consider the following way: Given that $ x_{1}\geq x_{2}\geq\ldots\geq x_{n} ,\ y_{1}\geq y_{2}\geq\ldots\geq y_{n}. $ Since $(x_n-x_k)(y_n-y{}_j{}_n)\ge 0 $ when $n\not =k ,n\not = j_n$ $\implies x{}_ky{}_j{}_n+x{}_ny{}_n\ge x_k\color{red}{y_n}\color{black}{+x_n}\color{red}{y{}_j{}_n}\cdots\color{black} {(*)}$ Let RHS of the ineq. be $S_0$ , when we exchange $y_n$ and $y{}_j{}_n$ and the other terms keep unchanged, the new Sum $S_1>S_0$ Then we use similiar ways to correct $(n-1)$th ,$(n-2)$th,..... we can get the sum $S_{n-1}$ , i.e. the LHS of the ineq. by at most $(n-1)$ exchanging processes. e.g. a permutation of y-subscript from (1,2,3,4,5) to (4,3,1,5,2) Then $S_0= x{}_1y{}_4+x{}_2y{}_3+x{}_3y{}_1+\color{blue}{x{}_4y{}_5+x{}_5y{}_2}$ Now $n=5$ ${{S_1=x{}_1y{}_4+x{}_2y{}_3+x{}_3y{}_1+\color{blue}{x{}_4y{}_2+x{}_5y{}_5}\color{black}=x{}_1y{}_4+x{}_4y{}_2+x{}_2y{}_3+x{}_3y{}_1+x{}_5y{}_5}}$ and $S_1\ge S_0$ ${S_1=\color{green}{x{}_1y{}_4+x{}_4y{}_2}\color{black}+x{}_2y{}_3+x{}_3y{}_1+x{}_5y{}_5}$ As $n=4$ ${S_2=\color{green}{x{}_1y{}_2+x{}_4y{}_4}\color{black}+x{}_2y{}_3+x{}_3y{}_1+x{}_5y{}_5}=x{}_1y{}_2+x{}_4y{}_4+x{}_2y{}_3+x{}_3y{}_1+x{}_5y{}_5$ and $S_2\ge S_1$ $S_2=x{}_1y{}_2+x{}_4y{}_4+\color{red}x{}_2y{}_3+x{}_3y{}_1\color{black}+x{}_5y{}_5$ As $n=3$ $S_3=x{}_1y{}_2+x{}_4y{}_4+\color{red}x{}_2y{}_1+x{}_3y{}_3\color{black}+x{}_5y{}_5=x{}_1y{}_2+x{}_2y{}_1+x{}_3y{}_3+x{}_4y{}_4+x{}_5y{}_5$ and $S_3\ge S_2$ At last take $n=2$ , we exchange the last two terms,i.e $S_3=\color{blue} x{}_1y{}_2+x{}_2y{}_1\color {black}+x{}_3y{}_3+x{}_4y{}_4+x{}_5y{}_5$ and get $S_4=x{}_1y{}_1+x{}_2y{}_2+x{}_3y{}_3+x{}_4y{}_4+x{}_5y{}_5$ and $S_4\ge S_3$ Then the given ineq. holds. If $j_n$ matches $n$ at the beginning , then we start from $(n-1)$. Hope the explanations may help you.

Tusen takk, vinskman.

Do we need to prove the Rearrangement inequality as this makes the problem obvious or is this just a really simple problem?

I says in PSS that this is equal to Chebyshev's eqaulity. How? Does anyone know? I have the same solution as enndb0x. Thanks!

Note after expanding, the inequality that we need to prove becomes $(x_1^2 + x_2^2 + x_3^2...x_n^2)+(y_1^2+y_2^2...y_n^2)-2(x_1y_1+x_2y_2...x_ny_n)\le (x_1^2 + x_2^2 + x_3^2...x_n^2)+(z_1^2+z_2^2+z_3^2...z_n^2)-2(x_1z_1+x_2z_2..x_nz_n)$. We know that $(z_1^2+z_2^2+z_3^2...z_n^2)=(y_1^2+y_2^2...y_n^2)$, so we can cancel those from both sides. Then our inequality becomes $-2(x_1y_1+x_2y_2...x_ny_n)\le -2(x_1z_1+x_2z_2...x_nz_n)$. We can divide both sides by -2 and then the result can easily be proven by the rearrangement inequality.