Задача 5.
Дядька Черномор набирает себе новую банду. На кастинг пришли 33 гномика и устроили драку. Каждый из них подбил один глаз другому гномику, и у каждого гномика был подбит ровно один глаз. Кроме того, для любых трёх гномиков можно указать четвёртого, который подбил глаз одному из них. Докажите, что Черномор может выгнать не более 5 гномиков, если он хочет всех оставшихся гномиков разделить на два отряда так, чтобы ни один гномик не попал в один отряд со своим обидчиком.
Ответ на Задачу 5.
Рассмотрим соответствующий орграф. Степени исхода и захода у каждой вершины равна 1. Значит, граф разбивается на циклы. Нет треугольных циклов, т. к. для любых трёх гномиков можно указать четвёртого, который подбил глаз одному из них. Нечетных циклов не более 6 (7 · 5 = 35 > 33), но тогда остаётся треугольник, поэтому нечётных циклов не более 5. Если убрать по одному гномику из каждого нечётного цикла, то всё получается.
