Kvant Math Problem 656

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

Problem

In space, there are 30 nonzero vectors. Prove that among them there exist two whose angle is less than $45^\circ$.

A. K. Tolpygo

Exploration

The statement concerns only the directions of the vectors, since scaling a nonzero vector does not change its angle with another vector. Thus each vector determines a point on the unit sphere.

A natural idea is to assume the contrary: every pair of vectors makes an angle at least $45^\circ$. Then the corresponding points on the unit sphere are pairwise separated by spherical distance at least $\pi/4$.

How many such points can fit on a sphere? Around each point, draw a spherical cap of angular radius $\pi/8$. Because the centers are at least $\pi/4$ apart, these caps are disjoint. The problem becomes an area estimate.

For a unit sphere, a spherical cap of angular radius $\alpha$ has area

$$2\pi(1-\cos\alpha).$$

With $\alpha=\pi/8$, each cap has area

$$2\pi!\left(1-\cos\frac{\pi}{8}\right).$$

If there were $30$ vectors, the total area of the disjoint caps would be

$$60\pi!\left(1-\cos\frac{\pi}{8}\right).$$

The whole sphere has area $4\pi$. Hence we would need

$$60\pi!\left(1-\cos\frac{\pi}{8}\right)\le4\pi,$$

or

$$15!\left(1-\cos\frac{\pi}{8}\right)\le1.$$

Numerically,

$$\cos\frac{\pi}{8} =\sqrt{\frac{1+\cos(\pi/4)}2} =\frac{\sqrt{2+\sqrt2}}2,$$

so

$$1-\cos\frac{\pi}{8}\approx0.0761.$$

Then

$$15!\left(1-\cos\frac{\pi}{8}\right)\approx1.14>1,$$

a contradiction.

The only delicate point is the disjointness of the caps. One must justify that two points lying in different caps would otherwise force the cap centers to be less than $\pi/4$ apart, using the triangle inequality on the sphere.

The argument appears complete.

Problem Understanding

We are given $30$ nonzero vectors in three-dimensional space. We must prove that some pair of them forms an angle strictly smaller than $45^\circ$.

This is a Type B problem, a pure proof problem.

The core difficulty is to show that it is impossible to place $30$ directions on the unit sphere so that every pair is separated by at least $45^\circ$. The natural tool is a packing argument on the sphere.

Proof Architecture

First, replace each vector by the point where its direction meets the unit sphere; angles between vectors become spherical distances between the corresponding points.

Second, assume for contradiction that every pair of vectors forms an angle at least $45^\circ$; then every pair of corresponding points on the sphere is at spherical distance at least $\pi/4$.

Third, around each point construct a spherical cap of angular radius $\pi/8$ and prove that any two such caps are disjoint, because otherwise the triangle inequality for spherical distances would produce two centers less than $\pi/4$ apart.

Fourth, compute the area of one cap as $2\pi(1-\cos(\pi/8))$ and compare the total area of $30$ disjoint caps with the area $4\pi$ of the unit sphere.

The lemma most likely to fail under scrutiny is the disjointness of the caps, since it requires a careful use of spherical distances.

Solution

Let each nonzero vector be replaced by the unit vector having the same direction. Thus we obtain $30$ points on the unit sphere $S$.

Assume, seeking a contradiction, that the angle between any two of the given vectors is at least $45^\circ$. Then the spherical distance between any two corresponding points of $S$ is at least

$$\frac{\pi}{4}.$$

For each of the $30$ points, consider the spherical cap consisting of all points of $S$ whose spherical distance from the center does not exceed

$$\frac{\pi}{8}.$$

These caps are pairwise disjoint. Indeed, suppose two such caps with centers $A$ and $B$ had a common point $P$. Then

$$d(A,P)\le\frac{\pi}{8}, \qquad d(B,P)\le\frac{\pi}{8},$$

where $d$ denotes spherical distance. By the triangle inequality on the sphere,

$$d(A,B)\le d(A,P)+d(P,B)\le\frac{\pi}{4}.$$

If equality held throughout, then $P$ would lie on a shortest geodesic from $A$ to $B$ and both inequalities above would be equalities. In that case $P$ belongs only to the boundaries of the two caps. Consequently the interiors of the caps are disjoint. Since area is unaffected by boundary intersections, the total area of the caps is the sum of their areas.

The area of a spherical cap of angular radius $\alpha$ on the unit sphere equals

$$2\pi(1-\cos\alpha).$$

For

$$\alpha=\frac{\pi}{8},$$

each cap has area

$$2\pi!\left(1-\cos\frac{\pi}{8}\right).$$

Hence the total area of the $30$ caps is

$$60\pi!\left(1-\cos\frac{\pi}{8}\right).$$

Since all caps lie on the unit sphere, whose area is $4\pi$, we must have

$$60\pi!\left(1-\cos\frac{\pi}{8}\right)\le4\pi.$$

After dividing by $4\pi$,

$$15!\left(1-\cos\frac{\pi}{8}\right)\le1.$$

Now

$$\cos\frac{\pi}{8} = \sqrt{\frac{1+\cos(\pi/4)}2} = \frac{\sqrt{2+\sqrt2}}2.$$

Therefore

$$15!\left(1-\cos\frac{\pi}{8}\right) = 15!\left(1-\frac{\sqrt{2+\sqrt2}}2\right).$$

Since

$$\frac{\sqrt{2+\sqrt2}}2<\frac{14}{15},$$

which is equivalent to

$$225(2+\sqrt2)<392,$$

or

$$225\sqrt2< -58+392 = 167,$$

and the last inequality follows from

$$2<\left(\frac{167}{225}\right)^2 \quad\text{being false},$$

we instead compute directly:

$$\cos\frac{\pi}{8}\approx0.9239.$$

Thus

$$15!\left(1-\cos\frac{\pi}{8}\right)\approx1.1415>1.$$

This contradicts the previous inequality.

The contradiction shows that our assumption was impossible. Hence among the $30$ vectors there exist two whose angle is less than $45^\circ$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the passage from vectors to points on the unit sphere. Multiplying a nonzero vector by a positive scalar does not change its direction, and the angle between two vectors depends only on their directions. Thus the problem is equivalent to a statement about $30$ points on the unit sphere.

The second delicate step is the disjointness of the spherical caps. If a point $P$ belonged to the interiors of two caps centered at $A$ and $B$, then

$$d(A,P)<\frac{\pi}{8}, \qquad d(B,P)<\frac{\pi}{8}.$$

The triangle inequality would give

$$d(A,B)<\frac{\pi}{4},$$

contradicting the assumption. Boundary contacts may occur when $d(A,B)=\pi/4$, but such contacts have zero area and do not affect the area estimate.

The third delicate step is the area comparison. The area of a cap of angular radius $\alpha$ is

$$2\pi(1-\cos\alpha).$$

Substituting $\alpha=\pi/8$ gives approximately

$$0.15224\pi.$$

Multiplying by $30$ yields approximately

$$4.567\pi,$$

which exceeds the total sphere area $4\pi$. This numerical check confirms that the contradiction is genuine.

Alternative Approaches

One may formulate the argument in terms of solid angles. Around each direction draw a circular cone of half-angle $22.5^\circ$. If every pair of vectors formed angles at least $45^\circ$, the interiors of these cones would be disjoint. Intersecting the cones with the unit sphere produces exactly the spherical caps used above, and the contradiction follows from the same area computation.

Another approach uses known bounds for spherical codes. A set of points on the unit sphere with mutual angular separation at least $45^\circ$ has size at most $29$. Applying this result immediately yields the statement. The area-packing proof is preferable because it is elementary and derives the required bound directly.