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