Skip to main content
MathOverflow

Return to Question

added 798 characters in body
Source Link
anon
anon
  • 303
  • 1
  • 8

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

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.

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.

Source Link
anon
anon
  • 303
  • 1
  • 8

How many ways to partition a group of people?

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.