ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73565
Темы:    [ Покрытия ]
[ Круг, сектор, сегмент и проч. ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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

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

Решение

Нам понадобится следующая очевидная лемма. Если два круга диаметров d1 и d2 пересекаются (имеют общую точку), то их можно заключить в один круг диаметра не больше d1+d2 (рис. 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .