Top.Mail.Ru

Часто ищут

Разделы

Бесплатно

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

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

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

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

Задача 1#175097Максимум баллов за задание: 7

Фокусник и его ассистент готовятся показать следующий фокус. У них есть колода из 2026 различных карт. Они сообщают зрителю натуральное число k≤ 1013.  Зритель выбирает k  произвольных карт из колоды, убирает их в конверт и заклеивает его. Затем ассистент выбирает k  карт из оставшихся и передает их зрителю. Тот перетасовывает эти карты как хочет и отдает фокуснику. Задача фокусника — отгадать карты, которые лежат в конверте. Для каких k  фокусник и ассистент могут договориться действовать так, чтобы фокус гарантированно удался?

Источники: ВП - 2026, 11.1 (см. olymp.hse.ru)

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

Подсказка 1

Ассистент видит k карт зрителя. Что он должен показать, чтобы фокусник восстановил набор?

Подсказка 2

Попробуйте представить процесс как соответствие между наборами. Как можно изобразить такое соответствие?

Подсказка 3

Используйте граф: вершины одной доли — наборы зрителя, другой — наборы ассистента. Когда между ними стоит проводить ребро?

Подсказка 4

Когда наборы не пересекаются. Сколько соседей будет у каждой вершины?

Подсказка 5

Степень равна Cₙⁿ⁻ᵏ. Что можно сказать про доли и сам граф?

Подсказка 6

Лемма Холла: паросочетание, покрывающее все вершины левой доли, существует, если для любого множества X наборов зрителя число соседей (наборов ассистента, не пересекающихся хотя бы с одним набором из X) не меньше |X|. В регулярном графе с равными долями это условие выполняется автоматически. Что из этого следует?

Подсказка 7

Следует, что есть совершенное паросочетание. Как фокусник и ассистент могут его использовать?

Подсказка 8

Если они заранее договорятся о конкретном паросочетании, то каждому набору зрителя будет соответствовать ровно один набор ассистента. Что тогда делает ассистент, увидев набор зрителя?

Подсказка 9

Он находит соответствующий набор в паросочетании и показывает его. Что делает фокусник? Для каких k это работает?

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

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

Задача 2#142204Максимум баллов за задание: 7

В графе n  вершин, все вершины имеют одинаковую степень. Докажите, что в этом графе есть паросочетание, содержащее не менее, чем n
 3  рёбер.

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

Подсказка 1:

Если требуемое в задаче верно, то наибольшее по числу рёбер паросочетание точно будет удовлетворять этому. Почему бы его не рассмотреть.

Подсказка 2:

Что делать дальше? Изучить ситуацию. Пусть в паросочетании менее n / 3 рёбер. Сколько тогда вершин вне паросочетания? Могут ли между ними быть рёбра, сколько рёбер от этих вершин проведено в вершины, вошедшие в паросочетание?

Подсказка 3:

Обозначим степень вершин через d. Вне паросочетания будет хотя бы [n / 3] + 1 вершина. Между ними рёбер нет. Из них выходит хотя бы d([n / 3] + 1) рёбер в вершины паросочетания. Не получится ли, например, для какого-то ребра AB в паросочетания найти две вершины X и Y вне паросочетания такие, что проведены рёбра AX и BY. Что можно сделать с такой конструкцией?

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

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

Задача 3#158674Максимум баллов за задание: 7

Лемма Холла. Даны m  юношей и несколько девушек. Если для любого k= 1,  2,  …, m  любые k  юношей знакомы в совокупности хотя бы с k  девушками, то можно одновременно поженить каждого юношу на знакомой девушке (иными словами, существует паросочетание, покрывающее всех мальчиков).

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

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

Задача 4#158676Максимум баллов за задание: 7

Обобщенная лемма Холла. Даны натуральное число s,  а также m  юношей и несколько девушек. Если Для любого k ≥s  любые   k  юношей знают не меньше, чем k− s  девушек, то можно одновременно поженить хотя бы m− s  юношей.

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

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

Задача 5#158678Максимум баллов за задание: 7

