How to arrange tournament with 4 rounds for 100 players with each player playing game in group of 10?

313 Views Asked by At

I have tournament with 4 rounds and 100 players. Each round consists of 10 games (groups) with 10 players playing together a game (so every round is $10 \times 10$).

Is it possible to schedule tournament that every player plays with another player in group at most once?

If not, how to maximize mixing of players?

Is there any general solution for n players, k groups and r rounds?

If everything else fails - how to "brute force" this kind of problem programatically? Genetic algorithm? Simulated annealing?

1

There are 1 best solutions below

1
On

This is a difficult problem related to combinatorial designs. You are attempting to construct what is called a $4$-net of order 10, which is a partial affine plane. It can be solved by looking at Latin squares; a Latin square of order $n$ is an arrangement of $n$ symbols in an $n \times n$ grid so that each symbol appears exactly once in each row and once in each column.

Here is the idea: we arrange our 100 points in a $10\times 10$ grid, each "round" will have matches numbered $0$ through $9$ and we will put this number in the grid to tell us which point is in which round. So we will have a grid for each round. Without loss of generality, take round 1 and 2 as $$\begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \end{bmatrix}$$ and $$\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &0\\ 1&1&1&1&1&1&1&1&1&1\\ 2&2&2&2&2&2&2&2&2&2\\ 3&3&3&3&3&3&3&3&3&3\\ 4&4&4&4&4&4&4&4&4&4\\ 5&5&5&5&5&5&5&5&5&5\\ 6&6&6&6&6&6&6&6&6&6\\ 7&7&7&7&7&7&7&7&7&7\\ 8&8&8&8&8&8&8&8&8&8\\ 9&9&9&9&9&9&9&9&9&9 \end{bmatrix}$$ Now your remaining rounds correspond to a Latin squares $L_{1}$ and $L_{2}$ that are orthogonal, that is, if you look at the positions in the grid, each ordered pair of symbols $(a,b)$ appears exactly once (that is, there is a unique $i,j$ so that $a$ appears at position $(i,j)$ in $L_{1}$ and $b$ appears at position $(i,j)$ in $L_{2}$).

Once you find a pair of orthogonal Latin squares of order 10, that will give you your solution. It is unknown if there exist sets of three mutually orthogonal Latin squares of this order, but you can find some information on creating a pair (essentially, creating one is easy, then you try to brute force a second orthogonal to the first). Since you are only looking for two more rounds, you can equivalently construct a single Graeco-Latin square (you will find lots of computational techniques if you look up this term).

This is indeed related to problems such as Kirkman's schoolgirl problem; for rounds of $6$ with $36$ players, this was Euler's 36 Officers problem.