9
$\begingroup$

My friend (who is a medical student!) posed me the following question:

There are 70 people, and you want to split them up into 10 groups of 7 people each. Two such partitions are "compatible" if no two individuals are together in the same group in both. What is the maximal number of compatible partitions you can form?

There is an obvious generalization here. When the number of groups is prime, there seems to be a pretty efficient way of generating lots of compatible partitions by rotating people in different increments. However, even though this particular case is in principle a ``finite computation,'' I don't see a feasible way to compute the answer.

[Edited in:] For the particular parameters in question, I already have a lower bound of 4 (from explicit construction) and the obvious upper bound of 11. Improvements on these would be interesting.

I am also interested in what one can say about the "general behavior" of the answer as the number of groups varies. As I mentioned already, one can easily produce lots of compatible partitions when the number of groups is prime (so for instance, I can produce 10 solutions in the case of 11 groups of 6 people). My instinct is that the answer should in some sense vary ``smoothly'' in the parameters, so I would be surprised if it depended on delicate arithmetic properties like the number of prime factors. A discussion of this issue, whether intuitive or precise, would be very welcome.

Improve this question
$\endgroup$
13
  • 5
    $\begingroup$ This is an example of a "social golfer problem", which asks for a maximal (70,10,1) block design with parallelism. You can read up on solution methods in this master's thesis, logic.at/prolog/sgp/sgp.html $\endgroup$
    – Zack Wolske
    Commented Mar 19, 2014 at 2:39
  • 8
    $\begingroup$ Why the close votes? This isn't high school combinations-and-permutations, it's a question about what turns out to be a significant and difficult research problem in combinatorial designs. $\endgroup$
    – Gerry Myerson
    Commented Mar 19, 2014 at 3:27
  • $\begingroup$ It is clear though that there can be a group of at most 11 such mutually compatible partitions, which in itself does not require research mathematics. The only part that does is the part that determines the actual value, and it is unclear from the question if the actual value is needed, or if the elementary estimate will suffice. $\endgroup$
    – The Masked Avenger
    Commented Mar 19, 2014 at 5:10
  • 1
    $\begingroup$ This is how participants are ideally assigned to the tables at Oberwolfach conferences. $\endgroup$
    – Roland Bacher
    Commented Mar 19, 2014 at 9:58
  • 2
    $\begingroup$ Your question is "what is the maximal $k$ which makes SGP ($10-7-k$) solvable". The SGP does not ask for a perfect solution, as the author notes on page 7 of the freely available thesis, and which should be clear from the simpler 10 week solution for 8 groups of 4. The thesis also includes an algorithm in ECLiPSe (page 48) for arbitrary numbers of golfers and groups, an SAT implementation, and gives a link to Warwick Harvey's page listing known (as of 2002) solutions, including 5 compatible partitions for yours. It really deserves more than a glance if you are researching this topic. $\endgroup$
    – Zack Wolske
    Commented Mar 19, 2014 at 15:41

1 Answer 1

Reset to default
6
$\begingroup$

I would be very surprised if it depended smoothly on the parameters. It is related to questions of block designs (and mutually orthogonal latin squares, finite planes, group divisible designs, etc.) which are famously quirky in their patterns.

Here is an improved lower bound of 5, from Warwick Harvey's page, which he attributes to Steve Prestwich, http://4c.ucc.ie/web/people.jsp?id=43. I bet there have been many improvements in constraint logic programming in the last 12 years, but who knows if anyone has looked at this specifically.

[[6, 14, 22, 39, 44, 46, 48], [1, 26, 34, 43, 53, 67, 70], [30, 36, 40, 47, 51, 54, 56], [3, 21, 28, 31, 33, 41, 65], [8, 11, 17, 38, 57, 59, 68], [13, 20, 23, 25, 49, 52, 63], [10, 12, 24, 29, 32, 35, 42], [2, 5, 7, 16, 19, 37, 50], [4, 15, 18, 58, 60, 66, 69], [9, 27, 45, 55, 61, 62, 64]]

[[22, 25, 27, 33, 34, 50, 59], [5, 12, 18, 31, 61, 67, 68], [10, 26, 37, 48, 51, 57, 65], [2, 3, 9, 35, 39, 40, 70], [4, 16, 20, 28, 29, 46, 54], [1, 6, 8, 52, 56, 62, 66], [17, 30, 42, 44, 60, 63, 64], [13, 24, 41, 43, 47, 55, 58], [19, 23, 32, 38, 45, 53, 69], [7, 11, 14, 15, 21, 36, 49]]

[[2, 4, 14, 17, 34, 41, 61], [29, 33, 37, 45, 47, 66, 68], [12, 20, 38, 39, 43, 60, 65], [8, 15, 19, 25, 44, 51, 67], [18, 21, 22, 32, 40, 57, 62], [5, 9, 24, 26, 28, 36, 52], [6, 7, 10, 13, 27, 30, 53], [35, 48, 49, 54, 59, 64, 69], [1, 3, 11, 16, 23, 42, 58], [31, 46, 50, 55, 56, 63, 70]]

[[30, 43, 50, 52, 57, 61, 69], [14, 16, 18, 47, 64, 65, 70], [25, 29, 31, 36, 48, 53, 62], [19, 21, 27, 39, 42, 54, 68], [5, 8, 10, 34, 45, 58, 63], [6, 15, 23, 28, 37, 40, 59], [2, 11, 12, 13, 26, 44, 56], [9, 32, 41, 46, 49, 51, 60], [1, 4, 7, 33, 35, 38, 55], [3, 17, 20, 22, 24, 66, 67]]

[[15, 32, 34, 52, 55, 65, 68], [2, 18, 28, 42, 43, 45, 48], [7, 8, 22, 23, 54, 60, 70], [24, 37, 39, 49, 53, 56, 61], [3, 4, 5, 27, 44, 47, 57], [13, 16, 17, 33, 51, 62, 69], [1, 12, 19, 36, 41, 59, 63], [10, 11, 25, 40, 46, 64, 66], [6, 9, 21, 29, 38, 50, 67], [14, 20, 26, 30, 31, 35, 58]]

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .