Паросочетания и лемма Холла
Ошибка.
Попробуйте повторить позже
теннисистов сыграли 
партий так, что каждый участвовал хотя бы в одной. Докажите, что найдутся 
партий, в которых
участвовали 
различных теннисистов.
Подсказка 1
Попробуем построить граф, в котором ребра — партии, а вершины — теннисисты. Пусть в его максимальном паросочетании x ребер. Тогда в нем 2x вершин. А можно ли оценить число ребер, которые выходят из оставшихся 200 - 2x вершин?
Подсказка 2
Ясно, что между этими теннисистами не может быть ребер, а иначе рассматриваемое паросочетание не является максимальным! При этом у каждой вершины есть по ребру, так что все они выходят в наше паросочетание. А сколько этих ребер?
Подсказка 3
Верно, 200 - 2x! А можем ли мы теперь снизу оценить число ребер и использовать число ребер из условия?
Построим граф, вершинами которого будут теннисисты, а ребрами — партии (кратные ребра разрешены). Рассмотрим максимальное
паросочетание. Пусть в нем 
ребер, то есть 
теннисистов. Рассмотрим оставшихся 
теннисистов. Между ними не может быть
ребер, иначе наше паросочетание было бы не максимальным. Но по условию из каждой вершины выходит хотя бы одно ребро. Тогда из этих
вершин выходит хотя бы 
ребер в выбранное паросочетание. Тогда всего ребер не меньше, чем 
откуда 
что и требовалось доказать.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
