Задача
Имеется несколько юношей, каждый из которых знаком с некоторыми девушками. Две свахи знают, кто с кем знаком. Одна сваха заявляет: "Я могу одновременно поженить всех брюнетов так, чтобы каждый из них женился на знакомой ему девушке!" Вторая сваха говорит: "А я могу устроить судьбу всех блондинок: каждая выйдет замуж за знакомого юношу!" Этот диалог услышал любитель математики, который сказал: "В таком случае можно сделать и то, и другое!" Прав ли он?
Решение
Пусть каждый брюнет возьмёт правой рукой левую руку девушки, предназначенной ему первой свахой, а каждая блондинка возьмёт правой рукой левую руку юноши, предназначенного ей второй свахой. При этом образуются хороводы (циклы) и цепочки, которые содержат всех брюнетов, всех блондинок и, возможно, кого-то еще. Цепочки из чётного числа людей и хороводы (там чётное число людей ввиду чередования) разбиваются на пары знакомых, и их можно поженить.
Пусть цепочка состоит из нечётного числа людей и юношей в ней больше, чем девушек. Тогда на её концах стоят юноши и у одного из них свободна правая рука. Значит, он не брюнет, и его можно удалить из цепочки, а оставшихся переженить. Аналогично поступим с цепочкой, в которой больше девушек.
Ответ
Прав.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь