28. Выбор представителей

Студенты Петя Соболев, Леня Комаров, Витя Егоров, Сережа СмирноВ, Коля Токарев и Левон АрутюняН были Закадычными друзьями. Многими делами они Занимались Сообща: Петя и Витя вместе работали над изобретеНИем Леня и Сережа вМЕсте писали реферат по философии, ПеТя, Леня и Коля вместе заНИмались в секциИ самбо, Витя И Коля вместе организовывали математическую ОлимпИаду в иНСтитуте, а Коля и Левон шефствовали над одНОй из групп первого курса. Все шло хорошо, но однаЖДы друзья стали в тупик — выяснилось, что в 15 часов 00 мИНут нужно делать доклад об изобретении, прийти на Консультацию к преподавателю философии, хотя бы одному выСТупить на соревнованиях по самбо, принять участие в подборе задач для олимпиады и провести собрание в подшЕФНОй группе. Ведь если Петя будет докладывать об изоБретении, Леня пойдет на коНСультацию, Коля будет Отбирать задачи, а Левон проведет собрание, то на Соревнования по самбо никто пойти НЕ сможет — ни Витя, ни Сережа ни разу этим видом спорта не заНИмались.

Но Витя и Коля НЕ зря интересовались МатематиКой и после некоторых размышлений они придумали такой план: об изобретении доложит Петя, на консультации пойдет Леня, на соревнования по самбо — Коля, заДачИ будет отбирать Витя, а собрание проведет Левон. ПОложение друзей было бы куда хуже, если бы над изобреТЕнием работали Петя и Витя, реферат писали Витя и Сережа, в секции самбо занимались Петя и Сережа, математическую олимпиаду организоВЫвали Петя, Витя и Сережа, а шефствовали Леня, Коля и Левон. В этом случае первыми четырьмя ДЕлами заНИмались бы всего трое друзей, и принцип Дирихле не позволил бы им так распределить обязанности, что все дела были бы сделаны.

Нетрудно сообразить, в чем заключается необходимое условие того, чтобы можно было распределить дела Между нашими друзьями — любыми K делами должны Заниматься по крайней мере K человек. Оказывается, что это Условие не только необходимо, но и достаточно — если оно выполнено, то требуемое распределение ОбязанноСтей всегда возможно.

В общем виде это утверждение формулируется так.

Пусть в каком-нибудь множестве Х выделены Подмножества . Для того чтобы в Х можно было Выбрать п различных ЭЛементов таких, что , Необходимо и достаточно выполнение следующего условия: объединение любых k заданных Подмножеств должно содержатЬ по крайней мере k элементов.

Эту теорему, доказанную английским математиком Ф. Холлом, НАзываЮТ теоремой о различных представителях или теоремой о ДерЕВенСких свадьбах. Последнее название ведет свое происхождение от формулировки, восходящей к изВЕстному немецкому математику ГермаНУ Вейлю.

В деревне относителЬНо каждого юноши и девушки ИзВестно, дружат они или нет. Если для любых k юношЕЙ ОБъединение множеств их подруг содержит по крайней мере k девушек, то каждый юноша может выбрать себе ЖеНY из числа своих подруг (в этой задаче Х — множество ВCex девушек, — подмножества, состоящие из подруг первого, второго, ..., П-Го юноши).

Докажем теорему в формулировке Г. Вейля, проведя иНДукцию по числу юНОшей. Пусть число юношей равно N. При П=1 все очевидно — в силу условия теоремы у ОДного юноши есть хотя бы одна подруга и оН может ВыбИрать себе жену. Предположим, что теорема доказана для ЛЮбого числа юношей, меньшего П. Возьмем П юношЕЙ, прИЧем будем считать, что множества их подруг удовлетворяЮТ условию теоремы — объединение множеств подруг любых K юношей состоит по крайней мере иЗ K девушек. Тогда возможны два случая:

А) найдется множество, состоящее из R юНОшей, где , для которых ОбъединеНие множЕСтв их подруг содЕржит r Девушек. Если бы девушек было хотя бы на одНу меньше, условие тЕОремЫ наруШИлось бы. Поэтому такую совокупность юношей и девушек называют «критической». Внутри этого критического множЕСтва ВыполнеНо условие теоремы — юноши этого множества имеют подруг лишь среди девушек того же множества, а потому выПОлНЕния условия для всех юношей и девушек вытекает, что оно верно и при ограничении этим множеств. Но тогда можно найти жен для всех юношей из Критического множества, выбирая их из того же множествА так, чтобы каждый юноша получил в жены одну из своих подруг. Поскольку с этими юношами все в порядке, устраним их и выбранных ими жен из рассмотрения и возьмем оставшихся П-R юношей. Легко видеть, что для них тоже выполняется условие теоремы (если бы для каких-нибудь S юношей объединение множеств их подруг содержало меньше, чем S девушек, то для множества, состоящего, из этих S юношей и R юношей из критического Множества Тоже нарушалось бы условие теоремы). Значит, по ПредПоложению индукции, можно найти жен и для ЭТих П-R Юношей. А тогДА все юноши нашли жен, и в этом случае теорема доказана;

Б) теперь рассмотрим случай, когда критических множеств нет — при R < п для любых R юношей объединЕние Множеств их подруг содержит по крайней мере Девушек. Тогда возьмем любого юношу, жеНИм его на одной из его подруг и устраним счастливую пару из рассмотрения. Остается П-1 юношей, причем для ниХ услоВие теоремы выполняется. В самом деле, возьмем любых R из оставшихся юношей. Объединение множеств их подруг состояло, по крайней мере, из девушек. Значит, И после удаления новобрачной, это множество состоит, по крайней мере, из R девушек. Но тогда можно выбрать жен для этих П-1 юношей, чем и заканчивается доказательство теоремы о деревенских свадьбах.

Серьезному читателю, недовольному тем, что в Столь Важной теореме мы говорим о матримониальных отношениях, предоставляем провести это доказательство, заменив слово «девушки» словами «элементы множестВА», слово «юноши», — словом «подмножества»; вместо того, ЧтоБы говорить «юноша дружит с девушкой», придется Говорить «элемент принадлежит подмножеству», а вместо «юноша женился на девушке», — «в подмножестве Выбран Элемент». А все остальное остается по-прежнему.

< Предыдущая		Следующая >