СПбГУ 2025, 10–11 классы, задача 16

Сложная
Комбинаторика
Источник:
Олимпиады школьников СПбГУ, Отборочный этап, 2025, 10–11 классы

( баллов) В компании из человек некоторые пары людей враждуют между собой (вражда взаимна). Известно, что у каждого в компании не более врагов. Докажите, что можно разбить всех людей на не более чем групп так, что количество пар врагов, оказавшихся в одной группе, будет не более .

Ответ

Решение. Рассмотрим разбиение людей не более чем на групп с наименьшим числом пар врагов внутри групп. Если у кого-то из людей в своей группе хотя бы врага, то найдётся другая группа, в которой у него не более врагов (иначе врагов было бы ). Тогда можно переместить этого человека в другую группу и уменьшить суммарное количество врагов. Следовательно, у каждого не более врагов в его группе. Тогда всего пар врагов внутри групп не более , что и требовалось.

1

Верное решение

40
Максимум: 40

Похожие задачи

СПбГУ 2024, 10–11 классы, задача 6

(40 баллов) На доске написаны числа 1, 2, 3,..., 2023. Раз в минуту к доске подбегает Жора. Он выбирает некоторое натуральное число k, но не обязательно написанное на доске. После этого каждое число на доске, не меньшее k, уменьшает на k. После нескольких операций на доске осталось ровно одно ненуле
Сложная
Комбинаторика

СПбГУ 2026, 8-9 классы, задача 3

(20 баллов) Король ходит по клетчатой доске 8 × 8. Он начинает в левом нижнем углу, а должен закончить в правом верхнем, смещаясь за один ход ровно на одну клеточку. Ему запрещено возвращаться на ту клеточку, где он уже был до этого, а также переходить в более левые столбцы. Другими словами, король
Сложная
Комбинаторика

СПбГУ 2025, 8–9 классы, задача 9

(40 баллов) В вершинах правильного 100-угольника расположены целые числа, сумма которых равна 2025. Два игрока по очереди берут себе по одному числу. Первый игрок начинает, выбирая любое число. Со второго хода разрешается брать числа только из вершин, соседних с теми, откуда уже были взяты числа. По
Сложная
Комбинаторика

СПбГУ 2022, 8–9 классы, задача 11

(40 баллов) Числа от 1 до 600 разбиты на несколько групп. Известно, что если в группе более одного числа, то сумма любых двух чисел из этой группы делится на 6. Какое наименьшее количество групп может быть?
Сложная
Теория чисел
Комбинаторика