Для охраны объекта в течение одной рабочей недели (5 суток) заказчик заключил договор с бригадой охранников. По договору каждый член бригады указывает один промежуток своего времени предполагаемого дежурства (в данную рабочую неделю) так, что в итоге объект всегда находится под охраной, после чего заказчик оставляет любую часть охранников, которая обеспечивает круглосуточную охрану, и оплачивает их работу из расчета 500 руб. в час каждому. Какую наименьшую сумму денег нужно подготовить заказчику заранее для гарантированной оплаты бригаде?

задан 26 Фев 18:30

10|600 символов нужно символов осталось
0

Пусть дан отрезок $%[a,b]$%, покрытый конечным числом отрезков. Выбираем самый длинный из этих отрезков, содержащий точку $%a$%. Пусть это $%[a,c]$%. Если $%c < b$%, то из всех отрезков покрытия, содержащих $%c$% не в качестве своего правого конца, выбираем наибольший по длине. Объединение выбранных отрезков будет равно $%[a,d]$%, где $%a < c < d$%, и так далее. В конечном счёте мы за конечное число шагов доберёмся до $%b$%.

В полученной системе отрезков, никакая точка из $%[a,b]$% не покрывается более чем двумя выбранными отрезками покрытия. В самом деле, если рассмотреть соседние выбранные отрезки, то они перекрываются по какому-то отрезку -- возможно, одноточеченому. Это значит, что они имеют вид $%[x,z]$% и $%[y,t]$%, где $%x < y\le z < t$%. Следующий по очереди отрезок, который мы выбирали, покрывает $%t$% вместе с какой-то окрестностью правее $%t$%. Тогда он не может пересекаться с общей частью $%[y,z]$% двух первых отрезков, так как он длиннее, чем $%[y,t]$%, и также покрывает точку $%z$%.

Таким образом, можно выбрать дежурных так, чтобы в каждый момент дежурили максимум двое. Это значит, что денег из расчёта 1000 руб. в час заведомо хватит, и на 5 суток придётся 120 тысяч.

Меньшей суммой не обойтись, и пример легко привести: пусть охранника всего два, и первый пожелал дежурить от начала почти до конца, уйдя за время $%t$% до истечения пяти суток. Второй приходит через время $%t$% после начала, и уходит в самом конце. Тогда обязательно привлечение того и другого, и это сколь угодно близко к двойной оплате, так как $%t$% можно устремить к нулю.

ссылка

отвечен 26 Фев 19:32

Второй раз встречаюсь с другой формулировкой подобной задачи.

(28 Фев 6:00) Верик

@Верик: имеется в виду переформулировка на языке покрытия отрезками?

(28 Фев 9:35) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×71

задан
26 Фев 18:30

показан
369 раз

обновлен
28 Фев 9:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru