Паросочетания и лемма Холла
Ошибка.
Попробуйте повторить позже
Фокусник и его ассистент готовятся показать следующий фокус. У них есть колода из 2026 различных карт. Они сообщают зрителю
натуральное число Зритель выбирает
произвольных карт из колоды, убирает их в конверт и заклеивает его. Затем ассистент
выбирает
карт из оставшихся и передает их зрителю. Тот перетасовывает эти карты как хочет и отдает фокуснику. Задача фокусника —
отгадать карты, которые лежат в конверте. Для каких
фокусник и ассистент могут договориться действовать так, чтобы фокус
гарантированно удался?
Источники:
Подсказка 1
Ассистент видит k карт зрителя. Что он должен показать, чтобы фокусник восстановил набор?
Подсказка 2
Попробуйте представить процесс как соответствие между наборами. Как можно изобразить такое соответствие?
Подсказка 3
Используйте граф: вершины одной доли — наборы зрителя, другой — наборы ассистента. Когда между ними стоит проводить ребро?
Подсказка 4
Когда наборы не пересекаются. Сколько соседей будет у каждой вершины?
Подсказка 5
Степень равна Cₙⁿ⁻ᵏ. Что можно сказать про доли и сам граф?
Подсказка 6
Лемма Холла: паросочетание, покрывающее все вершины левой доли, существует, если для любого множества X наборов зрителя число соседей (наборов ассистента, не пересекающихся хотя бы с одним набором из X) не меньше |X|. В регулярном графе с равными долями это условие выполняется автоматически. Что из этого следует?
Подсказка 7
Следует, что есть совершенное паросочетание. Как фокусник и ассистент могут его использовать?
Подсказка 8
Если они заранее договорятся о конкретном паросочетании, то каждому набору зрителя будет соответствовать ровно один набор ассистента. Что тогда делает ассистент, увидев набор зрителя?
Подсказка 9
Он находит соответствующий набор в паросочетании и показывает его. Что делает фокусник? Для каких k это работает?
Обозначим Зафиксируем
и рассмотрим двудольный граф, вершинами одной доли которого являются всевозможные
комбинации из
зрительских карт, а второй долей являются всевозможные комбинации из
ассистентских карт (эти доли идентичны и
по существу являются всевозможными наборами из
различных карт колоды), а ребра проведены между вершинами разных долей, если
соответствующие наборы карт не пересекаются.
По вершине, соответствующей набору зрительских, ассистент должен выдать набор карт, соответствующих смежной вершине. Степени
всех вершин в этом графе равны так как каждой вершине одной доли сопоставляются всевозможные наборы из
карт из остатка
колоды размером
Это двудольный граф с равными по размерам долями, в котором степени всех вершин равны, поэтому согласно следствию из леммы
Холла в этом графе существует паросочетание, покрывающее все вершины обеих долей (совершенное паросочетание). Для каждого
фокусник и ассистент договариваются о выборе конкретного паросочетания, поэтому по картам ассистента всегда можно будет восстановить
карты зрителя.
Специальные программы

Программа
лояльности вер. 2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

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

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

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

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

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

