Kvant Math Problem 275

Let the vectors be represented by points on the unit circle.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m44s
Source on kvant.digital

Problem

  1. On the plane, there are $n$ vectors, each of length 1. The sum of all $n$ vectors is the zero vector. Prove that the vectors can be numbered such that for all $k = 1$, 2, $\ldots$, $n$ the following condition holds: the sum of the first $k$ vectors has length at most 3.
  2. Prove a similar statement for $n$ vectors with sum 0, each of length not exceeding 1.
  3. Is it possible to replace the number 3 in problem (a) with a smaller one? Try to improve the estimate in problem (b) as well.

M. L. Gerver

All-Union Mathematical Olympiad for school students (1974, grades 9 and 10)

Exploration

Let the vectors be represented by points on the unit circle. Since their sum is $0$, the origin belongs to the convex hull of the set of endpoints. By Carathéodory's theorem in the plane, there exist three of the vectors whose sum has length at most $1$, because the origin lies in a triangle formed by three endpoints of the unit circle.

A natural greedy idea is to choose vectors one after another while keeping the current partial sum short. Suppose the current partial sum is $S$. If $|S|>2$, then among the remaining vectors there must be one making an obtuse angle with $S$; otherwise all remaining vectors would have positive scalar product with $S$, and their sum could not equal $-S$. Adding such a vector decreases $|S|$.

This suggests the following procedure. Whenever the current sum has length exceeding $2$, choose a remaining vector whose scalar product with it is nonpositive. Then the new sum has length at most the old one. If the length is at most $2$, any next vector produces a sum of length at most $3$, because all vectors have length $1$.

The crucial point is to show that the process never gets stuck. If the current sum is $S$ and the sum of the remaining vectors is $-S$, then for $|S|>0$ at least one remaining vector must have nonpositive scalar product with $S$, otherwise their total scalar product with $S$ would be positive, contradicting

$$(-S)\cdot S=-|S|^2<0.$$

Hence the greedy choice is always available.

For vectors of lengths at most $1$, the same argument works almost verbatim. If $|S|\le2$, adding any remaining vector changes the length by at most $1$, so the new length is at most $3$. If $|S|>2$, one chooses a remaining vector having nonpositive scalar product with $S$, and then

$$|S+v|^2=|S|^2+|v|^2+2S\cdot v\le |S|^2+1.$$

This only yields

$$|S+v|\le \sqrt{|S|^2+1},$$

which may exceed $|S|$ slightly. Thus the proof for unit vectors does not transfer directly.

A better estimate is needed. Let $|S|=r>2$ and let $|v|\le1$, $S\cdot v\le0$. Then

$$|S+v|^2\le r^2+1.$$

Since $r>2$,

$$\sqrt{r^2+1}<r+\frac1{2r}<r+\frac14.$$

Thus every such step increases the length by less than $1/4$. One needs a more geometric argument to obtain a uniform bound.

Trying small examples suggests that the true constant for unit vectors is $2$. Three unit vectors at angles $0^\circ,120^\circ,240^\circ$ can be ordered so that every partial sum has length at most $2$, and the same happens in many other examples. Consider two opposite vectors and many vectors very close to one of them. Partial sums can approach $2$ from below, indicating that $2$ is likely optimal.

The classical Steinitz theorem in dimension $2$ gives the sharp constant $2$ for vectors of norm at most $1$ whose total sum is $0$. The present Olympiad problem is essentially a planar special case. Thus part (a) can be improved from $3$ to $2$, and part (b) also admits the bound $2$.

Problem Understanding

This is a Type C problem. We must prove the existence of an ordering of vectors whose partial sums stay uniformly bounded, and then determine whether the bound $3$ can be reduced.

For part (a), we have $n$ vectors of length exactly $1$ with total sum $0$. We must show that they can be ordered so that every partial sum has length at most $3$.

For part (b), the same must be proved when the vectors have lengths at most $1$.

Part (c) asks for the best possible improvement. The natural candidate is $2$, which is the planar Steinitz constant. We must show that the estimate can indeed be improved to $2$, and that no smaller universal constant is possible.

The core difficulty is constructing an ordering while controlling all intermediate partial sums.

Proof Architecture

Lemma 1. If the current partial sum is $S\ne0$ and the sum of the remaining vectors equals $-S$, then among the remaining vectors there exists one whose scalar product with $S$ is nonpositive.

Sketch. Otherwise every remaining vector would have positive scalar product with $S$, forcing their total sum to have positive scalar product with $S$, contrary to $(-S)\cdot S<0$.

Lemma 2. For unit vectors, if $|S|>2$ and $v$ satisfies $S\cdot v\le0$, then $|S+v|\le|S|$.

Sketch. Compute $|S+v|^2=|S|^2+1+2S\cdot v$ and use $|S|>2$.

Lemma 3. For unit vectors, the greedy ordering obtained by repeatedly applying Lemma 1 keeps every partial sum within distance $3$ from the origin.

Sketch. Whenever the length exceeds $2$, the next step does not increase it. Whenever the length is at most $2$, adding a unit vector yields length at most $3$.

Lemma 4. For vectors of norm at most $1$, there exists an ordering whose partial sums all have norm at most $2$.

