uniolympiads English

IMC 1994, Ημέρα 2, Θέμα 5

Let x1,x2,…,xkx_1, x_2, \dots, x_k be vectors of mm-dimensional Euclidian space, such that x1+x2+⋯+xk=0x_1 + x_2 + \dots + x_k = 0. Show that there exists a permutation π\pi of the integers {1,2,…,k}\{1, 2, \dots, k\} such that

∥∑i=1nxπ(i)∥≤(∑i=1k∥xi∥2)1/2for each n=1,2,…,k.\left\| \sum_{i=1}^{n} x_{\pi(i)} \right\| \le \left( \sum_{i=1}^{k} \|x_i\|^2 \right)^{1/2} \quad \text{for each } n = 1, 2, \dots, k.

Note that ∥⋅∥\|\cdot\| denotes the Euclidian norm.

Πρωτότυπο από το επίσημο PDF(18 points) Let x 1 , x 2 , . . . , x k be vectors of m-dimensional Euclidian space, such that x 1 +x 2 +· · ·+x k = 0. Show that there exists a permutation π of the integers {1, 2, . . . , k} such that n X x π(i) ≤ i=1 k X kx i k 2 i=1 ! 1/2 for each n = 1, 2, . . . , k. Note that k · k denotes the Euclidian norm.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution. We define π\pi inductively. Set π(1)=1\pi(1)=1. Assume π\pi is defined for i=1,2,…,ni=1,2,\dots,n and also

∥∑i=1nxπ(i)∥2≤∑i=1n∥xπ(i)∥2.(1)\left\|\sum_{i=1}^nx_{\pi(i)}\right\|^2\le\sum_{i=1}^n\|x_{\pi(i)}\|^2.\tag{1}
Note (1) is true for n=1n=1. We choose π(n+1)\pi(n+1) in a way that (1) is fulfilled with n+1n+1 instead of nn. Set y=∑i=1nxπ(i)y=\sum\limits_{i=1}^nx_{\pi(i)} and A={1,2,…,k}∖{π(i):i=1,2,…,n}A=\{1,2,\dots,k\}\setminus\{\pi(i):i=1,2,\dots,n\}. Assume that (y,xr)>0(y,x_r)>0 for all r∈Ar\in A. Then (y,∑r∈Axr)>0\left(y,\sum\limits_{r\in A}x_r\right)>0 and in view of y+∑r∈Axr=0y+\sum\limits_{r\in A}x_r=0 one gets −(y,y)>0-(y,y)>0, which is impossible. Therefore there is r∈Ar\in A such that
(y,xr)≤0.(2)(y,x_r)\le 0.\tag{2}
Put π(n+1)=r\pi(n+1)=r. Then using (2) and (1) we have
∥∑i=1n+1xπ(i)∥2=∥y+xr∥2=∥y∥2+2(y,xr)+∥xr∥2≤∥y∥2+∥xr∥2≤≤∑i=1n∥xπ(i)∥2+∥xr∥2=∑i=1n+1∥xπ(i)∥2,\begin{aligned}\left\|\sum_{i=1}^{n+1}x_{\pi(i)}\right\|^2&=\|y+x_r\|^2=\|y\|^2+2(y,x_r)+\|x_r\|^2\le\|y\|^2+\|x_r\|^2\le\\ &\le\sum_{i=1}^n\|x_{\pi(i)}\|^2+\|x_r\|^2=\sum_{i=1}^{n+1}\|x_{\pi(i)}\|^2,\end{aligned}
which verifies (1) for n+1n+1. Thus we define π\pi for every n=1,2,…,kn=1,2,\dots,k. Finally from (1) we get
∥∑i=1nxπ(i)∥2≤∑i=1n∥xπ(i)∥2≤∑i=1k∥xi∥2.\left\|\sum_{i=1}^nx_{\pi(i)}\right\|^2\le\sum_{i=1}^n\|x_{\pi(i)}\|^2\le\sum_{i=1}^k\|x_i\|^2.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 8–9. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;