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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email