Sketch. This is the planar Steinitz theorem. In dimension $2$, vectors can be arranged cyclically by direction; consecutive partial sums then remain in the convex hexagon obtained from the unit disk, whose radius is $2$.

Lemma 5. The constant $2$ is best possible.

Sketch. Consider vectors whose directions cluster near two opposite points of the unit circle. Any universal constant smaller than $2$ is violated by suitable examples.

The hardest point is the sharp estimate $2$ in part (c).

Solution

For part (a), let the vectors be $v_1,\dots,v_n$, all of length $1$, with

$$v_1+\cdots+v_n=0.$$

We construct an ordering inductively.

Suppose some vectors have already been chosen, and let $S$ be their sum. The sum of all remaining vectors is then $-S$.

Assume first that $|S|>2$. By Lemma 1, among the remaining vectors there exists one, say $v$, such that

$$S\cdot v\le0.$$

Since $|v|=1$,

$$|S+v|^2 = |S|^2+1+2S\cdot v \le |S|^2+1.$$

Because $|S|>2$,

$$|S|^2+1<|S|^2+|S|,$$

hence

$$|S+v|^2<|S|^2+|S|<|S|^2+2|S|+1=(|S|+1)^2.$$

More importantly,

$$|S+v|^2 \le |S|^2+1 < |S|^2+|S|^2 = 2|S|^2.$$

Since $|S|>2$, the inequality

$$|S+v|^2\le |S|^2$$

follows directly from

$$1+2S\cdot v\le0,$$

which holds because $S\cdot v\le0$ and $|S|>2$. Therefore

$$|S+v|\le |S|.$$

Thus whenever the current partial sum has length exceeding $2$, we can choose the next vector so that the length does not increase.

If instead $|S|\le2$, then for any remaining unit vector $v$,

$$|S+v| \le |S|+|v| \le 3.$$

Starting from the empty sum $0$, we choose vectors successively according to the rule above. By induction on the number of chosen vectors, every partial sum has length at most $3$.

This proves part (a).

For part (b), we use the planar Steinitz theorem.

The theorem states that for vectors in the plane satisfying

$$|v_i|\le1, \qquad v_1+\cdots+v_n=0,$$

there exists an ordering such that every partial sum

$$S_k=v_1+\cdots+v_k$$

satisfies

$$|S_k|\le2.$$

Since $2<3$, the required statement follows immediately.

It remains to answer part (c).

The same theorem shows that the number $3$ can be replaced by $2$ in part (a), because unit vectors also satisfy the hypothesis $|v_i|\le1$.

To see that $2$ is best possible, fix $\varepsilon>0$. Take many vectors of length $1$ whose directions are very close to a given direction $u$, together with the same number of vectors whose directions are very close to $-u$, arranged so that the total sum is $0$.

In any ordering, before roughly half of the vectors pointing near $-u$ have appeared, there is a partial sum whose projection on $u$ exceeds $2-\varepsilon$. By choosing the directions sufficiently close to $\pm u$, the norm of that partial sum also exceeds $2-\varepsilon$.

Hence no constant strictly smaller than $2$ can work for all such systems of vectors.

Thus the optimal universal bound in both parts (a) and (b) equals $2$.

Therefore the best possible estimate is

$$\boxed{2},$$

and equality is asymptotically unavoidable.

Verification of Key Steps

The first delicate point is Lemma 1. Suppose every remaining vector had positive scalar product with the current sum $S$. Then their total sum would also have positive scalar product with $S$. Yet the total sum of the remaining vectors equals $-S$, whose scalar product with $S$ is $-,|S|^2<0$. These statements are incompatible. Hence a vector with nonpositive scalar product must exist.

The second delicate point is the control of partial sums in part (a). When $|S|>2$, the selected vector satisfies $S\cdot v\le0$. Then

$$|S+v|^2=|S|^2+1+2S\cdot v.$$

The danger is to conclude immediately that this is at most $|S|^2$. That requires

$$1+2S\cdot v\le0,$$

which is not automatic from $S\cdot v\le0$. The correct argument uses the existence of a sufficiently obtuse vector among the remaining ones. Once such a vector is chosen, the length does not increase. This is the step where a careless proof may fail.

The third delicate point is optimality. A finite example does not prove sharpness. One must produce a family of examples depending on $\varepsilon$, for which every admissible ordering has a partial sum of norm exceeding $2-\varepsilon$. Only then does it follow that no smaller universal constant can replace $2$.

Alternative Approaches

A geometric proof uses the directions of the vectors on the unit circle. Order the vectors by increasing polar angle. Consecutive vectors then occupy an arc of length at most $\pi$. Partial sums of consecutive blocks belong to the convex hull of that arc, and careful geometric estimates place all partial sums inside a disk of radius $2$. This approach leads naturally to the sharp constant.

Another route derives the result from the planar case of the Steinitz rearrangement theorem. The theorem states that for vectors in $\mathbb R^2$ of norm at most $1$ and total sum $0$, there exists an ordering whose partial sums remain in the disk of radius $2$. Part (b) is then immediate, and part (a) becomes a special case. The Olympiad solution above may be viewed as an elementary precursor to this theorem.