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

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?

• Please include your thoughts and efforts in this and future posts. Formatting tips here. – Em. Jan 8 '16 at 22:10
• Hint: Lay 100 points out in a $10 \times 10$ grid. Take the 10 rows as the first round, and the 10 columns as the second round. Now you need two more rounds. – Morgan Rodgers Jan 9 '16 at 9:06
• @probablyme thanks, I've added some formatting, about my thoughts - see below – kgs Jan 10 '16 at 8:24
• @MorganRodgers yeah, thanks - that's was also my first step, but then it gets much harder in 3rd and 4th round What I've found is this problem is some kind of variation of Kikrman's schoolgirl problem or Social Golfer Problem. And that generalization probably does not exist - so that's why second question about some heuristics. – kgs Jan 10 '16 at 8:27
• @kgs Do the diagonals work (looping around)? – Morgan Rodgers Jan 10 '16 at 8:50

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} \ \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}$).
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.