Question

В классе конечное число девочек и мальчиков. Некоторые мальчики и девочки дружат между собой. Назовём группу мальчиков "социальной", если каждая девочка дружит хотя бы с одним мальчиком из группы. Аналогично, назовём группу девочек "социальной", если каждый мальчик дружит хотя бы с одной девочкой из группы. Докажите, что количество социальных групп мальчиков имеет ту же чётность, что и количество социальных групп девочек.

Answer 1

Назовем множество девочек $\mathcal{F}$, а множество мальчиков -- $\mathcal{M}$. Социальную группу назовем примитивной, если удаление любого мальчика из нее сделает группу не социальной. Тем самым, всякая социальная группа порождена некоторой примитивной. Пусть $S_{k}$ -- число продолжений примитивной социальной группы $P_{k}$. Ясно, что $S_{k} = 2^{|\mathcal{M}|-|P_{k}|}$, поскольку объединение любого подмножества с социальной группой дает социальную группу. Количество социальных групп тем самым равно  $\sum\limits_{j=1}^{t}S_{j} - \sum\limits_{i,k}S_{ik}$, где $S_{ik}$ -- число продолжений социальной группы $P_{i}\cup P_{k}$. В самом деле, когда мы считаем число продолжений, мы не должны забывать, что у двух примитивных социальных групп может быть одинаковое продолжение. Если продолжения групп $P_{i}$ и $P_{k}$ совпадают, то они обязательно содержат $P_{i}\cup P_{k}$. Договоримся называть пустое множество примитивной социальной группой. Тогда если в первой сумме $S_{l} = \mathcal{M}$ для некоторого $l$, то перенесем это значение (без ущерба для четности) во вторую сумму, считая эту величину числом продолжений группы $S_{l}\cup \varnothing$. Имеем тогда: первая сумма есть четное число, а слагаемое во второй сумме является нечетным тогда и только тогда, когда $P_{i}\cup P_{k} = \mathcal{M}$.

Утверждение: число пар примитивных множеств $P_{i}$ и $P_{k}$ таких, что $P_{i}\cup P_{k} = \mathcal{M}$ имеет ту же четность, что и количество пар аналогичных множеств для $\mathcal{F}$.

Доказательство: в качестве доказательства можно посмотреть на иллюстрацию, где, например, $(5,6,7,8)$ и $(7,8,9,10,11)$ -- социальные. Теперь построим естественное соответствие. Из каждой вершины отметим ненулевое количество красных и синих ребер (иногда одно ребро красится двумя цветами). Тогда "образы" точек под действием красных ребер дадут социальную группу, скажем, $A$, а под действием синих -- $B$ (причем $A\cup B = \mathcal{M}$). Теперь сотрем цвета и сделаем аналогичную раскраску, но для множества $\mathcal{M}$ (то есть для ребер, исходящих из множества мальчиков). Здесь уже будет гарантироваться, что объединение социальных групп в множестве девочек будет давать $\mathcal{F}$. Количество таких раскрасок -- четное число (в вершинах степени не меньше $2$ число вариантов четно; случай, когда таких нет рассмотрим отдельно), а потому общее число пар четно. Симметрично рассматривается количество пар в $\mathcal{M}$. Ключевое здесь то, что оба множества покрывают друг друга ребрами.

Если все степени вершин равны $1$ (например, в $\mathcal{M}$), то имеется единственный случай: когда берется объединение $\mathcal{M}$ и пустого множества. Но ребра из $\mathcal{F}$ накрывают $\mathcal{M}$ (поскольку ребер нулевой степени нет), а потому и в $\mathcal{F}$ есть такая пара.                                       ∵

Получили, что четность $\sum\limits_{i,k}S_{ik}$ совпадает в обоих множествах, а значит, совпадает и четность всей суммы.

прощения, что так мудрено. Если что, отвечу на вопросы.