Теорема Кёнига. Наибольшее количество рёбер в паросочетании в двудольном графе равно наименьшему количеству вершин в вершинном покрытии графа G  (вершинное покрытие — это такое множество вершин, что каждое ребро содержит хотя бы одну из них).

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

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

Задача 6#160102Максимум баллов за задание: 7

Из графа K
 n,n  удалили n− 1  ребро. Докажите, что в нем все равно найдется совершенное паросочетание.

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

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

Задача 7#92177Максимум баллов за задание: 7

Оля и Максим оплатили путешествие по архипелагу из 2009  островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что Оля может выиграть.

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

Подсказка 1

Попробуем разбить острова на пары связанных маршрутом катера и отдельные острова. Рассмотрим такое разбиение с максимальным числом пар. Какую стратегию может выбрать Оля?

Подсказка 2

Верно! Сначала она выбирает прилет на отдельный остров. Затем, если Максим выбирает остров из какой-то пары, то Оля отвечает островом из этой пары. А может ли Максим сходить на отдельный остров?

Подсказка 3

Рассмотрим путь от начального острова до этого отдельного острова. Из скольки островов он состоит?

Подсказка 4

Верно! Ровно из 2k островов: k-1 пара островов и 2 отдельных острова. А можно ли разбить этот путь так, чтобы увеличить наше разбиение?

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

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

Задача 8#92178Максимум баллов за задание: 7

Набор ребер в графе называется покрытием, если каждая вершина графа принадлежит хотя бы одному ребру набора. Дан граф на n  вершинах, среди которых нет изолированных. Докажите, что сумма размеров максимального паросочетания и минимального реберного покрытия равна n.

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

Подсказка 1

Рассмотрим максимальное паросочетание, и пусть в нем ровно 2k вершин. По условию из каждой вершины выходит по ребру. А что можно сказать о ребрах, которые выходят из вершин, не вошедших в паросочетание?

Подсказка 2

Конечно! Любые две вершины не из паросочетания не соединены ребром (иначе паросочетание не максимальное). Кроме того, из двух различных вершин не из паросочетания ребра не могут вести в две различные вершины, связанные ребром, из паросочетания (иначе оно не максимальное). Попробуем выделить по ребру у каждой вершины не из паросочетания. Что можно сказать о минимальном покрытии этой конструкции?

Подсказка 3

Все верно! Оно содержит только ребра паросочетания и выделенные ребра, причем оно точно содержит все ребра паросочетания! Какова тогда сумма размеров максимального паросочетания и минимального покрытия?

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

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

Задача 9#92526Максимум баллов за задание: 7

Имеются 27  карточек с числами от 1  до 27.  Двое показывают следующий фокус. Первый получает k  карточек, выбранные случайным образом. Одну из них он убирает, а k− 1  оставшихся выкладывает в ряд. Второй должен назвать спрятанную карточку. Могут ли участники договориться так, чтобы по выложенным карточкам можно было определить спрятанную, если

(a) k= 4?

(b) k= 14?

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

Подсказка 1

Фокусник должен по какому-то набору карт, понять какой-то другой набор карт. Как это можно сделать?

Подсказка 2 пункт а

Постройте биекцию между наборами четверок и упорядоченными тройками карт.

Подсказка 2 пункт б

Постройте биекцию между наборами из 13 и из 14 карт.

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

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

Задача 10#73381Максимум баллов за задание: 7

В государстве некоторые города соединены двусторонними беспересадочными авиалиниями. Из каждого города выходит не более 10  авиалиний. Всего в государстве более 190  авиалиний. Докажите, что найдутся 11  авиалиний, никакие две из которых не имеют общих концов.

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

Подсказка 1

Понятно, что хочется найти паросочетание из хотя бы 11 ребер (если переведем задачу на язык графов). В задаче есть условие на ребра, степени - поэтому попробуем решать от противного и выделим максимальное паросочетание - в нем не больше 10 ребер. Какие выводы можно сделать из этого? Что можно сказать о вершинах, которые не вошли в такое паросочетание?

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

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

Задача 11#146051Максимум баллов за задание: 7

