3
$\begingroup$

I am organizing quiz for the university and I am having some problems with creating good schedule for this.

The tournament format is as follows: There are 6 * k players participating {k could be 7,8,9,10,11}
The game is split into 6 rounds.
For each round k teams are formed(each team consist of 6 players).

What I would like to achieve(from most important to least important):
- Maximize amount of people every person meet across all rounds(ex. in 6 round game in ideal case everybody will play with 30 different men);
- Minimize player pair duplication across different rounds(ex. player A shouldn't consequently meet player B in his team in 3 or 4 rounds);
- Insure, that formula used is fair for everybody.

For now I am using schedule, generated via brute force(for 42 persons). It guarantees, that every man would meet at least 23 different players in the game and each two people would not meet more than 3 times. I suppose there should be generic algorithm for such problem, but I have no idea where to dig. Any help would be appreciated.

$\endgroup$
  • $\begingroup$ Not that it helps, but... you are asking for a 6-uniform hypergraph that can be decomposed into 6 perfect matchings, and you want any two vertices to be in at most one edge. You would also like it to be "fair for everybody" so let's say vertex transitive would be nice. $\endgroup$ – Pat Devlin Dec 23 '16 at 1:05
  • $\begingroup$ What does the "fair for everybody" mean exactly in the case that no pair of players meet twice? For $k\geq 6$ a player can't meet everybody, so there always is someone who doesn't get to meet the guy who knows everything and makes their team win every time. But on the other hand if you make the seeding randomly, everyone is treated equally a priori. $\endgroup$ – Janne Kokkala Dec 23 '16 at 9:57
2
$\begingroup$

For $k=7,\dots,11$, you can fulfil the two first conditions using a set of $6$ mutually orthogonal Latin rectangles (MOLR) of size $6\times k$ (actually $5$ would be enough, see note at the bottom). They exist when $k\geq 7$ is a prime power and apparently also when $k=10$ (see Table 3.118 in Handbook of Combinatorial designs).

An $m\times n$ Latin rectangle ($m \leq n$) is an $m\times n$ array of symbols from a set of size $n$ (say $0,1,\dots,n-1$) such that every row contains each symbol exactly once and every column contains each symbol at most once. Two Latin rectangles are mutually orthogonal if there is no pair of positions that have the same symbol in the first rectangle and have the same symbol in the second rectangle.

Here, each position corresponds to a player and each rectangle corresponds to a round. The symbol tells the player's team in the round. There are $6$ of each symbol in every rectangle so the teams have $6$ players, and orthogonality means that no pair of players is on the same team twice.

Note: The requirement that the rectangles are Latin is not necessary in this case (as rows and columns don't mean anything), only the condition that each symbol occurs $6$ times in each rectangle is used. This can be used to add another round using a rectangle that has $0$ in the first column, $1$ in the second column etc., so in general you need only $n-1$ MOLR for $n$ rounds.

$\endgroup$
  • $\begingroup$ To add (I'll include this in the answer later if I have more to edit) if you're not familiar with Latin squares: For prime power $k$, you can generate $k-1$ MOLS of order $k$ here and take the first $6$ rows of first $6$ squares to get the rectangles. For $k=10$ I don't know the construction off the top of my head. $\endgroup$ – Janne Kokkala Dec 23 '16 at 10:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.