Задача
COM-B2-M08-P012 Представители секций
#12
★★★☆☆ Уровень 3 из 5
В каждой из \(n\) секций состоят некоторые школьники. Докажите, что можно выбрать из каждой секции по разному представителю тогда и только тогда, когда объединение любых \(k\) секций содержит не меньше \(k\) школьников.
Переформулируйте как SDR.
Если представители выбраны, то любые \(k\) секций имеют \(k\) разных представителей, все они лежат в объединении этих секций. Поэтому объединение содержит не меньше \(k\) школьников.
Обратно, условие про объединения — это условие Холла для множеств школьников, соответствующих секциям. По теореме Холла существует система различных представителей.
Формулировка Холла в языке множеств.