Sets of n-1 elements
Task number: 3996
For \( n \ge 2 \), let \( A_1, \ldots, A_n \) be distinct sets, each other with at least \( n-1 \) elements.
Prove that for the set system \( (\bigcup_i A_i, \{A_1, \ldots, A_n \}) \) there is a system of distinct representatives.
Solution
The union of any at most \( n-1 \) sets contains at least one whole set, i.e. at least \( n-1 \) elements.
There are at least two different sets in the union of all \( n \) sets, their union has at least \( n \) elements.
Indeed the union of any two sets has at least \(n\) elements.
The Hall condition is thus fulfilled, and therefore there is a system of different representatives.
