Kvant Math Problem 1483
Each vector lies in the first quadrant and has length $1$.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 10m28s
Source on kvant.digital
Problem
Find the smallest possible length of the sum of seven unit vectors with nonnegative coordinates in the plane $Oxy$.
B. D. Ginzburg
Exploration
Each vector lies in the first quadrant and has length $1$. Write the vectors as
$$u_k=(\cos\theta_k,\sin\theta_k),\qquad 0\le \theta_k\le \frac{\pi}{2}.$$
Their sum is
$$S=\sum_{k=1}^7u_k.$$
We seek the minimum possible value of $|S|$.
Since all coordinates are nonnegative, cancellation is impossible. If
$$X=\sum\cos\theta_k,\qquad Y=\sum\sin\theta_k,$$
then
$$|S|=\sqrt{X^2+Y^2}.$$
The problem becomes minimizing $X^2+Y^2$.
A first guess is that the vectors should be distributed as evenly as possible between the coordinate axes. For two vectors, taking one along each axis gives length $\sqrt2$, smaller than taking them in the same direction, which gives length $2$. For seven vectors, placing four on one axis and three on the other yields
$$|S|=\sqrt{4^2+3^2}=5.$$
We must determine whether anything smaller is possible.
Expanding,
$$|S|^2=\sum_{k=1}^7|u_k|^2+2\sum_{i<j}u_i\cdot u_j =7+2\sum_{i<j}\cos(\theta_i-\theta_j).$$
Since $0\le\theta_i,\theta_j\le\pi/2$, every difference satisfies
$$|\theta_i-\theta_j|\le\frac{\pi}{2},$$
hence every scalar product is nonnegative. This already gives
$$|S|^2\ge 7.$$
That lower bound is far too weak.
The crucial point is to exploit the inequality
$$(\cos\theta+\sin\theta)^2\ge 2.$$
Summing over seven vectors may give a fixed lower bound for $X+Y$, after which the quadratic inequality
$$X^2+Y^2\ge \frac{(X+Y)^2}{2}$$
could produce the desired estimate.
Indeed,
$$\cos\theta+\sin\theta\ge\sqrt2$$
on $[0,\pi/2]$, with equality only at $\theta=\pi/4$.
Therefore
$$X+Y\ge 7\sqrt2.$$
Then
$$X^2+Y^2\ge \frac{(X+Y)^2}{2}\ge \frac{(7\sqrt2)^2}{2}=49.$$
Thus $|S|\ge 5$.
Equality requires simultaneously
$$X=Y$$
and
$$\cos\theta_k+\sin\theta_k=\sqrt2$$
for every $k$. The second condition forces every $\theta_k$ to be $0$ or $\pi/2$. The first then requires equal numbers on the two axes as far as possible. With seven vectors, that means four on one axis and three on the other, yielding length $5$. This appears to be the optimum.
The most delicate step is the equality analysis.
Problem Understanding
We are given seven unit vectors in the plane, each having nonnegative coordinates. Equivalently, every vector lies in the closed first quadrant. We must find the smallest possible length of their sum.
This is a Type C problem. We must determine the minimum value, construct a configuration attaining it, and prove that no smaller value is possible.
The core difficulty is obtaining a sharp lower bound for the length of the sum despite the freedom in choosing seven directions.
The answer should be $5$. Intuitively, the sum is shortest when the total horizontal and vertical components are balanced as much as possible, and the extreme directions along the coordinate axes provide the greatest spreading of the vectors.
Proof Architecture
Let
$$X=\sum_{k=1}^7\cos\theta_k,\qquad Y=\sum_{k=1}^7\sin\theta_k.$$
Then the length of the sum equals $\sqrt{X^2+Y^2}$.
For every $\theta\in[0,\pi/2]$,
$$\cos\theta+\sin\theta\ge\sqrt2.$$
This follows from
$$(\cos\theta+\sin\theta)^2=1+\sin2\theta\ge1.$$
Summing the preceding inequality over all seven vectors gives
$$X+Y\ge7\sqrt2.$$
For nonnegative $X,Y$,
$$X^2+Y^2\ge \frac{(X+Y)^2}{2}.$$
This is equivalent to $(X-Y)^2\ge0$.
Combining the two inequalities yields
$$|S|^2=X^2+Y^2\ge49,$$
hence $|S|\ge5$.
To attain equality, take four vectors equal to $(1,0)$ and three equal to $(0,1)$. Their sum is $(4,3)$, whose length is $5$.
The equality conditions show that no smaller value is possible.
The lemma most likely to fail under scrutiny is the characterization of equality in the lower bound.
Solution
Let the seven unit vectors be
$$u_k=(\cos\theta_k,\sin\theta_k), \qquad 0\le\theta_k\le\frac{\pi}{2}, \qquad k=1,\dots,7.$$
Denote their sum by
$$S=\sum_{k=1}^7u_k.$$
Write
$$S=(X,Y),$$
where
$$X=\sum_{k=1}^7\cos\theta_k, \qquad Y=\sum_{k=1}^7\sin\theta_k.$$
Then
$$|S|^2=X^2+Y^2.$$
For every $\theta\in[0,\pi/2]$,
$$(\cos\theta+\sin\theta)^2 =\cos^2\theta+\sin^2\theta+2\sin\theta\cos\theta =1+\sin2\theta.$$
Since $\sin2\theta\ge0$ on this interval,
$$(\cos\theta+\sin\theta)^2\ge2,$$
hence
$$\cos\theta+\sin\theta\ge\sqrt2.$$
Summing over all seven vectors,
$$X+Y =\sum_{k=1}^7(\cos\theta_k+\sin\theta_k) \ge 7\sqrt2.$$
Next,
$$2(X^2+Y^2)-(X+Y)^2=(X-Y)^2\ge0,$$
so
$$X^2+Y^2\ge\frac{(X+Y)^2}{2}.$$
Therefore
$$|S|^2 =X^2+Y^2 \ge\frac{(X+Y)^2}{2} \ge\frac{(7\sqrt2)^2}{2} =49.$$
Thus
$$|S|\ge5.$$
It remains to show that this bound is attained. Take four vectors equal to $(1,0)$ and three vectors equal to $(0,1)$. Then
$$S=(4,3),$$
and hence
$$|S|=\sqrt{4^2+3^2}=5.$$
Since a configuration with length $5$ exists and every configuration satisfies $|S|\ge5$, the minimum possible length is
$$\boxed{5}.$$
Equality holds, for example, for four vectors along the positive $x$-axis and three vectors along the positive $y$-axis.
Verification of Key Steps
The first delicate step is the estimate
$$\cos\theta+\sin\theta\ge\sqrt2.$$
Using
$$(\cos\theta-\sin\theta)^2\ge0$$
gives
$$\cos^2\theta+\sin^2\theta\ge2\sin\theta\cos\theta,$$
hence
$$1\ge2\sin\theta\cos\theta.$$
Therefore
$$(\cos\theta+\sin\theta)^2 =1+2\sin\theta\cos\theta \ge2.$$
Equality occurs exactly when $\sin\theta\cos\theta=\tfrac12$, that is, when $\theta=\frac{\pi}{4}$.
The second delicate step is
$$X^2+Y^2\ge\frac{(X+Y)^2}{2}.$$
Expanding yields
$$2X^2+2Y^2-X^2-2XY-Y^2=(X-Y)^2.$$
The inequality is therefore exact and equality holds precisely when $X=Y$.
A careless argument could overlook that equality in the final bound requires equality in both intermediate inequalities. The constructed configuration avoids this issue because it directly gives $|S|=5$, matching the lower bound. Hence the minimum is established.
Alternative Approaches
Expand the square of the sum:
$$|S|^2 =\sum_{k=1}^7|u_k|^2 +2\sum_{i<j}u_i\cdot u_j.$$
Since each $|u_k|=1$,
$$|S|^2 =7+2\sum_{i<j}\cos(\theta_i-\theta_j).$$
One may then estimate the pairwise scalar products by expressing
$$\cos(\theta_i-\theta_j) =\cos\theta_i\cos\theta_j+\sin\theta_i\sin\theta_j \ge0.$$
Rewriting the resulting expression in terms of
$$X=\sum\cos\theta_i,\qquad Y=\sum\sin\theta_i$$
leads again to
$$|S|^2=X^2+Y^2.$$
Combining this with the bound $X+Y\ge7\sqrt2$ yields the same conclusion.
The main approach is preferable because it reaches the sharp lower bound directly through two elementary inequalities and makes the equality case transparent.