СПбГУ 2025, отборочный этап, 10–11 классы, задача 16
( баллов) В компании из человек некоторые пары людей враждуют между собой (вражда взаимна). Известно, что у каждого в компании не более врагов. Докажите, что можно разбить всех людей на не более чем групп так, что количество пар врагов, оказавшихся в одной группе, будет не более .
Ответ
Решение. Рассмотрим разбиение людей не более чем на групп с наименьшим числом пар врагов внутри групп. Если у кого-то из людей в своей группе хотя бы врага, то найдётся другая группа, в которой у него не более врагов (иначе врагов было бы ). Тогда можно переместить этого человека в другую группу и уменьшить суммарное количество врагов. Следовательно, у каждого не более врагов в его группе. Тогда всего пар врагов внутри групп не более , что и требовалось.