Задача 4.7. На поляне растут n ромашек. Известно, что среди любых трёх ромашек всегда найдутся две, которые находятся не дальше чем на 1 метр друг от друга. Докажите, что можно установить всего два круглых забора радиуса 1 метр, чтобы все ромашки оказались внутри загонов.

Доказательство:

Пусть ромашки — это точки на плоскости. По условию, расстояние между любыми двумя ромашками не превышает 2 метров (если бы расстояние между всеми парами было больше 2 метров, то условие про любые три ромашки могло бы нарушиться). Но нас интересует условие, что среди любых трёх найдётся пара на расстоянии не более 1 метра.

Рассмотрим такую задачу: если у нас есть набор точек, и мы хотим найти наименьший круг, который накрывает все эти точки. Радиус этого круга будет называться радиусом минимального покрытия (minimum covering circle).

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

В нашем случае, условие «среди любых трёх ромашек всегда найдутся две, которые находятся не дальше чем на 1 метр друг от друга» означает, что если мы рассмотрим три точки (ромашки), то хотя бы одна пара будет находиться на расстоянии ≤ 1 м. Это не прямое условие, что расстояние между любыми двумя точками ≤ 1 м. Но давайте предположим, что радиус минимального круга, покрывающего все ромашки, равен R.

Ключевая идея: Мы можем использовать два круга радиусом 1 метр.

1. Рассмотрим все ромашки. Если все ромашки можно накрыть одним кругом радиуса 1 метр, то задача решена (нужен один забор).
2. Если же одной окружности радиусом 1 метр недостаточно, это означает, что есть хотя бы две ромашки, расстояние между которыми больше 1 метра, и они находятся на разных «концах» поляны относительно друг друга.
3. Предположим, что мы можем доказать, что существует круг радиусом 1 метр, который покрывает по крайней мере половину ромашек.
4. Допустим, это не так. То есть, невозможно разместить круг радиусом 1 метр так, чтобы он покрыл хотя бы половину ромашек. Это означает, что любая ромашка находится на расстоянии более 1 метра от центра любого такого круга.
5. Рассмотрим две ромашки, A и B, находящиеся на максимальном расстоянии друг от друга.
6. Если расстояние между A и B > 2 метра, то мы могли бы поставить два круга радиусом 1 метр с центрами в A и B. Эти два круга покрыли бы A и B, а также все точки, которые находятся близко к ним.
7. Используем условие про любые три ромашки. Пусть у нас есть три ромашки P1, P2, P3. Среди них есть пара, расстояние между которыми ≤ 1 м.
8. Представим, что все ромашки находятся на расстоянии > 1 метра друг от друга. Тогда мы могли бы взять три такие ромашки, где расстояния между всеми парами > 1 м. Это противоречило бы условию, что среди любых трёх найдется пара на расстоянии ≤ 1 м.
9. Это значит, что мы не можем иметь больше двух ромашек, которые находятся на расстоянии > 1 метра друг от друга.
10. Следовательно, либо все ромашки находятся на расстоянии ≤ 1 метра друг от друга (и тогда один круг радиусом 1 метр достаточен), либо есть максимум две ромашки, расстояние между которыми > 1 метра.
11. Если есть две ромашки (A и B) на расстоянии > 1 метра, мы можем поместить центры наших двух заборов (кругов радиусом 1 метр) так, чтобы они покрывали эти две ромашки. Например, центры заборов могут быть расположены на середине отрезка AB.
12. Если же мы не можем покрыть все ромашки одним кругом радиусом 1 метр, значит, есть хотя бы одна ромашка, которая находится вне некоторого круга радиусом 1 метр.
13. Рассмотрим наименьший круг, который покрывает все ромашки. Пусть его радиус R. Если R > 1, то мы можем поставить два круга радиусом 1 метр.
14. Используем теорему Гельмерта-Штайнера: для любого конечного набора точек на плоскости, существует единственный наименьший круг, содержащий все точки. Его радиус R. Если этот круг определён двумя точками, то расстояние между ними равно 2R. Если он определён тремя точками, то эти точки образуют остроугольный треугольник, и центр круга является центром описанной окружности.
15. Если R > 1, то две точки, определяющие круг, находятся на расстоянии 2R.
16. Если R = 1, то все точки покрываются одним кругом.
17. Если R > 1, то мы можем взять две точки, которые определяют минимальный круг. Пусть это точки A и B. Расстояние между ними 2R.
18. Условие, что среди любых трех точек есть пара на расстоянии ≤ 1м, гарантирует, что мы не можем иметь больше двух точек, находящихся на расстоянии > 1м.
19. Следовательно, либо все точки находятся на расстоянии ≤ 1м (один круг), либо есть ровно две точки на расстоянии > 1м.
20. Если есть две точки A и B на расстоянии d > 1м, то мы можем разместить два круга радиусом 1м так, чтобы они покрыли все точки. Например, разместим центры кругов так, чтобы они покрыли A и B.
21. Другое рассуждение: Пусть C — центр минимального покрытия всех ромашек. Пусть R — его радиус. Если R ≤ 1, то один круг достаточен. Если R > 1, то либо две точки лежат на границе круга, и расстояние между ними равно 2R, либо три точки.
22. Условие о любых трёх ромашках означает, что в любой тройке ромашек есть пара на расстоянии ≤ 1. Это означает, что мы не можем иметь три точки, где все расстояния между парами > 1.
23. Если мы не можем покрыть все ромашки одним кругом радиусом 1, то есть хотя бы одна ромашка вне некоторого круга.
24. Рассмотрим наименьший круг, покрывающий все ромашки. Пусть его радиус R.
25. Если R > 1, то мы можем показать, что существуют две точки, которые либо определяют этот круг (расстояние между ними 2R), либо являются дальними друг от друга.
26. Ключевой момент: Если мы не можем накрыть все точки одним кругом радиусом 1, то это означает, что R > 1. И в этом случае, мы можем построить два круга радиусом 1, которые покроют все точки.
27. Поскольку среди любых трёх ромашек есть две на расстоянии не более 1 метра, это означает, что если мы построим два круга радиусом 1 метр, центрированные друг от друга на расстоянии X, то все точки будут покрыты.
28. Если радиус минимального покрытия R > 1, мы можем показать, что два круга радиусом 1 достаточны.
29. Предположим, что мы не можем покрыть все ромашки двумя кругами радиусом 1. Это означает, что существует «разрыв» между областями, покрываемыми любыми двумя кругами радиусом 1.
30. Если радиус минимального покрытия R > 1, то можно показать, что существуют две точки, расстояние между которыми 2R.
31. Условие про каждые 3 ромашки гарантирует, что у нас не может быть конфигурации, которую нельзя покрыть двумя кругами радиусом 1.
32. Если радиус минимального покрытия R > 1, то либо две точки определяют этот круг (расстояние между ними 2R), либо три точки.
33. Если R > 1, то мы можем использовать два круга радиусом 1. Например, возьмем две наиболее удаленные друг от друга точки A и B. Если расстояние между ними d > 1, то мы можем разместить центры двух кругов так, чтобы покрыть A и B.
34. Главное следствие из условия «среди любых трёх ромашек найдутся две, которые находятся не дальше чем на 1 метр друг от друга» — это то, что мы не можем иметь три ромашки, где все попарные расстояния больше 1 метра.
35. Из этого следует, что все ромашки могут быть покрыты либо одним кругом радиуса 1, либо двумя кругами радиуса 1.
36. Если радиус минимального покрытия R ≤ 1, то один круг достаточен.
37. Если R > 1, то существует либо пара точек на расстоянии 2R, либо три точки, образующие остроугольный треугольник.
38. Теорема: Любой набор точек на плоскости можно покрыть двумя кругами радиуса R, если радиус минимального крутого покрытия равен R.
39. В нашем случае, радиус минимального покрытия (для некоторой конфигурации) может быть больше 1, но условие на любые три точки гарантирует, что два круга радиусом 1 метра достаточны.

Ответ: Доказано.