Top.Mail.Ru

Часто ищут

Разделы

Бесплатно

Тема . Графы и турниры

Паросочетания и лемма Холла

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела графы и турниры
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#82774

На конференцию приехали 300  математиков, каждый знает 3  языка из 5  разрешенных на конференции. Докажите, что их можно разбить на три секции по 100  человек, говорящих на одном языке.

Подсказки к задаче

Подсказка 1

Попробуем реализовать следующую идею: возьмем три самых популярных языка (назовем их первым, вторым и третьим) и рассмотрим граф, в котором только эти три языка и все математики. Если найти в нем паросочетание, то распределить математиков на группы легко. А как доказать, что в этом графе есть паросочетание?

Подсказка 2

Рассмотрим любых k математиков. В случае k ≤ 100 условие леммы Холла очевидно. Попробуем разбить доказательство еще на два случая: 101 ≤ k ≤ 200 и 201 ≤ k ≤ 300. Предположим, что в первом из этих двух случаев условие леммы Холла не выполняется. Что тогда можно сказать о языковых знаниях математиков?

Подсказка 3

Действительно, условие леммы Холла не выполнится, только если все эти k математиков знают ровно 1 язык. Попробуем доказать, что это невозможно. Для этого пойдем от непопулярных языков: пусть пятый язык знают меньше всего людей. Если его знают более 100 человек, то четвертый язык - язык, который знают меньше всего людей после пятого, а в если не более 100 человек, то это язык, который знает меньше всего людей среди знающих пятый (в этот момент мы начинаем полагать, что 1, 2 и 3 языки являются просто всеми остальными). Теперь нам фактически нужно оценить число людей, знающих одновременно четвертый и пятый язык. Как это сделать?

Подсказка 4

Все верно! В первом случае это сразу ясно, а во втором это оценивается так: люди знают всего 900 языков (3 * 300 = 900), тогда пятый язык знают не более 900/5 < 200 человек, тогда эти люди знают менее 400 языков, помимо пятого, следовательно, сам четвертый язык знают менее 400/4 = 100 человек. Тогда невыполнение леммы Холла в случае 101 ≤ k <= 200 невозможно. А при каких условиях она может не выполняться для случая 201 ≤ k < 300?

Подсказка 5

Верно! Лемма Холла неверна, только если все эти k математиков не знают какой-то из языков: 1-ый, 2-ой или 3-ий. Однако меньше всего математиков знают пятый язык. Тогда в этом случае пятый язык знают менее ста человек. Как можно теперь доказать, что этот случай невозможен?

Подсказка 6

Пусть все эти k математиков не знают третий язык. Тогда его знает не более 300-k человек. Из наших k математиков не более 100 знают пятый язык, а можно ли тогда оценить число знающих четвертый язык и использовать условие его выбора для этой ситуации?

Сообщить об ошибке
Подсказки
Доказательство
Сообщить об ошибке

Специальные программы

Все специальные программы

Программа
лояльности вер. 2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к твоему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас важно быть полезными учителям по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!