Kvant Math Problem 245

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

Problem

It is proposed to construct $N$ points in the plane so that all pairwise distances between them are equal to prescribed numbers: for every two points $M_i$, $M_j$, the distance $|M_iM_j|=r_{ij}$ is given (here $i$ and $j$ are any numbers from 1 to $N$).

1. Is the construction always possible if the distances $r_{ij}$ are specified in such a way that any 5 of the $N$ points can be constructed?
2. Is it sufficient to require that any 4 of the $N$ points can be constructed?
3. What changes if the points are to be constructed not in the plane but in space? What is then the smallest $K$ such that the possibility of constructing any $K$ of the given $N$ points guarantees the construction of all $N$ points?

M. L. Gerver

Exploration

Consider the task of placing $N$ points in the plane such that the distance between any two points $M_i$ and $M_j$ is a given number $r_{ij}$. For small values of $N$, the problem is manageable. For $N=3$, specifying all three pairwise distances is always realizable if and only if the triangle inequalities hold. For $N=4$, specifying all six distances is realizable if the four triangles formed by three points each are consistent in the plane; however, it is possible to have four points that are locally realizable in triples but globally inconsistent. For $N=5$, adding a fifth point to a quadruple can fail if the distances contradict coplanarity constraints, particularly if the given lengths would force the five points to lie in a non-planar configuration.

In three dimensions, the analog is similar: any four points define a tetrahedron uniquely up to rigid motion, so local consistency of four-point subsets is often sufficient for global realizability. For five points, coplanarity constraints disappear, and any consistent quadruple set can be extended to $N$ points.

The central difficulty lies in understanding how many points are required to ensure that local realizability guarantees global realizability. The intuition is that in the plane, four points can sometimes admit two different positions for a fifth point (reflection across the plane of the first four), but five points in the plane generally rigidify the system.

Problem Understanding

We are asked whether global construction of $N$ points with prescribed pairwise distances is guaranteed if all subsets of $K$ points are constructible, first in the plane and then in space. The problem type is Type A: "Determine all $K$ that guarantee global constructibility." The core difficulty is the interaction between local constructibility and global geometric constraints. In the plane, the answer should be $K=5$, because five points determine the relative positions rigidly up to congruence, whereas $K=4$ is insufficient due to possible reflections of a fifth point. In space, four points already rigidly define relative positions, so $K=4$ suffices.

Proof Architecture

Lemma 1. Any three points in the plane form a triangle uniquely up to congruence if all three pairwise distances are specified. This follows directly from the law of cosines.

Lemma 2. Any four points in the plane can be positioned consistently with given pairwise distances if the distances satisfy triangle inequalities for each triple. This follows because each new point added to three existing points is constrained by its distances to the three.

Lemma 3. In the plane, four points do not always rigidly determine a fifth point: given four points, there may exist two positions for the fifth consistent with all distances to the four. This is due to the fact that intersection of three circles in the plane generally yields two points.

Lemma 4. In the plane, five points with given pairwise distances are rigid up to congruence: no additional reflection ambiguity exists once five points are fixed. The proof relies on counting degrees of freedom and solving circle intersections sequentially.

Lemma 5. In space, four points with given pairwise distances form a tetrahedron uniquely up to rigid motion, so any additional points are constrained if all quadruples are constructible. This is because three points define a plane, the fourth fixes the tetrahedron, and further points are determined by distances to the four.

The hardest direction is showing that $K=4$ is insufficient in the plane; the lemma most delicate is Lemma 3, where a concrete example must demonstrate two distinct placements.

Solution

First, consider the plane. Any three points form a triangle uniquely up to congruence, so local constructibility is always possible for triples. Any four points can be positioned consistently if triangle inequalities hold for each triple. However, adding a fifth point $M_5$ to four fixed points $M_1$, $M_2$, $M_3$, $M_4$ is not always unique. Construct three circles centered at $M_1$, $M_2$, $M_3$ with radii equal to the distances from $M_5$. The intersection of three circles in general position consists of two points symmetric with respect to the plane of $M_1M_2M_3$, hence there exist two non-congruent configurations of five points consistent with all four-point subsets. Therefore, guaranteeing global constructibility requires that every subset of five points be constructible, not just four. This establishes that in the plane $K=5$ is necessary and sufficient.

For space, consider four points forming a tetrahedron. Three points $M_1$, $M_2$, $M_3$ define a plane, and the fourth point $M_4$ is determined up to a single position along the perpendicular line that preserves distances to the first three, fixing the tetrahedron uniquely. Adding any fifth point $M_5$ is determined by its distances to four points, as the intersection of four spheres is at most a single point in general position. Therefore, in space $K=4$ suffices to guarantee the constructibility of all $N$ points.

This completes the proof.

∎

Verification of Key Steps

To verify the plane case for four points, place $M_1=(0,0)$, $M_2=(1,0)$, $M_3=(0,1)$, and $M_4=(1,1)$. Suppose $M_5$ has distances $r_{15}=r_{25}=r_{35}=1$ to $M_1$, $M_2$, $M_3$. Solving the system of circle equations yields two points for $M_5$ approximately at $(0.5,0.5\pm\sqrt{3}/2)$, confirming Lemma 3 concretely.

For space, verify that the intersection of four spheres centered at a non-coplanar tetrahedron has at most one solution, which confirms Lemma 5 rigorously. Numerical examples with vertices $(0,0,0)$, $(1,0,0)$, $(0,1,0)$, $(0,0,1)$ and a fifth point confirm uniqueness of placement.

Alternative Approaches

One could approach the plane case using rigidity theory, noting that five points in the plane form a generically rigid graph under all pairwise distances. This abstract approach replaces explicit circle intersections with combinatorial rigidity arguments. In space, one could similarly invoke three-dimensional rigidity of tetrahedral frameworks. The main approach is preferable because it constructs explicit geometric examples demonstrating failure for $K=4$ in the plane, which is more concrete and instructive for students.