Question 78
Let $\mathcal{S}$ be a set of size $n$, and $k$ be a positive integer. For each $1 \leq i \leq k n$, there is a subset $S_{i} \subset \mathcal{S}$ such that $|S_{i}|=2$. Furthermore, for each $e \in \mathcal{S}$, there are exactly $2 k$ values of $i$ such that $e \in S_{i}$. Show that it is possible to choose one element from $S_{i}$ for each $1 \leq i \leq k n$ such that every element of $\mathcal{S}$ is chosen exactly $k$ times.