# Problem regarding systems of representatives.

You probably know Hall's theorem:

The family $\mathcal{S} = ( S_1, S_2, \dots, S_m)$ has an SDR(system of distinct representatives) if and only if for each $k = 1, 2, \dots, n$ and each choice of $k$ distinct indices $i_1, i_2, \dots, i_k$ from $\{1, 2, \dots, n\}$, $$\vert S_{i_1} \cup S_{i_2} \cup \dots \cup S_{i_k} \vert \ge k;$$ in short, every $k$ sets of the family collectively contain at least $k$ elements.

Now we reformulate the problem.
Suppose $x_1 \in S_1, \dots, x_m \in S_m$, where $x_1, \dots, x_m$ are not necessarily distinct. Then we say $x_1, \dots, x_m$ is a system of representatives (a.k.a. SR) of $S_1, \dots, S_m$. Show that $S_1, \dots, S_m$ has an SR s.t. each element occurs at most $r$ times if and only if for each $k = 1, 2, \dots, n$ and each choice of $k$ distinct indices $i_1, i_2, \dots, i_k$ from $\{1, 2, \dots, n\}$, $$r\vert S_{i_1} \cup S_{i_2} \cup \dots \cup S_{i_k} \vert \ge k.$$ I know how to prove Hall's theorem. And the "only if" part of the new problem is pretty trivial. However, I'm having difficulty applying the method used to prove Hall's theorem to this new problem.

Define $R={1, 2, \dots, r}.$ Let $A_i = S_i \times R$, $i=1,2,\dots,m$ ,where "$\times$ " stands for Cartesian product.
Then for each $k=1,2,\dots,n$ and each choice of $k$ distinct indices $\{i_1, i_2, \dots, i_k\}$, we have $$\vert A_{i_1} \cup A_{i_2} \cup \dots \cup A_{i_k}\vert = \vert (S_{i_1} \cup S_{i_2} \cup \dots \cup S_{i_k}) \times R \vert \ge \frac{k}{r}r = k.$$ Hence $\{A_{1} , A_{2} , \dots ,A_{m}\}$ has an SDR $\{(x_1,n_1),(x_2,n_2),\dots,(x_m,n_m)\}$. Assume $x_1=x_2=\dots=x_{r+1}.$ However, this cannot happen since there must exist $j,k \in \{1,2,\dots,r+1\}$ s.t. $n_j=n_k.$ This means $(x_j,n_j)=(x_k,n_k)$, which contradicts with the fact that $\{(x_1,n_1),(x_2,n_2),\dots,(x_m,n_m)\}$ is an SDR.
Therefore we can conclude that $\{x_1,x_2,\dots,x_m\}$ forms a SR of $\{S_1,S_2,\dots,S_m\}$ s.t. each element occurs at most $r$ times.