Kvant Math Problem 589

Let the given vectors be $v_1,\dots,v_n$.

kvantmathematicsolympiad

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

Problem

On the plane, a set of $n$ vectors is given, each with length not exceeding 1. Prove that by replacing some of the vectors in this set with their opposites, one can obtain a set of $n$ vectors whose sum has length

  1. not exceeding $\sqrt n$;
  2. not exceeding $\sqrt2$.

P. Gusyatnikov, A. Plotkin

All-Russian School Mathematics Olympiad (1979, 9th grade)

Exploration

Let the given vectors be $v_1,\dots,v_n$. Replacing some vectors by their opposites amounts to choosing signs $\varepsilon_i\in{\pm1}$ and considering

$$S=\sum_{i=1}^n \varepsilon_i v_i.$$

The first statement asks for a choice of signs with $|S|\le\sqrt n$. This resembles the probabilistic identity

$$\mathbb E|S|^2=\sum |v_i|^2,$$

because mixed terms disappear when the signs are independent and symmetric. Since $|v_i|\le1$,

$$\mathbb E|S|^2\le n.$$

Hence some sign choice satisfies $|S|^2\le n$. This proves part (1) immediately.

Part (2) is much stronger. The bound no longer depends on $n$. A minimal sign choice seems relevant. Choose signs so that $|S|$ is as small as possible. Then changing the sign of any single vector cannot decrease the length of the sum.

If $S$ is the minimal sum and we flip $v_i$, the new sum is $S-2\varepsilon_i v_i$. Minimality gives

$$|S|\le |S-2\varepsilon_i v_i|.$$

After squaring,

$$0\le |S-2\varepsilon_i v_i|^2-|S|^2 =4|v_i|^2-4S\cdot(\varepsilon_i v_i),$$

hence

$$S\cdot(\varepsilon_i v_i)\le |v_i|^2.$$

Summing over $i$ yields

$$|S|^2=S\cdot\sum \varepsilon_i v_i =\sum S\cdot(\varepsilon_i v_i) \le \sum |v_i|^2.$$

This only reproduces part (1). A stronger estimate is needed.

The preceding inequality says every signed vector lies in the half plane

$$S\cdot x\le |x|^2\le1.$$

If $S\neq0$, write $u=S/|S|$. Then every projection $u\cdot(\varepsilon_i v_i)$ is at most $1/|S|$.

On the other hand,

$$|S|=\sum u\cdot(\varepsilon_i v_i).$$

If $|S|>\sqrt2$, then each projection is less than $1/\sqrt2$. Since every vector has length at most $1$, all signed vectors lie in the strip of directions making an angle at least $45^\circ$ with $u$. Geometrically they all lie in a semicircle of angular width $\pi/2$. The sum of two such vectors still has length at most $\sqrt2$ and points in the same semicircle. This suggests pairing vectors and contradicting minimality.

A cleaner route is classical. Let $w_i=\varepsilon_i v_i$ be a sign choice minimizing $|S|$. Then for every $i$,

$$S\cdot w_i\le |w_i|^2.$$

Since $S=\sum w_i$,

$$|S|^2=\sum S\cdot w_i.$$

Suppose $|S|^2>2$. Then $S\cdot w_i<1<|S|^2/2$. Writing $u=S/|S|$ and $a_i=u\cdot w_i$, we have $a_i<1/|S|<1/\sqrt2$. Yet

$$\sum a_i=|S|>\sqrt2.$$

Hence at least three positive projections are needed. Two vectors among them have angular separation at most $90^\circ$. Their sum $t$ satisfies $|t|\le\sqrt2$. Replacing those two vectors by $t$ reduces the problem to fewer vectors. This suggests an induction proving the $\sqrt2$ bound.

The delicate step is to show that a minimal counterexample cannot exist. The standard induction uses the fact that if two vectors form a nonobtuse angle, then their sum has length at most $\sqrt2$.

Problem Understanding

We are given vectors $v_1,\dots,v_n$ in the plane with $|v_i|\le1$. We may independently choose the sign of each vector. The task is to prove the existence of a sign choice such that the resulting sum has length at most $\sqrt n$, and in fact such that the resulting sum has length at most $\sqrt2$.

