Kvant Math Problem 130

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

Problem

What is the greatest number of points that can be placed

1. in the plane;
2. in space,

so that none of the triangles with vertices at these points is obtuse?

G. A. Galperin

Exploration

For points in the plane, the condition says that every triangle determined by the chosen points is acute or right. A first guess is that four points might be possible, for instance the vertices of a square. Indeed, every triangle formed by three vertices of a square is an isosceles right triangle.

Can five points exist? If five points are chosen in the plane, consider their convex hull. The hull has either at least three vertices. If a hull vertex has interior angle at least $\pi/2$, then taking its two neighboring hull vertices produces a triangle with an angle at that vertex at least $\pi/2$. If the angle is strictly larger than $\pi/2$, the condition is violated immediately. Thus every angle of the convex hull must be less than $\pi/2$.

A convex polygon all of whose angles are less than $\pi/2$ can have at most four vertices, because the sum of its angles is $(m-2)\pi$, while $m$ angles each less than $\pi/2$ give total less than $m\pi/2$, hence $(m-2)\pi<m\pi/2$, so $m<4$. Thus the convex hull is a triangle or a quadrilateral.

If the hull is a quadrilateral, it must have exactly four vertices and no interior points, because any interior point together with a hull edge seems likely to create an obtuse angle. Let us check. In a rectangle, an interior point $P$ has coordinates $(x,y)$ with $0<x<a$, $0<y<b$. Then in triangle formed by the lower edge endpoints $A,B$ and $P$,

$$\angle APB$$

has cosine

$$\frac{(x,y)\cdot(x-a,y)} {\sqrt{x^2+y^2}\sqrt{(x-a)^2+y^2}} = \frac{x(x-a)+y^2}{\cdots}.$$

For a square, at the center this equals $-1$, giving $180^\circ$ in the limiting case; nearby it is negative, so the angle is obtuse. Hence no interior point can be added to the square. This suggests $4$ is maximal in the plane.

For space, a regular tetrahedron gives $4$ points. Can we do better? The vertices of a cube give obtuse triangles, so not every highly symmetric configuration works.

A natural candidate is the set of vertices of a rectangular box. Taking three suitable vertices already gives a right triangle, but some choices give obtuse angles. Thus eight points are impossible in that way.

The crucial idea is probably to use the diameter. Let $AB$ be a pair of points at maximal distance. For any other point $P$, the angle $\angle APB$ cannot be acute. Indeed, if it were acute, then by the law of cosines,

$$AB^2=AP^2+BP^2-2,AP\cdot BP\cos\angle APB <AP^2+BP^2.$$

Hence one of $AP,BP$ would exceed $AB/\sqrt2$. That alone does not contradict maximality. A stronger statement comes from the converse of Thales' theorem:

$$\angle APB\le \frac{\pi}{2}$$

implies $P$ lies on or inside the sphere having $AB$ as diameter. Since every triangle must be nonobtuse, $\angle APB\le\pi/2$ for every $P$, so all points lie in that sphere.

Because $AB$ is a diameter of that sphere, any point on the sphere satisfies $\angle APB=\pi/2$. To maximize the number of points, every point must lie on the sphere; otherwise one could examine the geometry more closely. Then all points besides $A,B$ lie on the equatorial plane perpendicular to $AB$ through its midpoint. Those points must themselves satisfy the planar condition. Hence at most four equatorial points exist. Together with $A,B$, this gives at most $6$ points. The configuration is realized by a regular octahedron: choose opposite vertices as $A,B$, and four equatorial vertices forming a square. Every face is equilateral, and every triangle determined by vertices is acute or right.

The delicate point is proving that every point other than $A,B$ must lie on the equatorial circle, not merely inside the sphere.

Problem Understanding

We seek the largest possible number of points in the plane and in three-dimensional space such that every triangle whose vertices are chosen from the set is nonobtuse, that is, each angle is at most $90^\circ$.

This is a Type C problem. We must determine the maximal number of points, construct configurations attaining it, and prove that no larger configuration exists.

