Задача
COM-B2-M08-P011 Интервалы дней
#11
★★★☆☆ Уровень 3 из 5
Каждому из \(n\) докладов разрешено выступать в некоторые дни. Известно, что для любых \(k\) докладов объединение разрешённых дней содержит не меньше \(k\) дней. Докажите, что можно назначить всем докладам разные дни.
Это ровно условие Холла.
Построим двудольный граф: слева доклады, справа дни, ребро означает, что доклад можно поставить в этот день. Условие задачи говорит, что для любого набора \(S\) докладов множество соседних дней имеет размер не меньше \(|S|\). По теореме Холла есть паросочетание, покрывающее все доклады. Оно и задаёт расписание.
Текстовая задача на прямой перевод в граф.