> [!NOTE] Definition (System of Distinct Representatives) > Let sets $A_{1},\dots,A_{n}$ be [[Sets|set]] $X$ their union. A system of distinct representatives (SDR) for this set system is a set $\{ x_{1},\dots,x_{n} \}\subseteq X$ such that: > 1. $x_{i} \neq x_{j}$ for every distinct $i,j\in[n]$ (distinct elements), and > 2. $x_{i}\in A_{i}$ for every $i\in[n]$ (every set contributes a unique element). > [!Example] Examples > - Suppose that there are $n$ tasks that need to be done and each task has a set of workers qualified to perform the task. An SDR in this scenario would correspond to assigning workers to the tasks in such a way that every task is performed by someone qualified to do so and no worker performs two different tasks. > - There are $n$ student clubs at a university. A student can be a member of multiple clubs. Each club needs to send a representative to a student council in the university, in such a way that no person represents more than one club at the council. This is an SDR. # Properties > [!NOTE] Theorem (Existence of SDR, Hall's theorem) > Sets $A_{1},\dots,A_{n}$ have an SDR iff $\forall I \subset [n], \qquad \left\lvert \bigcup_{i\in I} A_{i} \right\rvert \geq \lvert I \rvert. $(This condition is known as *Hall's condition*). >See [[Hall's Theorem|Proof + Examples]].