How to distribute groups over activities in rounds

Question

I typed out my problem in a Latex file and I will add an image of it here:

If anyone could help me how to solve this problem that would be amazing. Thank in advance.

Boris

Answer 1

If one restricts to the assignments where the $2n$ groups are partitioned into two sets (of size $n$), such that each group only competes against the groups in the other group, the problem is equivalent to the construction of an $n \times n$ Graeco-Latin square, which Wikipedia succinctly describes as, given sets $S$ and $T$, both of $n$ elements "an $n \times n$ arrangement of cells, each cell containing an ordered pair $(s, t)$, where $s$ is in $S$ and $t$ is in $T$, such that every row and every column contains each element of $S$ and each element of $T$ exactly once, and that no two cells contain the same ordered pair." Here, one may take $S$ and $T$ to be the sets into which the groups are partitioned, the rows to represent rounds, and the columns to represent activities.

Unfortunately for your sister, in 1901 Tarry proved Euler's conjecture that no such arrangement is possible for $n = 6$. So, for any solution to your problem, the (regular) graph whose vertices are groups and whose edges connect groups that compete against one another in some round cannot be bipartite, that is, there is no solution to your problem if you also ask that the $12$ groups be split into two set such that each group competes against exactly the 6 groups from the other set, and no group from its own set. To be clear it doesn't say that no solution to your problem exists, but it does say that one has to look harder for it. In fact, Graeco-Latin squares do exist for all $n \neq 2, 6$, and the $n = 2$ case is trivial, so $n = 6$ is the only interesting case for which your problem cannot be solved by such a square.