Задача 35536

Тема:    [ Покрытия ]

Сложность: 3+ Классы: 8,9,10

Условие

Известно, что множество M точек на прямой может быть покрыто тремя отрезками длины 1.
Каким наименьшим числом отрезков длины 1 можно заведомо покрыть множество середин отрезков с концами в точках множества M?

Подсказка

Если точка A покрыта отрезком  [a, a + 1],  а точка B – отрезком  [b, b + 1],  то середина отрезка AB покрывается отрезком  [^a+b/₂, ^a+b/₂ + 1].

Решение

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

Ответ

Шестью отрезками.

Источники и прецеденты использования

web-сайт

задача