В классе учится поровну мальчиков и девочек. Назовём непустую группу мальчиков популярной, если каждая девочка в классе дружит хотя бы с одним мальчиком из этой группы (все дружбы взаимны). Оказалось, что в классе ровно 63 популярные группы. Докажите, что каждый мальчик дружит хотя бы с одной девочкой.
1 Ответ
Решение.
Предположим, существует мальчик 𝑥, который не дружит ни с одной девочкой. Обозначим через 𝑀 множество всех остальных мальчиков класса. Заметим, что группа мальчиков 𝐺 ⊂ 𝑀 является популярной тогда и только тогда, когда группа мальчиков 𝐺 ∪ {𝑥} является популярной. Таким образом, все популярные группы разбиваются на пары, в каждой из которых группы различаются только присутствием 𝑥, и их количество чётно. Но по условию популярных групп 63 — нечётное количество, противоречие. Следовательно, каждый мальчик дружит хотя бы с одной девочкой.