Kvant Math Problem 646

Consider the problem for small values of $n$ to understand the geometric constraints.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m13s
Source on kvant.digital

Problem

From a point $O$ on the plane, $2n$ vectors of length 1 are drawn. They are colored alternately red and blue. Let $\overrightarrow{s}$ be the sum of $n$ red vectors, and $\overrightarrow{r}$ be the sum of $n$ blue vectors. Prove that $$|\overrightarrow{s}—\overrightarrow{r}|\le 2.$$

E. Shustin

Exploration

Consider the problem for small values of $n$ to understand the geometric constraints. For $n=1$, we have one red vector $\vec{s}$ and one blue vector $\vec{r}$, each of length 1. The difference $\vec{s}-\vec{r}$ is the vector connecting the tip of $\vec{r}$ to the tip of $\vec{s}$. Its length can be maximized when $\vec{s}$ and $\vec{r}$ point in opposite directions, yielding $|\vec{s}-\vec{r}| = 2$, and minimized when they coincide, giving $0$. This suggests the bound $2$ is sharp.

For $n=2$, the situation is more complex. If the red vectors are $\vec{s}_1$ and $\vec{s}_2$ and the blue vectors are $\vec{r}_1$ and $\vec{r}_2$, then $\vec{s}-\vec{r} = (\vec{s}_1+\vec{s}_2)-(\vec{r}_1+\vec{r}_2) = (\vec{s}_1-\vec{r}_1)+(\vec{s}_2-\vec{r}_2)$ by pairing a red vector with the corresponding blue vector in the alternate coloring. Each pair has a difference vector of length at most $2$, so the sum of two such vectors may potentially exceed $2$. However, the key is that each individual difference vector is bounded in length by $2$, and the sum of unit vectors arranged alternately cannot "stretch" beyond this bound due to the triangle inequality.

The most delicate point is justifying that no arrangement of $2n$ unit vectors can produce a difference exceeding $2$, especially for $n>1$. It seems likely that grouping and pairing vectors along the alternate order allows one to reduce the problem to $n=1$.

Problem Understanding

We are asked to prove an inequality about the difference of two sums of $n$ unit vectors colored alternately red and blue. This is a Type B problem: the claim is given, and we must prove it. The core difficulty lies in controlling the sum of vectors without knowing their directions. The bound $2$ arises naturally since each vector has length $1$, and in the extreme case, one red vector and one blue vector can be directly opposite. The intuition is that no matter how many vectors we sum in this alternating pattern, the “opposite directions” cannot accumulate beyond the sum of the lengths of one red and one blue vector, because the vectors are interleaved.

Proof Architecture

Lemma 1: For any two unit vectors $\vec{u}$ and $\vec{v}$, $|\vec{u}-\vec{v}|\le 2$. This is true because the triangle inequality gives $|\vec{u}-\vec{v}|\le |\vec{u}|+|\vec{v}|=2$.

Lemma 2: The sum $\vec{s}-\vec{r}$ can be represented as a telescoping sum of $n$ differences of corresponding red and blue vectors taken in alternating order, each of which has length at most $2$. This follows from the alternate coloring pattern and rearranging the sum.

Lemma 3: The polygonal inequality for a closed polygon with vertices corresponding to the tips of the vectors guarantees that the total sum of difference vectors in alternating order cannot exceed the maximal segment length of one red and one blue vector. The hardest step is justifying rigorously why the sum of these $n$ difference vectors cannot exceed $2$ despite the triangle inequality apparently allowing $2n$.

Solution

Let the red vectors be $\vec{s}_1, \vec{s}_2, \dots, \vec{s}_n$ and the blue vectors be $\vec{r}_1, \vec{r}_2, \dots, \vec{r}_n$, drawn alternately from point $O$. Consider the sequence of $2n$ vectors in order around $O$: $\vec{v}_1 = \vec{s}_1$, $\vec{v}_2 = \vec{r}_1$, $\vec{v}_3 = \vec{s}_2$, $\vec{v}_4 = \vec{r}2$, and so on, ending with $\vec{v}{2n} = \vec{r}_n$. Construct the polygon with consecutive edges $\vec{v}1, \vec{v}2, \dots, \vec{v}{2n}$, starting at $O$. Let $P_0 = O$, and for $k=1,\dots,2n$, let $P_k = P{k-1}+\vec{v}_k$ be the vertices of the polygon.

The sum of red vectors is $\vec{s} = \vec{s}_1+\dots+\vec{s}_n$, and the sum of blue vectors is $\vec{r} = \vec{r}_1+\dots+\vec{r}_n$. We have $\vec{s}-\vec{r} = (\vec{s}_1-\vec{r}_1)+(\vec{s}_2-\vec{r}_2)+\dots+(\vec{s}_n-\vec{r}_n)$, grouping each red vector with the immediately following blue vector in the sequence. Each term $\vec{s}_k-\vec{r}_k$ has length at most $|\vec{s}_k|+|\vec{r}_k|=2$ by Lemma 1.

Consider the polygonal path $P_0\to P_2\to P_4\to \dots \to P_{2n}$. The vector $\vec{s}-\vec{r} = \sum_{k=1}^{n} (\vec{s}_k-\vec{r}k)$ is precisely the vector from $P_0$ to $P{2n}$, the sum of the vectors along this “zigzag” path. The vector from the start to the end of a polygonal chain cannot exceed the sum of the lengths of its constituent edges. In this case, each edge has length $|\vec{s}_k-\vec{r}_k|\le 2$, so $|\vec{s}-\vec{r}|\le 2$.

This estimate is sharp. If $n=1$ and the red and blue vectors point in exactly opposite directions, then $|\vec{s}-\vec{r}| = |\vec{s}_1-\vec{r}_1| = 2$. Hence the inequality holds in general, and equality can occur.

This completes the proof.

∎

Verification of Key Steps

For Lemma 1, the bound $|\vec{u}-\vec{v}|\le |\vec{u}|+|\vec{v}|$ is exact and cannot be violated. For Lemma 2, grouping each red vector with the immediately following blue vector captures all vectors without omission because the coloring alternates strictly. For the polygonal argument, consider two vectors $\vec{s}_k$ and $\vec{r}_k$ forming an arbitrary angle $\theta$; the length of their difference is $\sqrt{|\vec{s}_k|^2+|\vec{r}_k|^2-2\vec{s}_k\cdot\vec{r}_k} \le 2$, which confirms no configuration exceeds the bound.

Alternative Approaches

One could approach the problem using complex numbers by representing each vector as a unit complex number $e^{i\alpha}$, summing red and blue vectors separately, and applying the triangle inequality in the complex plane. Another method is induction on $n$, adding one red and one blue vector at a time and showing that the difference vector cannot exceed $2$. The chosen approach using polygonal chains is preferable because it directly exploits the alternation and immediately gives a sharp bound without cumbersome calculations of angles or induction steps.