2
$\begingroup$

Today I came up with this problem:

Find all natural numbers $n$ such that there exist a family of $3$-element subsets of the set $\{1,2,...,n\}$ like $\mathbf F$ such that:

a) For all distinct $1\le a,b \le n$ there exists a unique element of $\mathbf F$ like $\mathbf A$ such that it contains both $a$ and $b$.

b) If $1\le a,b,c,x,y,z \le n$ are distinct and $\{a,b,x\},\{b,c,y\},\{c,a,z\}\in \mathbf F$, then $\{x,y,z\}\in \mathbf F$.

It's easy to prove that $n$ should be of forms $6k+1$ or $6k+3$. For $n=3$ it's obvious and for $n=7$ I found this example:

$\{1,2,4\},\{2,3,5\},\{3,1,6\},\{4,5,6\},\{7,1,5\},\{7,2,6\},\{7,3,4\}$.

But I couldn't go any further. Would anyone please tell me, how can I construct such examples for larger $n$'s? Or prove there is no such examples? Thanks

  • 0
    It would be interesting if you edited the question to explain how you came to this problem, by the way!2012-03-25

1 Answers 1

3

Let $E$ be a finite set, and let $S$ be a set of $3$-element subsets of $E$ satisfying your conditions. Let $0$ be a new symbol and let $V=E\cup\{0\}$.

Let $\star:V\times V\to V$ be the operation defined as follows:

  • first, the element $0$ is a zero for $\star$, so that $0\star v=v\star 0=v$ for all $v\in V$;

  • second, if $e\in E$, we let $e\star e=0$;

  • finally and most interestingly, if $x$, $y\in E$ are different, we define $x\star y$ to be the unique element of $E$ such that $\{x,y,x\star y\}$ is an element of $S$.

I claim that your second condition implies that $\star$ is associative—this can be proved by considering several cases (reflecting the form of the definition of $\star$) and I will leave all the fun to you. In any case, it follows immediately from the construction that then $(V,\star,0)$ is in fact an abelian group of exponent $2$. In particular, its order is of the form $2^m$ for some $n$. Consequently, $E$ has $2^m-1$ elements.

More: it follows from this construction that we can reconstruct all such systems $(E,S)$. Indeed, we can deduce from all this that for each $m\geq1$ there is exactly one Steiner triple system satisfying your 2nd condition of order $2^m-1$, which can be constructed as follows: $E$ is the set of points of the projective space $P^m(\mathbb F_2)$ of dimension $m$ over the field $\mathbf F_2$ with two elements, and $S$ is the set of projective lines in $E$. There are no systems satisfying your conditions for other orders.

N.B. These things can be constructed concretely pretty easily. Given $m$, let $E=\{1,\dots,2^m-1\}$, which is precisely the set of positive integers which can be represented in binary with at most $m$ digits and let $S$ be the set of all $3$-element subsets $\{a,b,c\}$ of $E$ such that $a\oplus b\oplus c=0$, where $\oplus$ denotes the bitwise XOR operation.

  • 0
    +1: I want to remark that the construction in the last paragraph is the set of (supports of) words of weight 3 in a [Hamming code.](http://en.wikipedia.org/wiki/Hamming_code)2012-03-25