# 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.

-
@armpit I really like this problem. I think you can ensure $2$ by starting with an example that satisfies $1$ and working backwards. – Rustyn Jan 25 '13 at 20:53
There is definitely a possibility that it is not possible. This is not some Olympiad question or anything; I don't know if such $S_i$ exist or not. – armpit Jan 25 '13 at 21:04
Oh, I've got it now; curses. I should have waited a couple more hours before posting! I've answered my own question. – armpit Jan 25 '13 at 22:34
It's totally ok to answer your own question here (even of you knew the answer in advance). And you don't need to mark the answer as "community wiki". – leonbloy Jan 25 '13 at 23:06
Oh I didn't know that; thanks. I thought I surely should post my answer to the question, because there was no point waiting for someone else to independently come up with the idea I'd come up with. On the other hand it seems a bit ridiculous to try and gain from it, so I'm happy to leave it CW. – armpit Jan 26 '13 at 15:10

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.

-
I would accept your answer too for completeness – Rustyn Jan 26 '13 at 2:19
I can't -- probably because I'm a new user. I have to wait 2 days after posting it. In fact I realised since then that I don't even need Marshall Hall's variant. Here's a direct proof that at least two SDR's exist: by Hall, one exists; now remove x_1 from S_1 and apply Hall again! One can perhaps use this technique to prove that there will be very many SDR's. – armpit Jan 26 '13 at 15:08
OK it's let me now. – armpit Jan 27 '13 at 23:41

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.

-
I was just removing one element from one of the sets, not the entire SDR. – armpit May 19 '13 at 8:10