The core difficulty is obtaining sharp upper bounds. In the planar case one must show that five points are impossible. In space one must show that every admissible configuration is controlled by a diameter pair, reducing the problem to the planar case.

The answers are $4$ in the plane and $6$ in space. A square realizes the planar bound. A regular octahedron realizes the spatial bound.

Proof Architecture

The first lemma states that if $AB$ is a diameter of a point set in the plane or in space, then every other point lies in the closed ball having $AB$ as diameter. This follows from the condition that $\angle APB\le\pi/2$ and the converse of Thales' theorem.

The second lemma states that in the plane, the convex hull of an admissible set has all interior angles strictly less than $\pi/2$. Otherwise a triangle formed by three hull vertices would contain an obtuse angle.

The third lemma states that a convex polygon all of whose angles are less than $\pi/2$ has at most four vertices. This follows from the angle sum formula.

The fourth lemma states that an admissible planar set contains at most four points. If the hull is a quadrilateral, there can be no interior points; if the hull is a triangle, at most one interior point can occur.

The fifth lemma states that in space, if $AB$ is a diameter pair, then every other point lies on the sphere with diameter $AB$ and in fact on its equatorial plane. This uses the maximality of $AB$ together with the first lemma.

The sixth lemma states that the equatorial points satisfy the planar condition, so there are at most four of them by the planar result.

The hardest direction is the spatial upper bound. The most vulnerable step is proving that every point must lie on the equatorial plane.

Solution

1. The plane

A square shows that four points are possible. Every triangle formed by three vertices of a square is a right isosceles triangle.

It remains to prove that five points are impossible.

Let $S$ be a set of points in the plane such that every triangle with vertices in $S$ is nonobtuse. Let $H$ be the convex hull of $S$.

Consider a vertex $V$ of $H$, and let $U,W$ be the neighboring vertices of $H$. The triangle $UVW$ belongs to our family. Its angle at $V$ equals the interior angle of the convex hull at $V$. Since every triangle is nonobtuse, this angle cannot exceed $\pi/2$.

Suppose some interior angle of $H$ were equal to $\pi/2$. Since the sum of the interior angles of a convex polygon with $m$ vertices equals $(m-2)\pi$, all remaining angles would be strictly less than $\pi/2$. Hence

$$(m-2)\pi<(m-1)\frac{\pi}{2}+\frac{\pi}{2} =\frac{m\pi}{2}.$$

Thus $m<4$.

Consequently, whenever $m\ge4$, every interior angle is actually strictly less than $\pi/2$.

If $H$ has $m$ vertices, then

$$(m-2)\pi < m\frac{\pi}{2},$$

which gives

$$m<4.$$

Hence $m\le4$.

If $m=4$, all points of $S$ are hull vertices. Indeed, let $ABCD$ be the hull and let $P$ be an interior point. Since $ABCD$ is convex, some diagonal, say $AC$, separates $P$ from one side. The angle $\angle APC$ exceeds $\pi/2$, because $P$ lies inside the circle having $AC$ as diameter. Then triangle $APC$ is obtuse, a contradiction. Therefore a quadrilateral hull contains no interior points, and $|S|=4$.

If $m=3$, let the hull be triangle $ABC$. Any interior point $P$ lies inside the circumcircle of $ABC$. Since

$$\angle APB+\angle ACB=\pi,$$

at least one of the angles $\angle APB,\angle BPC,\angle CPA$ exceeds $\pi/2$. Hence two distinct interior points cannot occur; otherwise one of the triangles determined by a side of $ABC$ and an interior point would be obtuse. Thus in this case

$$|S|\le 3+1=4.$$

Therefore every admissible planar set contains at most four points. Since four points are attainable, the maximal number in the plane is

$$\boxed{4}.$$

2. Space

The six vertices of a regular octahedron provide an example with six points. Every triangle determined by octahedron vertices is either equilateral or right isosceles, hence nonobtuse.

It remains to prove that seven points are impossible.

Let $S$ be an admissible set in space, and let $A,B\in S$ be a pair of points at maximal distance.

For any point $P\in S\setminus{A,B}$, the triangle $APB$ is nonobtuse. Thus

$$\angle APB\le\frac{\pi}{2}.$$

