Problem
COM-B2-M08-P020 Large Sets
#20
★★★★★ Level 5 of 5
There is a family of finite sets \(A_1,\ldots,A_n\). Each element belongs to at most \(r\) sets, and each set has size at least \(r\). Prove that the family has a system of distinct representatives.
For \(k\) chosen sets, count pairs “set, element”.
Take any \(k\) sets. They contain at least \(rk\) element occurrences in total, because each set has size at least \(r\). Each element in their union can be counted at most \(r\) times, since it belongs to at most \(r\) sets overall.
If the union size is \(u\), then \(rk\le ru\), so \(u\ge k\). Hall's condition holds for any \(k\) sets. Therefore an SDR exists.
A strong and very useful form of Hall via double counting.