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. 



How many ways to partition a group of people?
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]]


