Олимпиадная задача по теории графов о пощёчинах депутатов для 7-9 классов

Решение 1:Рассмотрим наибольшую группу A депутатов, в которой никто никого не бил. Тогда каждый из оставшихся депутатов попадает в группу B тех, кого били депутаты из A, либо в группу C тех, кто бил депутатов из A (иначе его можно было бы добавить к A, что противоречит её максимальности). Ясно, что в B депутатов не больше чем в A. Но и в C депутатов не больше чем в A, поскольку в ней никто никого не бил. Следовательно, в A не меньше 150 депутатов.

Решение 2:Согласно задаче 208403 депутатов можно разбить на три группы, в каждой из которых никто никого не бил. В наибольшей из них не меньше 150 депутатов.

Ответ задачи отсутствует