Назад
Задача

Множество M есть объединение k попарно непересекающихся отрезков, лежащих на одной прямой. Известно, что любой отрезок длины, не большей 1, можно расположить на прямой так, чтобы его концы принадлежали множеству M. Докажите, что сумма длин отрезков, составляющих M, не меньше 1/k.

Решение

Обозначим данные отрезки  I1, I2, ... , Ik,  а их длины –  s1, s2, ... , sk.  Рассмотрим семейство Tij всевозможных отрезков, один конец которых принадлежит Ii, а другой конец – Ij. Минимальная длина такого отрезка равна растоянию l между ближайшими вершинами отрезков, а максимальная –  l + si + sj.  Таким образом, числа, выражающие длины отрезков семейства Tij, принадлежат отрезку длины  si + sj.  Длины отрезков семейства Ti, оба конца которых принадлежат Ii, заполняют отрезок длины si. Отсюда получаем, что числа, выражающие длины всех отрезков с концами в множестве M, заполняют несколько отрезков суммарной длины

С другой стороны, по условию эти числа принимают все значения от 0 до 1; отсюда   k(s1+s2+ ... +sk) ≥ 1,   то есть   s1+s2+ ... +sk1/k.
Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

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