Олимпиадная задача по комбинаторной геометрии о покрытии множества точ
Задача
Известно, что множество M точек на прямой может быть покрыто тремя отрезками длины 1.
Каким наименьшим числом отрезков длины 1 можно заведомо покрыть множество середин отрезков с концами в точках множества M?
Решение
Пусть две точки A и B покрыты одним единичным отрезком. Тогда середина отрезка AB также покрыта этим отрезком. Если точка A покрыта единичным отрезком [a, a + 1], а точка B – отрезком [b, b + 1], то середина отрезка AB покрывается единичным отрезком [a+b/2, a+b/2 + 1].
Пример. Обозначим через [a, a + 1], [b, b + 1], [c, c + 1] три отрезка, покрывающие данное множество M. Как показано выше, множество середин отрезков с концами в точках множества M покрывается шестью отрезками [a, a + 1], [b, b + 1], [c, c + 1], [a+b/2, a+b/2 + 1], [a+c/2, a+c/2 + 1], [b+c/2, b+c/2 + 1].
Оценка. Пусть M = [0, 1] ∪ [2, 3] ∪ [6, 7]. Тогда множество середин отрезков с концами в точках множества M – это [0, 5] ∪ [6, 7]. Значит, меньше чем шестью отрезками длины 1 обойтись нельзя.
Ответ
Шестью отрезками.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь