Задача
COM-B2-M08-P009 Устойчивый выбор
#9
★★★☆☆ Уровень 3 из 5
Для семейства множеств \(A_1,\ldots,A_n\) известно, что объединение любых \(k\) из них содержит не меньше \(k+1\) элементов. Докажите, что после удаления любого одного элемента всё равно можно выбрать систему различных представителей.
После удаления одного элемента объединение любых \(k\) множеств потеряет не больше одного элемента.
Удалим произвольный элемент \(x\). Возьмём любые \(k\) множеств. До удаления их объединение имело размер не меньше \(k+1\). После удаления \(x\) размер объединения уменьшится не более чем на \(1\), значит, останется не меньше \(k\) элементов.
Условие Холла выполнено для нового семейства, поэтому система различных представителей существует.
Показывает запас в условии Холла.