Let x1,x2,…,xk be vectors of m-dimensional Euclidian space, such that x1+x2+⋯+xk=0. Show that there exists a permutation π of the integers {1,2,…,k} such that
i=1∑nxπ(i)≤(i=1∑k∥xi∥2)1/2for each n=1,2,…,k.
Note that ∥⋅∥ denotes the Euclidian norm.
Πρωτότυπο από το επίσημο PDF
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Χρόνος σε αυτό το θέμα
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
Solution. We define π inductively. Set π(1)=1. Assume π is defined for i=1,2,…,n and also
i=1∑nxπ(i)2≤i=1∑n∥xπ(i)∥2.(1)
Note (1) is true for n=1. We choose π(n+1) in a way that (1) is fulfilled with n+1 instead of n. Set y=i=1∑nxπ(i) and A={1,2,…,k}∖{π(i):i=1,2,…,n}. Assume that (y,xr)>0 for all r∈A. Then (y,r∈A∑xr)>0 and in view of y+r∈A∑xr=0 one gets −(y,y)>0, which is impossible. Therefore there is r∈A such that
which verifies (1) for n+1. Thus we define π for every n=1,2,…,k. Finally from (1) we get
i=1∑nxπ(i)2≤i=1∑n∥xπ(i)∥2≤i=1∑k∥xi∥2.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 8–9. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.