[Math] how to create a schedule for 9 teams playing x number of games no team can play same team twice no team can play same game twice

combinatorial-designscombinatorics

I am setting up a minute to win it challenge for a party. I have 9 teams of 5 players each. Each round will be head to head challenge with one team idle per round. All games are played simultaneously. there will be stations set up with a different game at each station. Teams will rotate through each station/game.
Rules: no team will play the other team twice, no team will play the same game twice
How many games do I need to do this? How do I determine the schedule per round?

I am not a mathematics person so simpler answers or equations would be appreciated. Some of the answers I have read are over my head or are displaying complete graphs which I cannot interpret.

Best Answer

Here is a $9$-round schedule. This is optimal because there are $\binom 92=36$ pairs of teams, and each round takes care of four pairs.

${}$	G1	G2	G3	G4	G5	G6	G7	G8	G9
R1	3/5	7/8	2/6	1/4
R2		4/6	8/9	3/7	2/5
R3			5/7	9/1	4/8	3/6
R4				6/8	1/2	5/9	4/7
R5					7/9	2/3	6/1	5/8
R6						8/1	3/4	7/2	6/9
R7	7/1						9/2	4/5	8/3
R8	9/4	8/2						1/3	5/6
R9	6/7	1/5	9/3						2/4

I found this using the idea presented in Anders Kaseorg's solution to a similar scheduling problem, together with brute force search to find the parameters which work.

Related Solutions

[Math] Scheduling a team based activity with 10 different teams and X different games. Every team must meet each other ONCE but never twice,

Here is a proposed schedule with 9 rounds of 5 matches each: http://tournamentscheduler.net/schedule/NjkwMTM0ODg2
This is the best possible since you need $10\times 9/2=45$ matches and you can have at most 5 matches per round.
Here is a lovely explanation of how to construct such "round robin" tournaments: http://nrich.maths.org/1443
Here is the tool used for the above schedule: http://tournamentscheduler.net/

[Math] Schedule 8 teams for 6 events. Each team plays each event twice.

Using the constraint solver MiniZinc, I arrived at the following:

            1   2   3   4   5   6   7   8   9   10  11  12  
Beer Pong                   AC  BF  AE  BD  CG  DH  EG  FH
Beerball                    EG  DH  CG  FH  AE  BF  AC  BD
Can Jam     BG  AH  EF  CH  BD              DF  CE      AG
Corn Hole   CF  DE  AB  DG  FH                  AG  BH  CE
Beersbee    EH  FG  CD  BE      AG  DF  AC  BH          
Flip Cup    AD  BC  GH  AF      CE  BH  EG          DF

As a bonus beyond what was asked for in the question, I added constraints to prevent that teams have to play the same event in the next round. Also, additional constraints make sure that each team plays against all other teams, but the teams do not play against the same team in the next round.

The solution is found in under two seconds.

The MiniZinc code:

% number of rounds depends on the number of events and the
% number of times events are played by every team
int: NoOfEvents = 6;
int: EventPlaysPerTeam = 4;
int: NoOfRounds = EventPlaysPerTeam * NoOfEvents;
int: NoOfTeams = 8;
set of int: Teams = 1..NoOfTeams;  
set of int: Events = 1..NoOfEvents;
set of int: Rounds = 1..NoOfRounds;

array[Events] of string: 
    eventName = ["Beer Pong", "Beerball", "Can Jam", "Corn Hole", "Beersbee", "Flip Cup"];
array[Teams] of string:
    teamName = ["A", "B", "C", "D", "E", "F", "G", "H"];

%  decision variables
array[Rounds, Events, Teams] of var bool: ret;

%  in every round, every team plays exactly one event
constraint
    forall(r in Rounds, t in Teams)(
      1 == sum([ret[r,e,t] | e in Events])
    );

%  in every round, no or two teams participate in a given event
constraint
    forall(r in Rounds, e in Events)(
       let { var int: occ = sum([ret[r,e,t]| t in Teams]) } in (occ == 0) \/ (occ == 2)
    );

%  every team plays every event a certain number of times
constraint
     forall(e in Events, t in Teams)(
        EventPlaysPerTeam == sum([ret[r,e,t] | r in Rounds])
     );

%  no repetitions
constraint
    forall(e in Events, r1 in Rounds, r2 in Rounds, t1 in Teams, t2 in Teams where (r2 > r1) /\ (t2 > t1))(
      (ret[r1,e,t1] /\ ret[r1,e,t2]) -> (not (ret[r2,e,t1] /\ ret[r2,e,t2]))
    );

%  play every other team at least once
constraint
    forall(t1 in Teams, t2 in Teams where t2 > t1) (
      exists(r in Rounds, e in Events)(ret[r,e,t1] /\ ret[r,e,t2])
    );

%  different event in subsequent round
constraint
    forall(e in Events, t in Teams, r in Rounds where r < NoOfRounds)(
       ret[r,e,t] -> not ret[r+1,e,t]
    );

%  different team pair in subsequent round
constraint
    forall(e1 in Events, e2 in Events, t1 in Teams, t2 in Teams, r in Rounds where (e1 != e2) /\ (t1 < t2) /\ (r < NoOfRounds))(
       (ret[r,e1,t1] /\ ret[r,e1,t2]) -> not (ret[r+1,e2,t1] /\ ret[r+1,e2,t2])
    );

solve satisfy;

output 
[ if r == 1 then "\t\t" else "" endif ++ show(r) ++ "\t" | r in Rounds] ++
[ if r*t==1 then "\n    " ++ eventName[e] ++ "" else "" endif ++ 
  if t == 1 then "\t" else "" endif ++
  if fix(ret[r,e,t]) then teamName[t] else "" endif
  | e in Events, r in Rounds, t in Teams ];

Best Answer

Related Solutions

[Math] Scheduling a team based activity with 10 different teams and X different games. Every team must meet each other ONCE but never twice,

[Math] Schedule 8 teams for 6 events. Each team plays each event twice.

Related Question