На прямой даны ml+1 отрезков. Докажите что можно либо выбрать m+1 отрезков имеющих общую точку либо выбрать l+1 никакие два из которых не пересекаются.

задан 16 Янв 19:58

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

Если два отрезка не пересекаются, то один из них находится строго левее другого. Тем самым, мы имеем частичное упорядочение множества отрезков по этому принципу. По следствию из теоремы Дилворта, которая несложно доказывается по индукции, в множестве найдётся либо цепь длиной L+1, либо антицепь длиной M+1. Первое -- это система из L+1 отрезка, которые попарно не пересекаются. Второе -- это система из M+1 отрезка, любые два из которых пересекаются. Тогда остаётся сослаться на частный случай теоремы Хелли для отрезков на прямой, получая, что все M+1 отрезков имеют общую точку.

Можно кратко напомнить доказательство. Среди левых концов берём максимальный, а среди правых -- минимальный. Пусть это числа x и y. Если x<=y, то любая точка отрезка [x,y] подходит. Если же x > y, то отрезок с левым концом x не пересекает отрезок с правым концом y.

ссылка

отвечен 16 Янв 20:24

1

@falcao: Здесь в точности то же самое, что Вы написали, только имена авторов теорем почему-то другие)

http://www.mathschool.ru/storage/SCContent/762/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D1%8B_%D0%94%D0%B8%D0%BB%D1%83%D0%BE%D1%80%D1%81%D0%B0_%D0%B8_%D0%9C%D0%B8%D1%80%D1%81%D0%BA%D0%BE%D0%B3%D0%BE.pdf

(16 Янв 20:29) goldish09
1

@goldish09: Дилуорс -- это другая транскрипция той же фамилии Dilworth. Теоремой его имени часто называют следствие про существование длинной цепи или антицепи. Второе имя на ту же тему мне раньше не попадалось. А теорема Хелли -- она идёт как бы совсем отдельно.

(16 Янв 20:40) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,019
×480
×322

задан
16 Янв 19:58

показан
226 раз

обновлен
16 Янв 20:40

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

по почте:

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

по RSS:

Ответы

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

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