3
$\begingroup$

Suppose $E$ elements are partitioned into sets of equal size $P$ (e.g. elements 1 through 9 could be partitioned as $\{1,3,7\}\{2,6,9\}\{4,5,8\}$). Clearly $P|E$.

Call two partitions with sets of equal size ‘orthogonal’ (for lack of a better adjective) if no two sets share more than one element. (So $\{1,2,4\}\{3,5,6\}\{7,8,9\}$ is orthogonal to the partition above, while $\{1,2,3\}\{4,5,6\}\{7,8,9\}$ is not since 1 and 3, as well as 4 and 5, are grouped together in both partitions.)

Call a set of partitions, all pairwise orthogonal, ‘complete’ if every two elements appear together exactly one set. For example, if $E=9$ and $P=3$,

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

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

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

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

is a complete set.

This question has two parts: first, for what values of $E$ and $P$ is there a complete set of orthogonal partitions? With a little bit of thought it is apparent that $(P-1)$ must divide $(E-1)$, but it is not obvious that this is sufficient. ($E=P^2$ always allows a solution, as does $P=2$ with $E\ge 2$. $E=15$, $P=3$ also has a solution, which I eventually found by trial and error.)

Second, if a complete set exists for $E$ and $P$, is there a procedure to find such a set? (I am particularly interested in $E=28$ and $P=4$.)

(Apologies for the invented notation and terminology; I am not a combinatorist.)

  • 0
    [Wikipedia for Kirkman's schoolgirl problem](https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem) includes the $E=15, P=3$ solution2016-09-18

0 Answers 0