Minimize player duplication in schedule

Question

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.

Answer 1

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.