Round Robin tournament, but no team can play the same game twice

Question

So, my school is organizing a charity event for some children who are going to be split into teams and play minigames against each other. Naturally, we want all the teams to face every other team and ensure that each team plays every single minigame only once.

We have decided that there will be 12 teams (even number, so it should work well) as well as 6 different minigames.

I have tried to find a website/tournament scheduling software, but none are capable of ensuring each team plays a different minigame/at a different location.

Here is my attempted program/roster: http://tournamentscheduler.net/schedule/Mzg1OTk0ODE5MQ , however, not every team plays every minigame.

NOTE: The whole day is about 3 hours, so it isn't necessary that each team plays every other team, but it is essential that each team plays at every minigame station against different teams.

Thank you so much :) I look forward to any responses I will receive.

Kind Regards

Joshua Lochner

Answer 1

I don't think this can work if you have an even number of games. (Wrong: see edit below.) But if you have 5 or 7 games (with 10 or 14 teams), then Chas Brown's solution works perfectly. Here is the seating plan for 5 games (the game stations are named A through E, and the teams are numbered 1 to 10):

          A  B  C  D  E
          -------------
Round 1:  1  2  3  4  5
          6  7  8  9  10

Round 2:  2  3  4  5  1
          10 6  7  8  9


Round 3:  3  4  5  1  2
          9  10 6  7  8

Round 4:  4  5  1  2  3
          8  9  10 6  7

Round 5:  5  1  2  3  4
          7  8  9  10 6

This is the problem of designing pairings for duplicate bridge tournaments, where instead of different games, we have different deals. See this link for a discussion of the different strategies; and note that the Mitchell Movement with an even number of tables ends up with each pair having to skip one of the deals.

Edited to add: Especially Lime comments that a "perfect schedule" is possible when the number of games is a multiple of four (the so-called double-weave Mitchell Movement). Here is an example with eight games:

          A  B  C  D  E  F  G  H                A  B  C  D  E  F  G  H
          ----------------------                ----------------------
Round 1   1  2  3  4  5  6  7  8      Round 2   2  1  4  3  6  5  8  7
          9  10 11 12 13 14 15 16               16 11 10 13 12 15 14 9

Round 3   7  4  1  6  3  8  5  2      Round 4   4  7  6  1  8  3  2  5
          11 16 13 10 15 12 9  14               14 13 16 15 10 9  12 11

Round 5   5  6  7  8  1  2  3  4      Round 6   6  5  8  7  2  1  4  3
          10 9  12 11 14 13 16 15               15 12 9  14 11 16 13 10

Round 7   3  8  5  2  7  4  1  6      Round 8   8  3  2  5  4  7  6  1
          12 15 14 9  16 11 10 13               13 14 15 16 9  10 11 12

Edited again to add: As Chas Brown points out in the comments, this problem is just another disguise for Graeco-Latin squares, which means we can construct perfect schedules for all sizes except $2$ and $6$. This paper by D.A. Preece and B.J. Vowden has examples of $10\times 10$ Graeco-Latin squares.

Answer 2

(Ooops! BZZZT! Wrong...!!! Please un-vote me! In my 'solution' team 1 plays team 7 twice...)

Imagine seating the teams at a long table, with six seats on either side. Players on opposing seats will play games A, B, C, D, E, and F.

Start by seating teams 1-6 on one side of the table, and 7-12 on the other side.

After each round, each team player moves to the seat to THEIR right; with the person on the rightmost ends switching to the (now empty) leftmost seat on the SAME side of the table.

Then: each team plays each of the six games once; and no team plays the same opponent team twice. (I think that's what you want!)

Answer 3

Okay, so it looks like the answer to your problem is probably: it can't be done, because there are $6$ mini-games.

The problem you pose is close to (but not exactly the same as: see below) the problem of Graeco-Latin squares. For purposes of finding a solution, each of your $2n$ teams is assigned to a 'League': $n$ teams are in the 'Latin' league (and given arbitrary names $A, B, C$, etc.); while the other $n$ teams are in the 'Graeco' League (and given arbitrary names $\alpha, \beta, \gamma,$ etc.). In my failed solution, one side of the table was the 'Latin' league, and the other was the 'Graeco' league.

Now, if it is possible to make an $n \times n$ Graeco-Latin square, then you have your tournament: each row is a round, each cell is a pair of teams that will compete, and the column identifies which mini-game they should play in that round.

As the Wikipedia article notes, this is always possible if $n \neq 2$ or $n \neq 6$.

Now there is a difference between the problem of Graeco-Latin squares and your actual problem: in the former, no two teams from the same 'League' can play against each other; whereas you don't have two leagues, so potentially there might be solutions to your problem that don't also work as a Graeco-Latin square (because you might have a 'cell' that contains two Latin or two Graeco letters in it).

For $n=2$, this doesn't matter; it's pretty easy to see that there are no solutions in any case.

That leaves the problem of $n=6$, which unfortunately is your case! :). I haven't been able to determine if there is a proof that if a solution exists, it must then also be a G-L square (after suitable partitioning of the teams into two groups). Looking at that now...