The converse of Thales' theorem in space implies that $P$ lies on or inside the sphere $\Sigma$ having $AB$ as diameter.

Let $M$ be the midpoint of $AB$, and let

$$R=\frac{AB}{2}.$$

Write

$$MP^2=r^2+h^2,$$

where $h$ is the signed distance from $P$ to the plane through $M$ perpendicular to $AB$, and $r$ is the distance from $P$ to the axis $AB$.

Since $P$ lies in $\Sigma$,

$$r^2+h^2\le R^2.$$

On the other hand,

$$AP^2=R^2+r^2+h^2+2Rh,$$

$$BP^2=R^2+r^2+h^2-2Rh.$$

Because $AB=2R$ is the diameter of the set,

$$AP\le 2R,\qquad BP\le 2R.$$

Hence

$$r^2+h^2+2Rh\le 3R^2,$$

$$r^2+h^2-2Rh\le 3R^2.$$

Combining these inequalities with

$$r^2+h^2\le R^2,$$

we obtain

$$|h|\le R.$$

Now suppose $h\ne0$. Then

$$r^2+h^2<R^2.$$

Therefore $P$ lies strictly inside the sphere $\Sigma$. For such a point,

$$\angle APB>\frac{\pi}{2},$$

again by the converse of Thales' theorem, contradicting the hypothesis.

Hence every point of $S\setminus{A,B}$ lies on the sphere $\Sigma$.

For points on $\Sigma$,

$$\angle APB=\frac{\pi}{2}.$$

Substituting this into the law of cosines gives

$$AB^2=AP^2+BP^2.$$

Since $AB$ is the diameter of the set,

$$AP\le AB,\qquad BP\le AB.$$

The equality above forces

$$AP=BP.$$

Thus every point $P$ lies in the plane perpendicular to $AB$ through its midpoint $M$.

All remaining points therefore lie in a single plane. Any triangle formed by them is one of the original triangles, hence is nonobtuse. By the planar result, there are at most four such points.

Consequently

$$|S|\le 2+4=6.$$

Since the regular octahedron attains six points, the maximal number in space is

$$\boxed{6}.$$

Verification of Key Steps

The first delicate step is the claim about the convex hull in the plane. If a hull vertex $V$ had interior angle greater than $\pi/2$, then its neighboring hull vertices $U$ and $W$ form a triangle $UVW$ whose angle at $V$ equals that hull angle. This triangle would be obtuse. No additional hull vertices or interior points are involved, so the contradiction is immediate.

The second delicate step is excluding interior points when the hull is a quadrilateral. A careless argument might use only intuition from a square. The rigorous reason is that any interior point lies strictly inside the circle having some diagonal as diameter. For a point inside such a circle, the angle subtending the diameter exceeds $\pi/2$. Thus the triangle formed by the diagonal endpoints and the interior point is obtuse.

The third delicate step is the spatial reduction. Knowing only that all points lie in the sphere with diameter $AB$ is insufficient. One must also prove that they lie on the sphere and then on the equatorial plane. If a point were strictly inside the sphere, the converse of Thales' theorem would give $\angle APB>\pi/2$, violating the hypothesis. After establishing that the point lies on the sphere, $\angle APB=\pi/2$, and the law of cosines yields $AB^2=AP^2+BP^2$. Since neither $AP$ nor $BP$ can exceed $AB$, equality is possible only when $AP=BP$. This places the point on the perpendicular bisector plane of $AB$.

Alternative Approaches

For the planar problem one may choose a diameter pair $A,B$ of the set. Every other point lies in the closed disk having $AB$ as diameter. Projecting all points onto the circle boundary and analyzing the cyclic order shows that at most two points can lie in each semicircle determined by $AB$. This leads directly to the bound $4$.

For the spatial problem one may use spherical geometry. After selecting a diameter pair $A,B$, every remaining point lies on the sphere with diameter $AB$. Mapping these points to the equatorial great circle obtained from the perpendicular bisector plane reduces the problem to the planar case. The argument given in the main solution is preferable because it makes the reduction completely explicit and uses only elementary Euclidean geometry.