u1, u2, ... , un are vectors in the plane, each with length at most 1, and with sum zero. Show that one can rearrange them as v1, v2, ... , vn so that all the partial sums v1, v1 + v2, v1 + v2 + v3, ... , v1 + v2 + ... + vn have length at most √5.
Solution
Suppose first that all the vectors are multiples of the unit vector e, so ui = xie. We show that a stronger result holds with 1 in place of √5. List the positive xi and some or all of the zero xi in any order: s1, s2, s3, ... . List the negative xi and some or all of the zero xi in any order: t1, t2, t3, ... . Take s1, then take the smallest i such that s1 + t1 + t2 + ... ti <= 0. Then take the smallest j such that s1 + t1 + t2 + ... + ti + s2 + s3 + ... + sj ≥ 0 and so on. Clearly the partial sums all have absolute value at most max |xi| ≤ 1.
Now take the subset of the vectors whose sum has the largest absolute value. Without loss of generality it is s = u1, u2, ... , um. Let the unit vector in the direction of s, and let the unit vector perpendicular to s be f. We may take the vectors ui for i = 1, 2, ... , m to be xie + yif and the remaining vectors to be Xje + Yjf for j = 1, 2, ... , n-m. Since the vectors have zero sum we have y1 + ... + ym + Y1 + ... + Yn-m = 0. Also y1 + ... + ym = 0 and hence Y1 + ... + Yn-m = 0. By the maximality of s we have all xi ≥ 0 and all Xi ≤ 0.
Using the first result, we may assume that all the partial sums |y1 + y2 + ... + yi| ≤ 1 and |Y1 + Y2 + ... + Yj| ≤ 1. Using the same technique as in the first result we may take blocks of terms alternately from xi and Xj so that all the partial sums |x1 + X1 + ... + Xa + x2 + ... + xb + Xa+1 + ... | ≤ 1. The corresponding partial sums for the other coordinate are the sum of a partial sum of yi and a partial sum of Yj, so they each have absolute value at most 1 + 1 = 2. Hence the partial sums of the vectors all have absolute value at most √(12 + 22) = √5.
© John Scholes
jscholes@kalva.demon.co.uk
30 Dec 2002
Last corrected/updated 30 Dec 02