Задача
COM-B2-M08-P016 Запрещённые дни
Есть \(n\) экзаменов и \(n\) дней. Каждый экзамен запрещено проводить не более чем в одном дне, и каждый день запрещён не более чем для одного экзамена. Докажите, что экзамены можно назначить на разные дни, соблюдая запреты.
Проверьте условие Холла для одного экзамена и для двух или более экзаменов отдельно.
Построим двудольный граф: экзамен соединён с днём, если его можно провести в этот день. Проверим условие Холла.
Для одного экзамена доступно хотя бы \(n-1\) дней, а при \(n\ge2\) это не меньше \(1\). Если взято \(k\ge2\) экзаменов, то любой день доступен хотя бы одному из них: ведь один день может быть запрещён не более чем для одного экзамена. Значит, объединение доступных дней равно всем \(n\) дням, а \(n\ge k\).
Условие Холла выполнено для любого набора экзаменов. Следовательно, существует расписание с разными днями.
Хорошая задача на аккуратную проверку Холла по случаям.