Принцип крайнего

Подсказка 1

Переведем задачу на язык графов. Рассмотрим граф, вершинами которого являются люди, а рёбрами (неориентированными) — письма. Степень каждой вершины в нашем графе хотя бы 1, и среди любых 40 вершин есть ребро. К какому условию на языке графов тогда сводится наша задача?

Подсказка 2

Верно! Наша задача равносильна поиску минимального k, для которого можно выбрать k ребер, покрывающих все вершины (чтобы каждая вершина была концом некоторого ребра). Значит, доказательство будет вида оценка + пример. Начнем с оценки. Пусть M максимальное паросочетание. Пусть в M не вошло x вершин. Тогда как можно оценить сверху x?

Подсказка 4

Точно! Не может! У нас в исходном графе и в M по четное количество вершин. Поэтому x < 39. Добавим к M по одному ребру из каждой вершины, не вошедшей в максимальное паросочетание. Тогда как сверху можно оценить количество ребер в этом множестве?

Подсказка 5

Ага! Ребер не больше, чем 69. Теперь давайте попробуем построить пример.

Подсказка 6

Разобьем людей на 30 троек и группу из 10 человек. Пусть люди в тройках посылают письма по циклу. Тогда в каждой тройке мы должны взять минимум два ребра. Попробуйте придумать, как сделать так, чтобы нам пришлось из группы из 10 человек взять девять ребер.

Подсказка 7

В группе из 10 человек (один из которых Дед Мороз) сделаем так: все послали письмо Деду Морозу, а Дед Мороз — любому из остальных девяти людей. Попробуйте теперь доказать, что будет выполняться условие, что среди любых 40 людей есть отправитель, и получатель одного письма.