3

I am planning a “beer Olympics” for me and my friends and I need to write out a schedule.

There are 9 teams (I know) and 6 games to play.

In the past we have had 8 teams and this was much easier.

I would like each team to play every other team at least once but not exceed in playing a team 3 times.

I want every team to play each game 2 times.

Teams cannot participate in more than one game per round. The last 2 years we did this, there was 12 rounds. I would like to stay close to that number.

Is this possible? I’ve been asking chat gpt all morning and I want to pull my hair out. If it’s not possible, if I added a game, would that be helpful? If I added a game that had 3 teams against each other, would that be helpful?

TIA!

Kat
  • 31

2 Answers2

2

You can solve the problem via integer linear programming. The minimum number of rounds is $14$, and here is such a schedule, where $i,j$ means that team $i$ plays team $j$:

r\g 1   2   3   4   5   6 
 1  1,2 4,8     5,7     3,6 
 2  4,7 6,8 2,9     1,3   
 3      3,7 1,9 5,8 2,4   
 4  3,9     4,7     6,8 2,5 
 5  1,3 6,9     2,7     5,8 
 6          1,8 3,4 2,6 7,9 
 7      5,9     1,6     
 8      1,2 3,6 8,9 4,5   
 9  7,8     2,5 1,3     4,6 
10  5,9     6,7     3,8 1,4 
11  4,8         2,6 5,7 3,9 
12  5,6 2,3     4,9     1,7 
13      4,7 3,5     1,9 2,8 
14  2,6 1,5 4,8     7,9

By request, here is the SAS code I used:

proc optmodel;
   num numTeams = 9, numGames = 6, numRounds = 14;
   set TEAMS = 1..numTeams;
   set GAMES = 1..numGames;
   set ROUNDS = 1..numRounds;
   set PAIRS = {i in TEAMS, j in TEAMS: i < j};

var AssignPair {PAIRS, GAMES, ROUNDS} binary;
   var UseRound {ROUNDS} binary;


min NumRoundsUsed = sum {r in ROUNDS} UseRound[r];


con AssignImpliesRound {<i,j> in PAIRS, g in GAMES, r in ROUNDS}:
      AssignPair[i,j,g,r] <= UseRound[r];


con PairCountRange {<i,j> in PAIRS}:
      1 <= sum {g in GAMES, r in ROUNDS} AssignPair[i,j,g,r] <= 3;


con PlayGameTwice {t in TEAMS, g in GAMES}:
      sum {r in ROUNDS} sum {<i,j> in PAIRS: t in {i,j}} AssignPair[i,j,g,r] = 2;


con OneGamePerTeamRound {t in TEAMS, r in ROUNDS}:
      sum {g in GAMES} sum {<i,j> in PAIRS: t in {i,j}} AssignPair[i,j,g,r] <= 1;


con OnePairPerGameRound {g in GAMES, r in ROUNDS}:
      sum {<i,j> in PAIRS} AssignPair[i,j,g,r] <= 1;


solve;


str sol {ROUNDS, GAMES} init '___';
   for {r in ROUNDS, g in GAMES} do;
      for {<i,j> in PAIRS: AssignPair[i,j,g,r].sol > 0.5} do;
         sol[r,g] = i||','||j;
         leave;
      end;
   end;
   print sol;
quit;
RobPratt
  • 45,619
1

I know an answer has already been posted, but I wanted to make something colorful anyway.

Each of the six games is a color. The $(i, j)$ cell's colors means teams $i$ and $j$ will play the respective games against each other.

  • Each team will play against every other team and do it at most twice (since every cell has at most two colors).
  • Every color should appear exactly twice in each row and column (if I didn't miss anything), so every team is playing every game exactly twice.
  • Didn't think much about the rounds, but I guess iterating over the diagonals won't be so bad.

Notice the table is symmetric.

enter image description here

Alma Arjuna
  • 3,759