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

combinationscombinatoricspermutationsstatistics

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

Best Answer

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.

Related Question