Задача
COM-B2-M08-P020 Множества большого размера
Есть семейство конечных множеств \(A_1,\ldots,A_n\). Каждый элемент принадлежит не более чем \(r\) множествам, а каждое множество имеет размер не меньше \(r\). Докажите, что у семейства есть система различных представителей.
Для \(k\) выбранных множеств посчитайте пары «множество, элемент».
Возьмём любые \(k\) множеств. В них суммарно не меньше \(rk\) вхождений элементов, потому что каждое множество имеет размер не меньше \(r\). Каждый элемент из их объединения может быть посчитан не более \(r\) раз, так как он принадлежит не более чем \(r\) множествам всего.
Если размер объединения равен \(u\), то \(rk\le ru\), значит, \(u\ge k\). Условие Холла выполнено для любых \(k\) множеств. Следовательно, система различных представителей существует.
Сильная и очень полезная форма Холла через двойной подсчёт.