Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$,





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

share|cite|improve this question
It seems you mean "no two sets share more than one element"? – joriki Aug 24 '12 at 13:36
This is called the social golfer problem. According to MathWorld 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, Math Games, and a page by Warwick Harvey. – joriki Aug 24 '12 at 13:52
Actually the Math Games link contains a solution to the $E=28$, $P=4$ instance you're particularly interested in. – joriki Aug 24 '12 at 14:08
joriki- thanks for the links. Yes, I do mean that no two sets share more than one element. – Mark R. Aug 24 '12 at 17:53
@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. – Mark R. Aug 24 '12 at 18:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.