Combinatorial problem: constructing certain subsets of a set of size eight.

Question

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.

Answer 1

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.

Answer 2

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.