Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to pick the minimum number of sets to cover $1,...,n$ such that if we pick $S_t$, then for all $i \in S_t$, we can not pick $S_i$ anymore.

What will be the minimum number of sets that we need to pick considering all possible permutations of the elements numbered $1,...,n$. We are not looking at a particular ordering of the numbers and sets (i.e. We want to know the expected number of sets needed to be picked to cover all the elements).

EDIT: We can also look at the problem from another viewpoint, not sure if this is any helpful way to look at it.

Consider those $n$ elements as just $n$ vertices of a $k$-regular graph and each $S_i$ is the neighborhood of $i$, i.e. $N(i)$. Now we want to pick the least number of neighborhoods so that the graph is completely partitioned.