ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35536
Тема:    [ Покрытия ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Подсказка

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


Решение

  Пусть две точки 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 обойтись нельзя.


Ответ

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

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .