Покрытие конечной системы точек кругами — олимпиадная задача Арнольда

Нам понадобится следующая очевидная лемма.

Если два круга диаметров 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 . Заметим, что поскольку это утверждение доказывается для любой единицы измерения, то (выбрав эту единицу несколько меньше) из него можно легко получить и утверждение, сформулированное в задаче.

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