Олимпиадная задача: Восстановление расстояний между городами на плоскости. Теория графов, 10-11 класс

Решение 1:   а) Пусть 98 точек лежат на одной прямой l, а две точки A и B – вне её. Если неизвестно расстояние между A и B, то восстановить его нельзя: при замене точки B на B', симметричную B относительно l, остальные расстояния не изменятся.   б) Индукцией покажем, что для  n ≥ 4  городов  k = n – 4.  База очевидна.

  Шаг индукции. Пусть для n городов стёрто не более  n – 4  записей. Выберем город А, для которого стёрто хотя бы одно расстояние до другого города, и рассмотрим остальные n городов. Между ними стёрто не более  n – 5  расстояний, и по предположению индукции можно восстановить все эти расстояния, а тогда и взаимное расположение этих городов на плоскости. Для города А известны расстояния по крайней мере до трёх городов, и это позволяет однозначно восстановить его расположение.

  Увеличить k до  n – 3  нельзя. Пусть неизвестны расстояния от точки A до всех точек, кроме B и C. Тогда положение точки A определено с точностью до симметрии относительно прямой BC, значит, расстояния от неё до остальных точек не восстанавливаются.

Решение 2:   Рассмотрим граф со 100 вершинами и 96 рёбрами, соответствующими стёртым записям. Этот граф содержит не менее четырёх компонент связности (см. задачу 131098 г). Зафиксируем по вершине  (A, B, C, D)  в каждой из этих четырёх компонент. Все расстояния между этими вершинами известны.

  Рассмотрим произвольную вершину первой компоненты. Известны её расстояния до точек B, C, D, следовательно, положение соответствующего города на плоскости определено однозначно. Аналогична ситуация с вершинами оставшихся компонент.