Условие
Докажите, что любые n точек на плоскости всегда можно накрыть
несколькими непересекающимися кругами так, что сумма их
диаметров меньше n и расстояние между любыми двумя из них
больше 1.
Решение
Построим круги с центрами в данных точках радиуса
a = 1/2 + 1/2n.
Ясно, что пересекающиеся круги радиусов R1 и R2 можно
заключить в круг радиуса не более R1 + R2. Будем так делать до
тех пор, пока не получатся непересекающиеся круги. Все данные
точки расположены на расстоянии не меньше a от границ этих
кругов, поэтому их радиусы можно уменьшить на b < a, и при этом
они по-прежнему будут покрывать все данные точки. Если кругов
k штук, то сумма их диаметров не больше
n . 2a - k . 2b
2na - 2b. Нам нужно, чтобы выполнялись следующие условия:
2na - 2b < n и 2b > 1. Они выполняются, если
a = 1/2 + 1/2n и
b = 1/2 + 1/4n.
Источники и прецеденты использования
