ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65392
Темы:    [ Теория алгоритмов (прочее) ]
[ Связность и разложение на связные компоненты ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 3+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Эвнин А.Ю.

Имеется несколько юношей, каждый из которых знаком с некоторыми девушками. Две свахи знают, кто с кем знаком. Одна сваха заявляет: "Я могу одновременно поженить всех брюнетов так, чтобы каждый из них женился на знакомой ему девушке!" Вторая сваха говорит: "А я могу устроить судьбу всех блондинок: каждая выйдет замуж за знакомого юношу!" Этот диалог услышал любитель математики, который сказал: "В таком случае можно сделать и то, и другое!" Прав ли он?


Решение

  Пусть каждый брюнет возьмёт правой рукой левую руку девушки, предназначенной ему первой свахой, а каждая блондинка возьмёт правой рукой левую руку юноши, предназначенного ей второй свахой. При этом образуются хороводы (циклы) и цепочки, которые содержат всех брюнетов, всех блондинок и, возможно, кого-то еще. Цепочки из чётного числа людей и хороводы (там чётное число людей ввиду чередования) разбиваются на пары знакомых, и их можно поженить.
  Пусть цепочка состоит из нечётного числа людей и юношей в ней больше, чем девушек. Тогда на её концах стоят юноши и у одного из них свободна правая рука. Значит, он не брюнет, и его можно удалить из цепочки, а оставшихся переженить. Аналогично поступим с цепочкой, в которой больше девушек.


Ответ

Прав.

Замечания

1. Для знатоков. Без особых изменений доказательство проходит и для бесконечных множеств "юношей" и "девушек" (надо дополнительно рассмотреть бесконечные цепочки). Заметим, что теорема Кантора-Бернштейна является частным случаем этой задачи (когда все юноши – брюнеты, а все девушки – блондинки).

2. 8-9 кл. – 5 баллов, 10-11 кл. – 4 балла.

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Номер 25
Дата 2003/2004
вариант
Вариант осенний тур, основной вариант, 8-9 класс
задача
Номер 2
олимпиада
Название Турнир городов
Турнир
Номер 25
Дата 2003/2004
вариант
Вариант осенний тур, основной вариант, 10-11 класс
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .