Problem 1. (5 points) In a country, there are 100 cities, which we consider as points in a plane. In a directory, the distance between each pair of cities is listed (4950 distances are listed).

a) One of the distances is erased. Can it always be uniquely restored using the remaining ones?

b) Suppose $k$ distances are erased and it is known that no three cities lie on the same line. What is the largest value of $k$ for which the erased distances can always be uniquely restored?
Solution. a) Not always. Let 98 points lie on a straight line $l$, and two points $A$ and $B$ are outside the line, and they are not symmetric with respect to it. If only the distance between $A$ and $B$ is unknown, it cannot be restored, since by replacing $B$ with $B_{1}$ - its symmetric with respect to $l$, only the distance between $A$ and $B$ changes.

b) We will prove that $\mathrm{k}=96$. By induction on $n$ we will prove that for $n \geq$ 4 we have $k=n-4$. For $n=4$ the statement can be verified directly. Suppose it is true for some $n$ and consider $n+1$ cities. If we erase the distances from a given city to $n-2$ cities, we will know the distances from $A$ only to two cities - $B$ and $C$. By replacing $A$ with its symmetric with respect to the line through $B$ and $C$, we will preserve the distances to $B$ and $C$, all known distances will not change, and the unknown distances will change (since there are no other cities on the line $B C$). Therefore, $k \geq n-3$.

Suppose no more than $n-3$ distances are erased. Choose a city $A$ from which at least one distance is erased and consider the remaining $n$ cities. Among them, no more than $n-4$ distances are erased, and from the inductive hypothesis it follows that all distances can be restored. Then we will know the relative positions of these $n$ cities. For city $A$, we will know the distances to at least 3 other cities (which do not lie on a straight line), which allows us to uniquely determine the position of $A$ in the plane. Therefore, we can find the distances from $A$ to all other cities.