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.
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
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.
Transcribed from the official solutions, pages 8–9. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.