Задача
COM-B2-M08-P006 Три кружка и три ученика
#6
★★★☆☆ Уровень 3 из 5
Три кружка имеют списки возможных старост: \(A_1=\{a,b\}\), \(A_2=\{b,c\}\), \(A_3=\{a,c\}\). Докажите, что можно выбрать разных старост для всех кружков.
Проверьте условие Холла для подмножеств кружков.
Для одного кружка вариантов \(2\). Для любых двух кружков объединение списков содержит все три имени или хотя бы два имени. Для трёх кружков объединение равно \(\{a,b,c\}\), имеет размер \(3\). Условие Холла выполнено, значит, существует система различных представителей. Например, \(A_1\to a\), \(A_2\to b\), \(A_3\to c\).
Первое явное применение Холла.