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
    It seems you mean "no two sets share more than one element"?2012-08-24
  • 1
    This is called the *social golfer problem*. According to [MathWorld](http://mathworld.wolfram.com/SocialGolferProblem.html) this is an unsolved problem, but I'm not sure whether that means that the first part of your question can't be answered. Here are some more links: [math.SE](http://math.stackexchange.com/questions/69325), [Math Games](http://www.maa.org/editorial/mathgames/mathgames_08_14_07.html), and [a page by Warwick Harvey](http://web.archive.org/web/20050308115423/http://www.icparc.ic.ac.uk/~wh/golf/).2012-08-24
  • 0
    Actually the Math Games link contains a solution to the $E=28$, $P=4$ instance you're particularly interested in.2012-08-24
  • 0
    joriki- thanks for the links. Yes, I do mean that no two sets share more than one element.2012-08-24
  • 0
    @joriki- the articles you mentioned do suggest to me that both questions are generally unsolved. That's disappointing, but the specific solutions that have been found are all I needed (if not all I wanted). Thanks for your help.2012-08-24
  • 0
    aka *Steiner Triples* aka "Kirkman's schoolgirl problem"2016-09-18
  • 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