В собрании клуба «Диоген» принимают участие несколько джентльменов, некоторые из которых дружат между собой (дружба взаимна). Назовём участника нелюдимым, если у него среди присутствующих на собрании ровно один друг. По правилам клуба единственный друг любого нелюдимого участника может покинуть собрание (джентльмены покидают собрание по одному). Цель собрания — добиться того, чтобы среди участников не осталось друзей. Докажите, что если цель вообще может быть достигнута, то количество оставшихся на собрании участников не зависит от того, кто и в каком порядке уходил.

Источники: СПбОШ - 2023, 10.6 (см. pdmi.ras.ru)

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

Подсказка 1

Джентльмены уходят по одному, пока не останется ни одной пары друзей. Что нужно исследовать в графе, построенном по условию, чтобы применять какие-то известные факты?

Подсказка 2

Очень похоже на условие задачи вершинного покрытия графа. Это такой набор вершин, для которого любое ребро имеет инцидентную (связанную с этим ребром) вершину в данном множестве. Какие существуют связанные понятия?

Подсказка 3

С вершинным покрытием связаны паросочетания — наборы ребер, не имеющих общих смежных с ними вершин. Попробуйте рассмотреть максимальное паросочетание, количество ребер в нем равно количеству вершин в минимальном вершинном покрытии.

Подсказка 4

Что можно сказать про количество ребер в максимальном паросочетании при уходе друга нелюдимого джентльмена?

Подсказка 5

Верно, количество ребер либо уменьшилось на 1, либо не изменилось. Если доказать, что оно обязано уменьшится на 1, то количество оставшихся джентльменов ровно на количество ребер в паросочетании меньше, чем в начале собрания.

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

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

Задача 12#81317Максимум баллов за задание: 7

 200  теннисистов сыграли 140  партий так, что каждый участвовал хотя бы в одной. Докажите, что найдутся 60  партий, в которых участвовали 120  различных теннисистов.

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

Подсказка 1

Попробуем построить граф, в котором ребра — партии, а вершины — теннисисты. Пусть в его максимальном паросочетании x ребер. Тогда в нем 2x вершин. А можно ли оценить число ребер, которые выходят из оставшихся 200 - 2x вершин?

Подсказка 2

Ясно, что между этими теннисистами не может быть ребер, а иначе рассматриваемое паросочетание не является максимальным! При этом у каждой вершины есть по ребру, так что все они выходят в наше паросочетание. А сколько этих ребер?

Подсказка 3

Верно, 200 - 2x! А можем ли мы теперь снизу оценить число ребер и использовать число ребер из условия?

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

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

Задача 13#81771Максимум баллов за задание: 7

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

Сообщить об ошибке
Ответ и решение
Сообщить об ошибке

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

Задача 14#82767Максимум баллов за задание: 7

Из шахматной доски вырезали 7  клеток. Докажите, что на оставшиеся клетки можно поставить 8  не бьющих друг друга ладей.

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

Подсказка 1

Попробуем применить лемму Холла. Для этого нужно построить двудольный граф. Что можно считать вершинами, а что ребрами?

Подсказка 2

Верно! Пусть в одной доле будут вершины-строки, а в другой — вершины-столбцы, а ребра — невырезанные клетки, стоящие на пересечении соответствующих столбцов и строк. Попробуем теперь доказать условие леммы Холла для вершин-строчек.

Подсказка 3

Как и полагается в условии леммы, выберем любые k строчек. Нам нужны столбцы, которые с этими строчками соединяются. А можно ли оценить число столбцов, которые с нашими строчками не имеют общих ребер?

Подсказка 4

Конечно! Если столбец не имеет общих ребер с нашими строчками, то в нем вырезано хотя бы k клеток, а значит таких столбцов не более 7/k. Тогда столбцов, соединенных с нашими строчками хотя бы 8 - 7/k. Что остается проверить для леммы Холла?

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

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

Задача 15#82769Максимум баллов за задание: 7

В множестве A  2016  элементов. Докажите, что ко всем 1001  -элементным подмножествам добавить по одному элементу так, чтобы все получившиеся 1002  -элементные подмножества были бы различны.

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

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

Задача 16#82770Максимум баллов за задание: 7

