SOS
Opgave - IMO 1975 dag 1 vraag 1
Zij $x_1\le ...\le x_n$ en $y_1\le...\le y_n$. Bewijs dat voor elke permutatie $\sigma$ geldt dat $$\sum^n_{i=1}(x_i-y_i)^2 \leq \sum^n_{i=1}(x_i-y_{\sigma(i)})^2.$$
- login om te reageren
Olympia
Nederlandstalig olympiadeproject
Zoeken
Random generator
Niveau
Wie is online
Er zijn momenteel 0 gebruikers en 2 gasten online.
Oplossing
Merk op dat de optelling commutatief is, zodat de sommen $x_i^2$ en $y_i^2$ direct wegvallen, dus de uitdrukking is equivalent aan:
$\sum_{i=1}^{n}{x_iy_i} \ge \sum_{i=1}^{n}{x_iy_{\sigma(i)}}$
Dit geldt wegens de orde-ongelijkheid en gelijk gesorteerde rijen $(x_n)_n$ en $(y_n)_n$