Combinatorial design related to scheduling group activities (everyone tries every activity, no pair is together twice)

173 Views Asked by At

Trying to solve this problem led me to consider the following generalization.

Let $g$ and $p$ be positive integers. Imagine that you own $g$ distinct board games, where each game requires exactly $p$ people to play. You plan to host a game night, and invite exactly $p\times g$ friends over to play your games. You plan to do this over the course of $g$ rounds, where in each round, the group divides itself into $g$ groups of $p$ people, and each group plays a game. The goal is to do this in such that way that

  1. Everyone plays every game exactly once, and

  2. No pair of people play together more than once.

This is equivalent to finding a $g\times (gp)$ matrix such that each column is a permutation of $\{1,\dots,g\}$, each number in $\{1,\dots,g\}$ appears $p$ times in each row, and where any two columns agree in at most one place (each column is a player, each row is a round, the entry says which game that player plays in that round). When $p=1$, this is just a Latin square of order $g$.

My question is, for what values of $g$ and $p$ is this possible? Also, I am curious if anyone has seen this problem in the literature. This certainly bears a resemblance to the social golfer problem. Both this and the SGP involve dividing $pg$ people into $g$ groups of $p$ over the course of several rounds, such that no pair of people play together twice. The difference is that here, people are playing distinct games instead of splitting into unlabeled groups, so constraint $(1)$ does not make sense in the context of SGP and makes this problem distinct.

This is possible in the trivial cases where $g=1$ or $p=1$. Besides these, I know that $$g\ge p+1$$ is a necessary condition for a schedule to exist. Consider the $p$ people who play Monopoly (say) in the first round. In the next round, they must all play different games, so there must be at least $p$ other games besides Monopoly.

I suspect that this is also a sufficient condition, since I have only found positive results in this regime:

  • You can succeed with $p=2$, as long as $g$ is odd. For each $x,y\in \{0,1,\dots,g-1\}$, persons numbered $2x$ and $2y+1$ will play game number $x+y\pmod g$ during round number $x-y\pmod g$.

  • It is also possible when $(g,p)=(4,3)$ and $(5,4)$. I found the schedule for the former case by hand, and for the latter case by computer. However, I cannot see how the schedule I found would generalize. Here is the solution for $(g,p)=(4,3)$: $$ \begin{array}{|cccccccccccc|}\hline 1&1&1&2&2&2&3&3&3&4&4&4\\ 2&3&4&1&3&4&1&2&4&1&2&3\\ 3&4&2&4&1&3&2&4&1&3&1&2\\ 4&2&3&3&4&1&4&1&2&2&3&1\\\hline \end{array} $$

Therefore, I further ask is it indeed true that a schedule exists if and only if $g\ge p+1$?