Need to split 2n teams into n different games with no team meeting another team or playing a game more than once

combinatorial-designscombinatorics

I've found multiple similar questions, but none answering this case, and I can't manage to extrapolate from the other answers. The closest I've found is this one.

Here is my problem:
I have 10 different mini-games, and 20 teams. I also have (ideally) only 10 timeslots, or rounds. Every team needs to play every game exactly once, and every game they will be facing-off against another team.

I don't need every team to face every other team. Although, I would like them to never face the same team twice.

I've created a brute-force code which picks a random permutation of games for team 1, then picks games for every team after that, ensuring that everything remains valid (2 teams need to be at the same game in the same round). I then compute the amount of "unique encounters" (meaning a team facing off against another team they haven't seen before), and try to maximize that.

Ideally then, for 20 teams and 10 games, I'm looking for every team to have 10 unique encounters, so a total of 200 unique encounters.

I've managed to find perfect solutions for up to 10 teams and 5 games (example below), but the way I'm approaching the problem is so exponential that I haven't found a perfect solution for 12 teams and 6 games (best I've found is 70 uniques out of 72, so only 2 teams meeting twice), let alone for 20 teams and 10 games. The best I've found for 20 teams and 10 games is 182 uniques out of a possible 200.

Example for 10 teams and 5 games:

Best representation, with 50 uniques and no team meeting less than 5 opponents:
          Round 1 Round 2 Round 3 Round 4 Round 5
Team 1       g3      g0      g2      g4      g1
Team 2       g3      g1      g4      g2      g0
Team 3       g1      g3      g0      g2      g4
Team 4       g2      g4      g1      g3      g0
Team 5       g0      g3      g1      g4      g2
Team 6       g4      g1      g0      g3      g2
Team 7       g1      g4      g2      g0      g3
Team 8       g4      g2      g3      g0      g1
Team 9       g0      g2      g4      g1      g3
Team 10      g2      g0      g3      g1      g4

I believe the problem can be re-written as:

Need to select 2n different permutations of a set of n items such that every item is in every position exactly twice, i.e. no item is in the same position more than 2 times.

It's obviously not feasible to brute force this for 20 teams and 10 games, so I see that my approach isn't the right one. From the other answers I've seen that I should be using an approach similar to colored graphs, but I have absolutely no experience with those.

Any help would be greatly appreciated, be it only a solution table for 20 teams and 10 games, or an actual algorithm to compute a solution for any n number of games, or even a hint of what to look for in order to create this algorithm myself.

Thank you!

Best Answer

Here is a schedule that works. Each row is a team, each column is a round, and the games are numbered $0$ to $9$.

${}$ R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
T1 $0$ $8$ $9$ $5$ $7$ $6$ $3$ $1$ $2$ $4$
T2 $4$ $1$ $8$ $9$ $6$ $7$ $0$ $2$ $3$ $5$
T3 $1$ $5$ $2$ $8$ $9$ $0$ $7$ $3$ $4$ $6$
T4 $7$ $2$ $6$ $3$ $8$ $9$ $1$ $4$ $5$ $0$
T5 $2$ $7$ $3$ $0$ $4$ $8$ $9$ $5$ $6$ $1$
T6 $9$ $3$ $7$ $4$ $1$ $5$ $8$ $6$ $0$ $2$
T7 $8$ $9$ $4$ $7$ $5$ $2$ $6$ $0$ $1$ $3$
T8 $3$ $4$ $5$ $6$ $0$ $1$ $2$ $7$ $8$ $9$
T9 $6$ $0$ $1$ $2$ $3$ $4$ $5$ $8$ $9$ $7$
T10 $5$ $6$ $0$ $1$ $2$ $3$ $4$ $9$ $7$ $8$
T11 $0$ $6$ $5$ $9$ $3$ $8$ $7$ $4$ $1$ $2$
T12 $7$ $1$ $0$ $6$ $9$ $4$ $8$ $5$ $2$ $3$
T13 $8$ $7$ $2$ $1$ $0$ $9$ $5$ $6$ $3$ $4$
T14 $6$ $8$ $7$ $3$ $2$ $1$ $9$ $0$ $4$ $5$
T15 $9$ $0$ $8$ $7$ $4$ $3$ $2$ $1$ $5$ $6$
T16 $3$ $9$ $1$ $8$ $7$ $5$ $4$ $2$ $6$ $0$
T17 $5$ $4$ $9$ $2$ $8$ $7$ $6$ $3$ $0$ $1$
T18 $4$ $5$ $6$ $0$ $1$ $2$ $3$ $7$ $9$ $8$
T19 $1$ $2$ $3$ $4$ $5$ $6$ $0$ $8$ $7$ $9$
T20 $2$ $3$ $4$ $5$ $6$ $0$ $1$ $9$ $8$ $7$

I found this by taking an orthogonal pair of $10$ by $10$ Latin Squares, and concatenating them vertically. In general, if you have $n$ different mini-games, each of which takes $k$ players, then you can get a schedule for $nk$ players to each play all the games over $n$ rounds without repeating teammates by concatenating together $k$ mutually orthogonal Latin squares. This known to be possible whenever $n$ is a prime power (and $k\le n-1$).

Related Question