1975 IMO Problems/Problem 1

Problem

Let $x_i, y_i$ $(i=1,2,\cdots,n)$ be real numbers such that $x_1\ge x_2\ge\cdots\ge x_n \text{ and } y_1\ge y_2\ge\cdots\ge y_n.$ Prove that, if $z_1, z_2,\cdots, z_n$ is any permutation of $y_1, y_2, \cdots, y_n,$ then $\sum^n_{i=1}(x_i-y_i)^2\le\sum^n_{i=1}(x_i-z_i)^2.$

Solution

We can rewrite the summation as $\sum^n_{i=1} x_i^2 + \sum^n_{i=1} y_i^2 - \sum^n_{i=1}x_iy_i \le \sum^n_{i=1} x_i^2 + \sum^n_{i=1} z_i^2 - \sum^n_{i=1}x_iz_i.$ Since $\sum^n_{i=1} y_i^2 = \sum^n_{i=1} z_i^2$ , the above inequality is equivalent to $\sum^n_{i=1}x_iy_i \ge \sum^n_{i=1}x_iz_i.$ We will now prove that the left-hand side of the inequality is the greatest sum reached out of all possible values of $\sum^n_{i=1}x_iz_i$ . Obviously, if $x_1 = x_2 = \ldots = x_n$ or $y_1 = y_2 = \ldots = y_n$ , the inequality is true. Now, assume, for contradiction, that neither of those conditions are true and that there exists some order of $z_i$ s that are not ordered in the form $z_1 \ge z_2 \ge \ldots \ge z_n$ such that $\sum^n_{i=1}x_iz_i$ is at a maximum out of all possible permutations and is greater than the sum $\sum^n_{i=1}x_iy_i$ . This necessarily means that in the sum $\sum^n_{i=1}x_iz_i$ there exists two terms $x_pz_m$ and $x_qz_n$ such that $x_p > x_q$ and $z_m < z_n$ . Notice that $x_pz_n + x_qz_m - (x_pz_m + x_qz_n) = (x_p-x_q)(z_n-z_m) > 0,$ which means if we make the terms $x_pz_n$ and $x_qz_m$ instead of the original $x_pz_m$ and $x_qz_n$ , we can achieve a higher sum. However, this is impossible, since we assumed we had the highest sum. Thus, the inequality $\sum^n_{i=1}x_iy_i \ge \sum^n_{i=1}x_iz_i$ is proved, which is equivalent to what we wanted to prove. $\[\]$ ~Imajinary

1975 IMO (Problems) • Resources
Preceded by First Question	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

Page

Toolbox

Search

1975 IMO Problems/Problem 1

Problem

Solution

See Also