4
$\begingroup$

Over at Wolves and Sheep on puzzling.stackexchange.com, noedne's answer involves repeatedly partitioning a group of 99 sheep into a series of "test groups" such that

  1. All but one sheep are tested six times.
  2. No pair of sheep shares more than one test.

This feels like it ought to be a well-studied combinatorics problem, something like a generalization of Kirkman's schoolgirl problem, but I can barely state the generalized problem, let alone figure out how to Google it!

The problem is:

Define a "partition of a set $S$ into $g$ groups" as a mapping $P : S \rightarrow [1..g]$.
Given a collection $S$ of $n$ elements, produce $k$ different $g$-group partitions of the collection, such that no pair of elements is ever in the same group together more than $M$ times.
That is, produce $k$ different partitions $P_0, P_1, \cdots, P_k$ such that $\forall s_1, s_2\in S, \sum_{i\in [1..k]}{\big(P_i(s_1)=P_i(s_2)\big)} \leq M$.

noedne's answer to Wolves and Sheep gives one viable solution for $n=99$, $g=11$, $k=6$, $M=1$: "Given a collection $S$ of 99 elements, produce 6 different 11-group partitions of the collection, such that no pair of elements is ever in the same group together more than once."

So I'm asking you, Math StackExchange: What is the name of this problem, and what is known about the space of parameters $(n,k,g,M)$ for which it is solvable?

$\endgroup$
  • $\begingroup$ Hmm, following the "related questions" links, I suspect that for $M=1$ (which is the most interesting case anyway), this is exactly the "Social Golfers Problem"; see e.g. math.stackexchange.com/questions/69325/… I'm not sure what happens when we let $M$ vary, though! $\endgroup$ – Quuxplusone Apr 21 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.