Правду ли говорят девочки

[Fedorov]

На вечеринке было 15 девочек и 12 мальчиков.
Каждого мальчика знают не менее половины девочек.
Три подружки — Таня, Оксана и Полина — похвастались, что вместе они знают всех мальчиков.

Правду ли говорят девочки?
Всегда ли на вечеринке найдутся три девочки, которые вместе знают всех мальчиков?

[JohnnyIpcom]

Хм... Разобьём мальчиков на 2 группы по 6 человек. Мальчиков из первой группы знают только девочки под номерами 1-8, второй группы - 8-15. Такой граф удовлетворяет условию задачи и если Таня, Оксана и Полина из одной группы - то они не знают всех мальчиков. Более того, может существовать группа даже в 7 девочек, которые не знают всех. Может ли больше(13 девочек) - я не знаю пока. Интуитивно - нет.

[Fedorov]

JohnnyIpcom
Примеры, когда такие три девочки есть, и когда таких нет, привести не очень трудно.
Ответ на второй вопрос сложнее.

[zhekas]

Предположим, что найдётся такое разбиение 15 девочек, что никакие 3 не знают всех мальчиков. Это значит, что любая тройка девочек не знает как минимум одного мальчика.

Всего троек девочек - $\frac{15\cdot14\cdot13}{3\cdot2\cdot1} = 455$

По принципу Дирихле, найдётся мальчик которого не знают $\frac{455}{12}=38$ троек девочек. Эти 38 троек образуют группу из не менее 8 девочек (Так как группа из семи девочек составляет $\frac{7\cdot6\cdot5}{3\cdot2\cdot1} = 35$ троек).

Получается, что одного мальчика не знает как минимум 8 девочек, а значит его знает меньше половины девочек. А это противоречит условию.

Значит Всегда найдутся три девочки, которые вместе знают всех мальчиков