В
Все
М
Математика
О
ОБЖ
У
Українська мова
Х
Химия
Д
Другие предметы
Н
Немецкий язык
Б
Беларуская мова
М
Музыка
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
У
Українська література
Р
Русский язык
Ф
Французский язык
П
Психология
О
Обществознание
А
Алгебра
М
МХК
Г
География
И
Информатика
П
Право
А
Английский язык
Г
Геометрия
Қ
Қазақ тiлi
Л
Литература
И
История
obilan228
obilan228
30.11.2022 20:21 •  Математика

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

Показать ответ
Ответ:
2YAROSLAV5
2YAROSLAV5
15.02.2022 22:15

Назовем множество девочек \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} совпадает в обоих множествах, а значит, совпадает и четность всей суммы.

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


В классе конечное число девочек и мальчиков. Некоторые мальчики и девочки дружат между собой. Назовё
0,0(0 оценок)
Популярные вопросы: Математика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота