1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Please include your thoughts and efforts in this and future posts. Formatting tips here. $\endgroup$ – Em. Jan 8 '16 at 22:10
  • $\begingroup$ 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. $\endgroup$ – Morgan Rodgers Jan 9 '16 at 9:06
  • $\begingroup$ @probablyme thanks, I've added some formatting, about my thoughts - see below $\endgroup$ – kgs Jan 10 '16 at 8:24
  • $\begingroup$ @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. $\endgroup$ – kgs Jan 10 '16 at 8:27
  • $\begingroup$ @kgs Do the diagonals work (looping around)? $\endgroup$ – Morgan Rodgers Jan 10 '16 at 8:50
1
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ Thank you for the nice explanation. One further note: The OEIS Sequence of the maximal number of mutually orthogonal Latin squares gives a link to this pretty picture of a solution to the OP's problem. $\endgroup$ – jpvee Feb 17 '16 at 6:21

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.