30. Общие представители

КаждЫЙ студент группы участвовал в одной из 5 Спортивных секций. А на летние каникулы каждый из ниХ Вошел В один из 5 студенческих строителЬНых отрядов. Однажды на ЗАседании факулЬТетского бюро ВЛКСМ стояли вопросы о спортивной работе и о работе студенческих строительных отрядов. Можно ли послать 5 делегатов от этой группы так, чтобы они представляли и всЕ спортивные секци, и и всЕ строительные Ompяды?

Разумеется, в столь общей постановке задача Неразрешима, — иногда моЖНо послать, иногда и нельзя. Поэтому надо найти условия, при которых такой выбор ДелегациИ возможен. Если, например, участники волейбоЛьНой и шахматной секций целиком входят в первый отряд, то представитель этого отряда сможет говорить либо о шахматах, либо о волейболе, но не об обеих играх Сразу. Этот пример показывает, в чем заключается Необходимое Условие возможности требуЕМого выбора: никакие K СпорТивных секций не могут входИТь в объединение мЕнЕе Чем K строительных отрядов. Оказывается, это условие Является и достаточным. Сформулируем его так.

ПустЬ студенческая группа разбита на П Спортивных Секций И П строителЬНых отрядов . Для того чтобы МОжно было ВЫбратЬ п Студентов Так, чтобы каждая спортивная секция и каждый CmроИтельный отряд имели представителей, необходимо и достаточно, чтобы никакие k спортивных секций не Входили В объединение менее чем k строительных отрядов.

Доказательство ЭТого утверждения сводится к Использованию теоремы о различных представителях.

Отметим одно достаточное условие для возможноСти Назначить общих представителей: Если множество из элЕМеНТов разбито двумя способами на k Подмножеств Содержащих по Р ЭЛементов, то длЯ ЭТих двух Разбиений Можно выбрать систему общих представителей.

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