Докажите, что $N$ точек на плоскости всегда можно покрыть несколькими непересекающимися кругами,
сумма диаметров которых меньше $N$ и расстояние между любыми двумя из которых больше 1.
(Под расстоянием между двумя кругами понимается расстояние между их ближайшими точками.)
Если два круга диаметров $d_1$ и $d_2$ пересекаются (имеют общую
точку), то их можно заключить в один круг диаметра не больше $d_1+d_2$
(рис. 7, а, б).
Рис. 7, аРис. 7, б
Построим круг с центром в каждой из данных $N$ точек, имеющий радиус $a$
($a$ несколько больше $\dfrac12$; точнее значение $a$ выберем ниже). Если
среди этих кругов окажутся пересекающиеся, то, пользуясь леммой, заменим
какие-либо два пересекающихся круга (всё равно какие) одним покрывающим их кругом. Если среди полученных кругов ещё есть пересекающиеся, снова
воспользуемся леммой, и т. д. Пусть вообще есть какая-то система кругов,
которые:
покрывают все данные точки вместе с кругами радиуса $a$ с центрами в этих точках и
имеют сумму диаметров не больше $N\cdot2a$.
Тогда если среди них есть пересекающиеся, то мы можем воспользоваться леммой
и построить новую систему из меньшего количества кругов, удовлетворяющую тем же условиям 1), 2), и так до тех пор, пока мы не получим такой системы из $k$ кругов, никакие два из которых не пересекаются.
Уменьшим теперь радиус каждого из этих $k$ кругов на величину $b$,
оставив их центры на месте ($b$ больше $\dfrac12$, и меньше $a$; точное
значение $b$ указано ниже). Тогда полученные $k$ кругов:
содержат все данные точки,
имеют сумму диаметров не большe $N\cdot2a-k\cdot2b\le2Na-2b$,
отстоят друг от друга не меньше чем на $2b$.
Ясно, что если выбрать $a$ и $b$ так, чтобы выполнялись неравенства
$b\lt a$, $2Na-2b\lt N$, $2b\gt1$, то все требования задачи будут
удовлетворены. Достаточно было, например, взять с самого начала
$a=\dfrac12+\dfrac1{2N}$ и $b=\dfrac12+\dfrac1{4N}$.
Разумеется, такие $a$ и $b$ понадобились только потому, что в условии требуется удовлетворить строгим
неравенствам: сумма диаметров меньше $N$, расстояния между кругами больше 1. Если бы мы взяли просто $a=b=\dfrac12$, то было бы доказано, что наши $N$ точек можно покрыть (при некотором $k$) $k$
кругами так, чтобы расстояние между кругами было не меньше 1, а сумма их диаметров — не больше $N-k$. Заметим, что поскольку это утверждение
доказывается для любой единицы измерения, то (выбрав эту единицу несколько меньше) из него можно легко получить и утверждение, сформулированное в задаче.
