Задача 73565

Темы:    [ Покрытия ] [ Круг, сектор, сегмент и проч. ]

Сложность: 5- Классы: 8,9,10

Условие

Автор: Арнольд В.И.

Любую конечную систему точек плоскости можно покрыть несколькими непересекающимися кругами, сумма диаметров которых меньше количества точек и расстояние между любыми двумя из которых больше 1. Докажите это.

Расстояние между двумя кругами — это расстояние между их ближайшими точками.

Решение

Нам понадобится следующая очевидная лемма. Если два круга диаметров d₁ и d₂ пересекаются (имеют общую точку), то их можно заключить в один круг диаметра не больше d₁+d₂ (рис. 7 а, б ). Построим круг с центром в каждой из данных N точек, имеющий радиус a ( a несколько больше 1/2 ; точнее значение a выберем ниже). Если среди этих кругов окажутся пересекающиеся, то, пользуюсь леммой, заменим какие-либо два пересекающихся круга (все равно какие) одним покрывающим их кругом. Если среди полученных кругов еще есть пересекающиеся, снова воспользуемся леммой, и т.д. Пусть вообще есть какая-то система кругов, которые: 1) покрывают все данные точки вместе с кругами радиуса a с центрами в этих точках и 2) имеют сумму диаметров не больше N · 2a . Тогда если среди них есть пересекающиеся, то мы можем воспользоваться леммой и построить новую систему из меньшего количества кругов, удовлетворяющую тем же условиям 1), 2), и так до тех пор, пока мы не получим такой системы из k кругов, никакие два из которых не пересекаются. Уменьшим теперь радиус каждого из этих k кругов на величину b , оставив их центры на месте ( b больше 1/2 и меньше a ; точное значение b указано ниже). Тогда полученные k кругов: 1) содержат все данные точки, 2) имеют сумму диаметров не больше N · 2a-k · 2b 2Na-2b , 3) отстоят друг от друга не меньше чем на 2b . Ясно, что если выбрать a и b так, чтобы выполнялись неравенства b; 2Na-2b, 2b>1 , то все требования задачи будут удовлетворены. Достаточно было, например, взять с самого начала a=1/2+ 1/2N и b=1/2+1/4N . Разумеется, такие a и b понадобились только потому, что в условии требуется удовлетворить строгим неравенствам: сумма диаметров меньше N , расстояния между кругами больше 1 . Если бы мы взяли просто a=b=1/2 , то было бы доказано, что наши N точек можно покрыть (при некотором k ) k кругами так, чтобы расстояние между кругами было не меньше 1 , а сумма их диаметров– не больше N-k . Заметим, что поскольку это утверждение доказывается для любой единицы измерения, то (выбрав эту единицу несколько меньше) из него можно легко получить и утверждение, сформулированное в задаче.

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1970
выпуск
Номер	6
Задача
Номер	М30