Problem
COM-B2-M08-P012 Section Representatives
#12
★★★☆☆ Level 3 of 5
Each of \(n\) sections contains some students. Prove that one can choose a different representative from each section if and only if the union of any \(k\) sections contains at least \(k\) students.
Reformulate as an SDR.
If representatives are chosen, then any \(k\) sections have \(k\) distinct representatives, all lying in the union of these sections. Therefore the union contains at least \(k\) students.
Conversely, the condition on unions is Hall's condition for the student sets corresponding to the sections. By Hall's theorem, an SDR exists.
Hall's theorem in set language.