To start, let us introduce Steiner (1796-1863) system with parameters $latex (n, r, t)$. There is a set of $latex n$ elements, and one would like to find a collection $latex F$ of subsets of size $latex r$ so that every $latex t$-tuple of elements appear in exactly one member of the collection. Since each $latex r$-tuple contains $latex {r \choose t}$ $latex t$-tuples, it is clear that $latex {r \choose t}$ must divide ${n \choose t}$. More generally, for any $latex 0 \le i \le t$, $latex {r -i \choose t-i}$ must divide $latex {n -i \choose t-i}$ (exercise).* Is this necessary divisibility condition sufficient ?*

A famous related problem was posted by Kirkman (1850) known as the “15 school girls problem”: There is a class of 15 students in a private girl school. The girls want to walk in groups of three every day of the week, but…

View original post 1,075 more words