|
|
 |
Условие
В некой стране 100 городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего 4950 записей).
а) Одна запись стёрлась. Всегда ли можно однозначно восстановить её по остальным?
б) Пусть стёрлись k записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем k всегда можно однозначно восстановить стёршиеся записи?
Решение 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 рёбрами, соответствующими стёртым записям. Этот граф содержит не менее четырёх компонент связности (см. задачу 31098 г).
Зафиксируем по вершине (A, B, C, D) в каждой из этих четырёх компонент. Все расстояния между этими вершинами известны.
Рассмотрим произвольную вершину первой компоненты. Известны её
расстояния до точек B, C, D, следовательно, положение соответствующего города на плоскости определено однозначно. Аналогична ситуация с вершинами оставшихся компонент.
Ответ
а) Не всегда; б) при k = 96.
Замечания
баллы: 2 + 3
