**u**_{1}, **u**_{2}, ... , **u**_{n} are vectors in the plane, each with length at most 1, and with sum zero. Show that one can rearrange them as **v**_{1}, **v**_{2}, ... , **v**_{n} so that all the partial sums **v**_{1}, **v**_{1} + **v**_{2}, **v**_{1} + **v**_{2} + **v**_{3}, ... , **v**_{1} + **v**_{2} + ... + **v**_{n} have length at most √5.

**Solution**

Suppose first that all the vectors are multiples of the unit vector **e**, so **u**_{i} = x_{i}**e**. We show that a stronger result holds with 1 in place of √5. List the positive x_{i} and some or all of the zero x_{i} in any order: s_{1}, s_{2}, s_{3}, ... . List the negative x_{i} and some or all of the zero x_{i} in any order: t_{1}, t_{2}, t_{3}, ... . Take s_{1}, then take the smallest i such that s_{1} + t_{1} + t_{2} + ... t_{i} <= 0. Then take the smallest j such that s_{1} + t_{1} + t_{2} + ... + t_{i} + s_{2} + s_{3} + ... + s_{j} ≥ 0 and so on. Clearly the partial sums all have absolute value at most max |x_{i}| ≤ 1.

Now take the subset of the vectors whose sum has the largest absolute value. Without loss of generality it is **s** = **u**_{1}, **u**_{2}, ... , **u**_{m}. Let the unit vector in the direction of **s**, and let the unit vector perpendicular to **s** be **f**. We may take the vectors **u**_{i} for i = 1, 2, ... , m to be x_{i}**e** + y_{i}**f** and the remaining vectors to be X_{j}**e** + Y_{j}**f** for j = 1, 2, ... , n-m. Since the vectors have zero sum we have y_{1} + ... + y_{m} + Y_{1} + ... + Y_{n-m} = 0. Also y_{1} + ... + y_{m} = 0 and hence Y_{1} + ... + Y_{n-m} = 0. By the maximality of **s** we have all x_{i} ≥ 0 and all X_{i} ≤ 0.

Using the first result, we may assume that all the partial sums |y_{1} + y_{2} + ... + y_{i}| ≤ 1 and |Y_{1} + Y_{2} + ... + Y_{j}| ≤ 1. Using the same technique as in the first result we may take blocks of terms alternately from x_{i} and X_{j} so that all the partial sums |x_{1} + X_{1} + ... + X_{a} + x_{2} + ... + x_{b} + X_{a+1} + ... | ≤ 1. The corresponding partial sums for the other coordinate are the sum of a partial sum of y_{i} and a partial sum of Y_{j}, so they each have absolute value at most 1 + 1 = 2. Hence the partial sums of the vectors all have absolute value at most √(1^{2} + 2^{2}) = √5.

© John Scholes

jscholes@kalva.demon.co.uk

30 Dec 2002

Last corrected/updated 30 Dec 02