Lesson 7

The answer to the previous question is negative, and there is a “local” reason for this: the clubs Chess, Math, Physics, Robotics are competing for three people (Alice, Bob, and Carol). Below, we prove that in general this is the only obstacle: a system of distinct representatives exists if and only if every subset of clubs has at least as many available people as the number of clubs.

Theorem (Hall, 1935). Let \(S_{1}, \dotsc, S_{m}\) be finite sets. There exists a system of distinct representatives for these sets if and only if for any \(1 \le k \le m\), the union of any \(k\) sets has at least \(k\) elements. In other words, there exist pairwise distinct \(x_{1} \in S_{1}, \dotsc, x_{m} \in S_{m}\) if and only if \[\left|\bigcup_{i \in I}S_{i}\right| \ge |I| \text{ for any }I \subseteq \{1, \dotsc, m\} \ .\]

Proof. We will prove this by induction on \(m\). The base case \(m=1\) is obvious, consider the step \(\{1, 2, \dotsc, m-1\} \to m\).

• Case 1:  for any \(1 \le k < m\), the union of any \(k\) sets contains more than \(k\) elements. Then it is straightforward to use the induction hypothesis. Assign an arbitrary element \(x \in S_{m}\) as the representative of the set \(S_{m}\). After this, remove \(x\) from all sets \(S_{1}, \dotsc, S_{m-1}\). It is easy to see that the induction hypothesis holds for the sets \(S_{1}, \dotsc, S_{m-1}\), so representatives can be chosen for them.


• Case 2:  the union of some \(1 \le k < m\) sets contains exactly \(k\) elements. For these \(k\) sets, a system of representatives can be found by the induction hypothesis. Remove these \(k\) elements from all remaining sets and show that the condition of the theorem holds for these sets after this (and then a system of representatives can be found for them by the induction hypothesis). Indeed, if there are \(s\) sets among the remaining ones that give a union of fewer than \(s\) elements, then if we return the removed \(k\) sets and \(k\) elements, we get \(k+s\) sets, the union of which has fewer than \(k+s\) elements (which contradicts the condition).

◼