Высшая проба 2023, 8 класс, задача 4
( баллов) В классе учится поровну мальчиков и девочек. Назовём непустую группу
мальчиков популярной, если каждая девочка в классе дружит хотя бы с одним мальчиком из этой
группы (все дружбы взаимны). Оказалось, что в классе ровно популярные группы. Докажите,
что каждый мальчик дружит хотя бы с одной девочкой.
Решение. Предположим, существует мальчик , который не дружит ни с одной девочкой. Обозначим через множество всех остальных мальчиков класса. Заметим, что группа мальчиков ⊂ является популярной тогда и только тогда, когда группа мальчиков ∪ {} является популярной. Таким образом, все популярные группы разбиваются на пары, в каждой из которых группы различаются только присутствием , и их количество чётно. Но по условию популярных групп — нечётное количество, противоречие. Следовательно, каждый мальчик дружит хотя бы с одной девочкой.
Замечание. Описанная в условии задачи конструкция существует. Например, класс, в котором учится мальчиков и девочек, и каждая девочка дружит с каждым мальчиком, удовлетворяет условиям задачи.
Используется наибольший подходящий критерий.
15 б. Любое полное решение задачи.
12 б. Разбиение на пары построено не вполне корректно (например, в предположении, что мальчик, который не дружит ни с одной девочкой, существует, каждой популярной груп- пе, которая его содержит, сопоставлена группа, которая его не содержит; но обратное сопоставление не указано). # hse-vp-2023-final-g8 / solutions / page 5 ## Best Text.
5 б. Присутствует идея разбивать группы мальчиков на пары, но она не применяется именно к популярным группам.