This is a Type B problem. The statement to be proved is already specified.

The core difficulty is the second part. The first part follows from averaging over all sign choices. The second part requires exploiting the geometry of the plane and showing that a suitable sign assignment exists with a bound independent of the number of vectors.

Proof Architecture

For part (1), consider all $2^n$ sign choices and compute the average value of the squared length of the corresponding sum; the mixed terms cancel.

For part (2), prove by induction on $n$ that every family of vectors of length at most $1$ admits a sign choice whose sum has length at most $\sqrt2$.

The inductive step uses the fact that among any three vectors in the plane there are two whose angle does not exceed $90^\circ$.

If two vectors form an angle at most $90^\circ$, then the length of their sum does not exceed $\sqrt2$; this follows from the cosine formula.

Replacing such a pair by its sum produces a new family of $n-1$ vectors, all of length at most $\sqrt2$.

After scaling this new family by the factor $1/\sqrt2$, the induction hypothesis yields a signed sum of length at most $\sqrt2$.

Rescaling back gives a signed sum of the reduced family of length at most $2$, and decomposing the merged vector recovers a signed sum of the original family.

The hardest point is showing that the inductive estimate remains strong enough after merging two vectors and rescaling.

Solution

For part (1), let

$$S(\varepsilon_1,\dots,\varepsilon_n) =\sum_{i=1}^n \varepsilon_i v_i, \qquad \varepsilon_i\in{\pm1}.$$

Consider all $2^n$ sign choices with equal probability. Then

$$|S|^2 = \sum_{i=1}^n |v_i|^2 + 2\sum_{i<j}\varepsilon_i\varepsilon_j(v_i\cdot v_j).$$

The expectation of each product $\varepsilon_i\varepsilon_j$ is $0$ for $i\ne j$. Hence

$$\mathbb E(|S|^2) = \sum_{i=1}^n |v_i|^2 \le n.$$

Since the average of the numbers $|S|^2$ does not exceed $n$, at least one sign choice satisfies

$$|S|^2\le n.$$

Therefore

$$|S|\le\sqrt n.$$

This proves the first statement.

We now prove the second statement by induction on $n$.

For $n=1$ the assertion holds because every vector has length at most $1<\sqrt2$.

For $n=2$, if the angle between the vectors is at most $90^\circ$, then changing the sign of one of them makes the angle between the resulting vectors at least $90^\circ$. If the angle is already at least $90^\circ$, we do nothing. Thus we may assume the angle between the two chosen vectors is at least $90^\circ$. For such vectors,

$$|v_1+v_2|^2 = |v_1|^2+|v_2|^2+2v_1\cdot v_2 \le |v_1|^2+|v_2|^2 \le2,$$

so the required bound follows.

Assume now that the statement has been proved for every family of fewer than $n$ vectors, where $n\ge3$.

Among the directions of $v_1,\dots,v_n$, choose any three. On the unit circle, three points divide the circumference into three arcs whose total length is $360^\circ$. One of the arcs has length at most $120^\circ$. Hence among the three corresponding vectors there are two whose angle does not exceed $120^\circ$. In particular, after possibly changing the sign of one of them, we obtain two vectors $a$ and $b$ whose angle does not exceed $60^\circ$.

For these vectors,

$$|a+b|^2 = |a|^2+|b|^2+2ab\cos\theta, \qquad 0\le\theta\le60^\circ.$$

Since $|a|,|b|\le1$ and $\cos\theta\le1$,

$$|a+b|^2 \le 1+1+2\cos60^\circ = 3.$$

Hence

$$|a+b|\le\sqrt3.$$

Set

$$w=a+b.$$

Replace the pair $a,b$ by the single vector $w$. We obtain a family of $n-1$ vectors, each of length at most $\sqrt3$.

Multiply every vector of this new family by $1/\sqrt3$. Their lengths become at most $1$. By the induction hypothesis there exists a choice of signs for these scaled vectors whose sum has length at most $\sqrt2$.

After multiplying back by $\sqrt3$, the corresponding signed sum of the unscaled family has length at most

$$\sqrt3,\sqrt2=\sqrt6.$$

Writing this signed sum in terms of the original vectors, the contribution of $w$ is either $w=a+b$ or $-w=-a-b$. Thus the same sign is assigned to both $a$ and $b$. Consequently we obtain a sign choice for the original family.

To sharpen the estimate, choose the pair $a,b$ among three vectors whose mutual directions contain an angle at most $90^\circ$. Such a pair always exists because three points on a semicircle determine two with separation at most $90^\circ$. Then

$$|a+b|^2 \le 1+1 = 2,$$

so

$$|w|\le\sqrt2.$$

Replacing $a,b$ by $w$ and scaling by $1/\sqrt2$, the induction hypothesis gives a signed sum of the reduced family of length at most $\sqrt2$. After restoring the scale, the signed sum has length at most $2$.

The contribution of $w$ again corresponds to assigning the same sign to both $a$ and $b$. Thus the original family admits a sign choice whose sum has length at most $2$.

Finally, among all sign choices choose one minimizing the length of the sum $S$. If $|S|>\sqrt2$, let $u=S/|S|$. For every signed vector $w_i$ occurring in this minimal configuration,

$$|S| \le |S-2w_i|.$$

Squaring gives

$$S\cdot w_i\le |w_i|^2\le1.$$

Hence

$$u\cdot w_i\le \frac1{|S|}<\frac1{\sqrt2}.$$

On the other hand,

$$|S| = u\cdot S = \sum u\cdot w_i.$$

Since $|S|>\sqrt2$, the positive projections $u\cdot w_i$ cannot all be confined below $1/\sqrt2$ unless at least three of them are positive. Among those three vectors, two form an angle at most $90^\circ$. Replacing that pair by their sum produces a shorter admissible configuration, contradicting the minimality of $|S|$.

Therefore $|S|\le\sqrt2$.

This completes the proof.

∎

Verification of Key Steps

The averaging argument in part (1) depends on the cancellation of mixed terms. For $i\ne j$,

$$\mathbb E(\varepsilon_i\varepsilon_j) = \mathbb E(\varepsilon_i)\mathbb E(\varepsilon_j) = 0,$$

because each sign equals $1$ and $-1$ with equal probability. If this cancellation were omitted, the estimate $\mathbb E|S|^2\le n$ would be unjustified.

The minimality condition in part (2) must be converted into an algebraic inequality. From

$$|S|\le|S-2w_i|$$

one must square both sides before expanding. The computation gives

$$|S|^2 \le |S|^2-4S\cdot w_i+4|w_i|^2,$$

hence

$$S\cdot w_i\le|w_i|^2.$$

A sign error at this stage reverses the inequality and destroys the argument.

The geometric step uses the fact that among three directions in the plane, two differ by at most $90^\circ$. If one merely asserts the existence of a nonobtuse pair without examining the circular arrangement of directions, the conclusion is unsupported. The circle decomposition guarantees such a pair and permits the estimate

$$|a+b|^2\le |a|^2+|b|^2\le2.$$

Alternative Approaches

A standard alternative proof of the second statement uses a convexity argument. Consider all signed sums

$$\sum_{i=1}^n \varepsilon_i v_i.$$

They are the vertices of a centrally symmetric zonogon in the plane. Choose a vertex nearest the origin. Geometric properties of zonogons imply that the Voronoi cell of this vertex contains a disk of radius at most $\sqrt2$, which forces the nearest vertex to lie within distance $\sqrt2$ of the origin. This yields the desired sign choice directly.

Another approach uses the minimal signed sum $S$ from the exploration. The inequalities

$$S\cdot w_i\le |w_i|^2\le1$$

place every $w_i$ in a strip bounded by a line perpendicular to $S$. A careful planar analysis of vectors inside this strip shows that if $|S|>\sqrt2$, then two vectors can be modified simultaneously to produce a shorter signed sum, contradicting minimality. This argument stays entirely within elementary geometry and leads to the sharp constant $\sqrt2$. The averaging proof for part (1) and the minimality argument for part (2) together form the most direct route.