Problem: (1975 IMO - #1) 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 $\displaystyle \sum \limits_{i=1}^{n} ( x_{i} -\ y_{i} )^{2} \leq \sum \limits_{i=1}^{n} ( x_{i} - z_{i})^{2}$.
Solution: Expanding both sides, we see that
$ \displaystyle \sum x_i^2 $ and $ \displaystyle \sum y_i^2 = \sum z_i^2 $ appear on both sides, so we can cancel them out, leaving
$ \displaystyle -2 \sum x_iy_i \le -2 \sum x_iz_i \Rightarrow \sum x_iy_i \ge \sum x_iz_i $ which is a direct result of the Rearrangement Inequality (easily extended to all reals). QED.
--------------------
Comment: Well, I can't say this is the toughest IMO problem ever, but it does teach a few good lessons. One might be inclined to keep the squared differences there because they do look a bit nicer than after expansion. But getting a little messy can sometimes produce exactly the result you want, as it does here. Knowing the Rearrangement Inequality basically gives you the first ideas of an approach which is easy to finish.
--------------------
Practice Problem: Extend the Rearrangement Inequality to all reals (i.e. show that the proof holds even when there are negative numbers).
No comments:
Post a Comment