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