Suppose there are $n$ people, and a task that must be done at each time step that requires exactly $k \leq n$ people to be completed.
We want to create a "fair" repeating schedule that assigns $k$ people to perform the task at each time step. The schedule must meet a few requirements to be fair:
- Each of all ${n \choose k}$ combinations of people must be scheduled for at least one time stamp.
- Each combination of people appears in the schedule the same number of times as all other combinations of people.
- Each individual person's schedule is identical, modulo a shift in the start time. In other words, each person has the same list of intervals between their assignments.
How could we find a shortest schedule that meets these requirements? It seems somewhat related to block design.
Examples
For example, if $n = 3$ and $k = 2$, then a shortest schedule would be: $$(1, 2), (1, 3), (2, 3)$$
If $n = 4$ and $k = 2$, then the shortest schedule I've come up with is: $$(1, 3), (1, 2), (3, 4), (2, 4), (1, 4), (2, 3), (1, 3), (3, 4), (1, 2), (2, 4), (2, 3), (1, 4)$$
For this one, person $1$'s individual schedule is: $$(Y, Y, N, N, Y, N, Y, N, Y, N, N, Y)$$ person $2$'s schedule is: $$(N, Y, N, Y, N, Y, N, N, Y, Y, Y, N)$$ which is identical to $1$'s but shifted three spots left. Similarly, persons $3$ and $4$ have the same schedule shifted 6 and 9 spots left, respectively.
Equivalent Formulation
Another way to think about this problem is as a "spoke design" problem. We want to design a set of spokes that can be overlaid on itself $n$ times to fill each slot exactly $k$ times. For example, in the $n = 4$, $k = 2$ case, a fair schedule would consist of the following "spokes" represented by blue dots:
This set of spokes can be overlaid on itself 4 times (in different orientations) to fill each point along the circle exactly twice, while representing all possible combinations an equal number of times (in this case each combination appears twice).
