Задача 081 — Задачи на Графы

В городе есть несколько мальчиков и девочек, некоторые пары знакомы. Оказалось, что в любом множестве $D$ из 8 девочек найдётся (возможно, пустое) подмножество $D^{\prime}$ такое, что любой мальчик, знакомый со всеми девочками из $D^{\prime}$ , знаком ещё хотя бы с одной девочкой из $D$ . Докажите, что в любом множестве $M$ из 300 мальчиков найдётся (возможно, пустое) подмножество $M^{\prime}$ такое, что любая девочка, знакомая со всеми мальчиками из $M^{\prime}$ , знакома ещё хотя бы с одним мальчиком из $M$ .

Подсказка

Решение

Заметим, что $D_{1} \subset D$ может быть взято за $D^{\prime}$ тогда и только тогда, когда ни для какого мальчика множество его знакомых в $D$ не совпадает с $D_{1}$ . Аналогично с $M$ и $M^{\prime}$ . Предположим, что нашлось множество из $M$ мальчиков, в котором нельзя выделить $M^{\prime}$ , удовлетворяющее условию. Тогда для любого $M_{1} \subset M$ найдется девочка, которая в множестве $M$ знакома в точности с мальчиками из $M_{1}$ . Выберем в $M_{1} 300$ мальчиков, из них — 256 , и каждому мальчику сопоставим своё четырёхзначное двоичное число. Выберем 8 девочек так, чтобы $i$ -ая девочка знала в множестве $M$ в точности тех мальчиков, которым сопоставлено число с 1 в $i$ -ом разряде (мальчиков, которым ничего не сопоставлено, все эти девочки не знают). Тогда легко видеть, что в выбранном множестве девочек никакое подмножество нельзя назначить $D^{\prime}$ . Действительно, если $i_{1}, \ldots, i_{k}$ — номера девочек в подмножестве, то мальчик, которому сопоставлено число с единицами в разрядах $i_{1}, \ldots, i_{k}$ и нулями во всех остальных разрядах, из восьми выбранных девочек знает в точности $i_{1}, \ldots, i_{k}$ .