Combinatorial problem: constructing certain subsets of a set of size eight. I'd like to find eight subsets $S_1$, $S_2$,$\ldots$,$S_8$ of $\{1,2,3,\ldots,8\}$ with the following properties:
1) Each $S_i$ has size 3, and each $i$, $1\leq i\leq 8$, is in precisely three of the $S_i$.
2) The $S_i$ have a unique "system of distinct representatives". That is, there is only one way of choosing elements $x_i\in S_i$ such that all the $x_i$ are
distinct, or equivalently that $\{x_1,x_2,\ldots,x_8\}=\{1,2,3,\ldots,8\}$.
I don't know whether such subsets should exist. I tried starting with $S_i=\{i,i
+1,i+2\}$ (modulo 8), so e.g. $S_5=\{5,6,7\}$ and $S_8=\{8,1,2\}$; this satisfies (1), and then I tried messing around changing a few elements about to get (2) to work, but I failed. There's a finite field of size 8 but I couldn't see a natural
way of constructing eight subsets of size 3 that would work. Similarly there's a
finite field of size 9 but I couldn't see a natural way of constructing eight subsets of its multiplicative group of size 3 that would work. This sort of thing
is a long way from my area and I thought I should ask in case I'd missed something.
 A: If Wikipedia's entry on Hall's Marriage Theorem here is to be believed, this is not possible. Assumption (1) implies that the $S_i$ satisfy Hall's Marriage Condition, so by Marshall Hall's variant of Hall's Marriage Theorem there are always at least six systems of distinct reps.
A: The argument in the comments of the accepted answer is faulty.  Consider the set system:  $$\big(123,123,123,124,125,126,127,128\big).$$  It has the SDR $(1,2,3,4,5,6,7,8)$.  If we delete it, we obtain: $$\big(23,13,12,12,12,12,12,12\big)$$ which doesn't have an SDR.  The problem is that Marshall Hall Jr's extension to Latin rectangles doesn't apply here; the column sets of Latin rectangles have stronger assumptions than those imposed on the sets $S_i$.  However, his lower bound $3!$ still applies (Wikipedia ref.).
This question is equivalent to asking if there is a $8 \times 8$ $(0,1)$-matrix with exactly three $1$'s in each row with permanent $1$.  We know it's not possible, by the $3!$ lower bound.  The above example corresponds to the matrix:
$$\left(\begin{array}{cccccccc} 1 & 1 & 1 & 0 & 0 & 
0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 
1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 
0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 
1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 
0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 
1 \\ \end{array}\right)$$
which has permanent $3!$.  So the minimum is achieved by this example.
