Maths Olympiad Prep

Library / /257 of 520

Algebra Difficulty 6.5 National olympiad Prove it

2. (CZS) IMO1{ }^{\mathrm{IMO} 1} Let x1≥x2≥⋯≥xnx_{1} \geq x_{2} \geq \cdots \geq x_{n} and y1≥y2≥⋯≥yny_{1} \geq y_{2} \geq \cdots \geq y_{n} be two nn-tuples of numbers. Prove that
∑i=1n(xi−yi)2≤∑i=1n(xi−zi)2 \sum_{i=1}^{n}\left(x_{i}-y_{i}\right)^{2} \leq \sum_{i=1}^{n}\left(x_{i}-z_{i}\right)^{2}
is true when z1,z2,…,znz_{1}, z_{2}, \ldots, z_{n} denote y1,y2,…,yny_{1}, y_{2}, \ldots, y_{n} taken in another order.

Solution

2. Since there are finitely many arrangements of the ziz_{i}'s, assume that z1,…,znz_{1}, \ldots, z_{n} is the one for which ∑i=1n(xi−zi)2\sum_{i=1}^{n}\left(x_{i}-z_{i}\right)^{2} is minimal. We claim that in this case i<j⇒zi≥zji<j \Rightarrow z_{i} \geq z_{j}, from which the claim of the problem directly follows. Indeed, otherwise we would have (xi−zj)2+(xj−zi)2=(xi−zi)2+(xj−zj)2+2(xizi+xjzj−xizj−xjzi)=(xi−zi)2+(xj−zj)2+2(xi−xj)(zi−zj)≤(xi−zi)2+(xj−zj)2 \begin{aligned} \left(x_{i}-z_{j}\right)^{2}+\left(x_{j}-z_{i}\right)^{2}= & \left(x_{i}-z_{i}\right)^{2}+\left(x_{j}-z_{j}\right)^{2} \\ & +2\left(x_{i} z_{i}+x_{j} z_{j}-x_{i} z_{j}-x_{j} z_{i}\right) \\ = & \left(x_{i}-z_{i}\right)^{2}+\left(x_{j}-z_{j}\right)^{2}+2\left(x_{i}-x_{j}\right)\left(z_{i}-z_{j}\right) \\ \leq & \left(x_{i}-z_{i}\right)^{2}+\left(x_{j}-z_{j}\right)^{2} \end{aligned} contradicting the assumption.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.