Bogdanov I.I.

In a certain country, there are 100 cities (consider the cities as points on a plane). In a directory, for each pair of cities, there is a record of the distance between them (a total of 4950 records).

a) One record has been erased. Can it always be uniquely restored from the remaining ones?

b) Suppose $k$ records have been erased, and it is known that no three cities in this country lie on the same straight line. For what largest $k$ can the erased records always be uniquely restored?

#
a) Let 98 points lie on a straight line $l$, and two points $A$ and $B$ lie outside it. If the distance between $A$ and $B$ is unknown, it cannot be restored: by replacing point $B$ with $B^{\prime}$, symmetric to $B$ relative to $l$, the other distances will not change.
b) By induction, we will show that for $n \geq 4$ cities, $k=n-4$. The base case is obvious.

Inductive step. Suppose for $n$ cities, no more than $n-4$ records are erased. Choose a city $A$ for which at least one distance to another city is erased, and consider the remaining $n$ cities. Between them, no more than $n-5$ distances are erased, and by the inductive hypothesis, all these distances can be restored, and thus the relative positions of these cities on the plane. For city $A$, at least three distances to other cities are known, which allows us to uniquely determine its position.

Increasing $k$ to $n-3$ is not possible. If the distances from point $A$ to all points except $B$ and $C$ are unknown, then the position of point $A$ is determined up to symmetry relative to the line $B C$, meaning the distances from it to the other points cannot be restored.

## Answer

a) Not always; b) for $k=96$.

Submit a comment