IMO 1988 SL 8

Origin: FRA

Problem

Let u1, u2, . . . , um be m vectors in the plane, each of length less than or equal to 1, which add up to zero. Show that one can rear- range u1, u2, . . . , um as a sequence v1, v2, . . . , vm such that each partial sum v1, v1 + v2, v1 + v2 + v3, . . . , v1 + v2 + \cdot \cdot \cdot + vm has length less than or equal to \sqrt 5.

Solution

Consider first the case that the vectors are on the same line. Then if e is a unit vector, we can write u1 = x1e, . . . , un = xne for scalars xi, |xi| \leq1, with zero sum. It is now easy to permute x1, x2, . . . , xn into z1, z2, . . . zn so that |z1| \leq1, |z1 + z2| \leq1, . . . , |z1 + z2 + \cdot \cdot \cdot + zn−1| \leq1. Indeed, suppose w.l.o.g. that z1 = x1 \geq0; then we choose z2, . . . , zr from the xi’s to be negative, until we get to the first r with x1 + x2 + \cdot \cdot \cdot + xr \leq0; we continue successively choosing positive zj’s from the remaining xi’s until we get the first partial sum that is positive, and so on. It is easy to verify that |z1 + z2 + \cdot \cdot \cdot + zj| \leq1 for all j = 1, 2, . . ., n. Now we pass to the general case. Let s be the longest vector that can be obtained by summing a subset of u1, . . . , um, and assume w.l.o.g. that s = u1 + \cdot \cdot \cdot + up. Further, let \delta and \delta′ respectively be the lines through the origin O in the direction of s and perpendicular to s, and e, e′ respectively the unit vectors on \delta and \delta′. Put ui = xie + yie′, i = 1, 2, . . . , m. By the definition of \delta and \delta′, we have |xi|, |yi| \leq1; x1+\cdot \cdot \cdot+xm = y1+\cdot \cdot \cdot+ym = 0; y1+\cdot \cdot \cdot+yp = yp+1+\cdot \cdot \cdot+ym = 0; we also have xp+1, . . . , xm \leq0 (otherwise, if xi > 0 for some i, then |s+vi| > |s|), and similarly x1, . . . , xp \geq0. Finally, suppose by the one-dimensional case that y1, . . . , yp and yp+1, . . . , ym are permuted in such a way that all the sums y1 + \cdot \cdot \cdot + yi and yp+1 + \cdot \cdot \cdot + yp+i are \leq1 in absolute value. We apply the construction of the one-dimensional case to x1, . . . , xm tak- ing, as described above, positive zi’s from x1, x2, . . . , xp and negative ones

from xp+1, . . . , xm, but so that the order is preserved; this way we get a permutation x\sigma1, x\sigma2, . . . , x\sigmam. It is then clear that each sum y\sigma1 + y\sigma2 + \cdot \cdot \cdot+y\sigmak decomposes into the sum (y1 +y2 +\cdot \cdot \cdot+yl)+(yp+1 +\cdot \cdot \cdot+yp+n) (because of the preservation of order), and that each of these sums is less than or equal to 1 in absolute value. Thus each sum u\sigma1 + \cdot \cdot \cdot + u\sigmak is composed of a vector of length at most 2 and an orthogonal vector of length at most 1, and so is itself of length at most \sqrt 5.