Top.Mail.Ru

Часто ищут

Разделы

Бесплатно

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

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

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

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

Задача 1#175097

Фокусник и его ассистент готовятся показать следующий фокус. У них есть колода из 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.0

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

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

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

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

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

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

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

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

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

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

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

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