Из бумаги вырезан квадрат. Сверху на нем красным цветов нарисовано разбиение на n  равновеликих треугольников, а снизу зеленым цветом нарисовано разбиение на n  равновеликих треугольников. Докажите, что можно проткнуть квадрат n  булавками так, чтобы каждая булавка протыкала во внутренней точке один зеленый и один красный треугольник, и каждый треугольник был проткнут ровно один раз.

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

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

Задача 17#82772Максимум баллов за задание: 7

Дана таблица n× n.  Её первые k< n  строчек заполнены натуральными числами от 1  до n  так, что в каждой строке и в каждом столбце все числа различны. Докажите, что можно расставить натуральные числа от 1  до n  в оставшиеся клетки таблицы так, чтобы по-прежнему выполнялось это условие.

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

Подсказка 1

Достаточно доказать, что можно заполнить еще одну строку. Попробуем рассмотреть для чисел от 1 до n столбцы, в которых их нет. Как удобно по-другому представить эту информацию?

Подсказка 2

Верно! Представим это в виде двудольного графа, в котором вершины одной доли — числа, а вершины другой доли — столбцы. Ребро проводится между числом и столбцом, в котором этого числа нет. Какие будут степени у вершин?

Подсказка 3

Точно! Степень каждой вершины равна n - k. Тогда в каждой доле степени вершин одинаковы. Можно ли выделить паросочетание, покрывающее долю столбцов?

Подсказка 4

Верно, по лемме Холла получается нужное паросочетание! Как теперь расставить числа, чтобы они соответствовали условию?

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

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

Задача 18#82773Максимум баллов за задание: 7

Даны n  мальчиков и 2n − 1  конфета. Докажите, что можно дать каждому мальчику по конфете так, чтобы мальчику, которому не нравится его конфета, не нравились и конфеты остальных мальчиков.

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

Подсказка 1

Рассмотрим граф, в котором вершинами являются конфеты и мальчики, ребро проводится между конфетой и мальчиком, если конфета этому мальчику нравится. Конечно, если выполняется условие леммы Холлы, то легко указать паросочетание, покрывающее мальчиков. А что, если это условие неверно?

Подсказка 2

Посмотрим на максимальное множество мальчиков, для которого условие леммы Холла неверно. Для него можно указать соответствующее множество конфет, которое, конечно, строго меньше. Что можно сказать о графе, если из него удалить все указанные вершины и соответствующие ребра?

Подсказка 3

Конечно! Множество удаленных конфет по мощности не превосходило n - 1, так что сейчас осталось хотя бы n конфет. Можно ли тогда указать в этом графе паросочетание?

Подсказка 4

Можно! Ведь в этом графе, конечно, выполняется условие леммы Холла (а иначе было удалено не максимальное множество мальчиков, которое ему не удовлетворяет). Как тогда можно раздать конфеты?

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

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

Задача 19#82774Максимум баллов за задание: 7

На конференцию приехали 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 знают пятый язык, а можно ли тогда оценить число знающих четвертый язык и использовать условие его выбора для этой ситуации?

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

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

Задача 20#83424Максимум баллов за задание: 7

(a) Пусть G   — двудольный граф, в каждой доле по n  вершин, и в нём больше чем (k− 1)n  рёбер. Докажите, что в нём найдётся паросочетание, в котором хотя бы k  рёбер.

(b) Докажите, что из 51  различного натурального числа, меньшего 100,  можно выбрать 6  чисел, попарно отличающихся в обоих разрядах (считаем, что у однозначных чисел в разряде десятков стоит 0  ).

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

Подсказка 1, пункт (a)

Попробуем предположить противное. Какой вывод можно сделать по теореме Кенига?

Подсказка 2, пункт (a)

Верно! Найдется вершинное покрытие из k-1 вершины. Причем степени этих вершин мы можем оценить. Какое максимальное число ребер может содержать граф?

Подсказка 1, пункт (b)

Попробуем построить двудольный граф, который удовлетворял бы условию предыдущего пункта. Как это можно сделать?

Подсказка 2, пункт (b)

Верно! Вершины одной доли будут цифрами десятков, а вершины другой доли будут цифрами единиц. Что можно сказать о числе ребер в этом графе?

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке
Рулетка
Вы можете получить скидку в рулетке!