3
$\begingroup$

I have a seemingly simple question. I'm holding a Beer Olympics at my house tomorrow. There are 8 teams competing in 6 different events (Beer Pong, Beerball, Can Jam, Corn Hole, Beersbee, and Flip Cup). Each event is seeing two teams compete. Is there a way to arrange the schedule so that each team plays each event twice? I understand teams will play some teams twice in different events, but I don't want them to play the same event against the same opponent they played the first time (example - team 1 plays team 2 in cornhole, later on team 1 plays a different team in cornhole).

Round 1: All 6 events can happen at the same time (Obviously only 4 of the games will be played at once due to 8 teams) Round 2: All 6 events happen at the same time. And so on until Round 12.

$\endgroup$
  • 1
    $\begingroup$ Fun. And I'm sure the answer is yes, your schedule is possible; the constraints are relatively loose. $\endgroup$ – Joffan Jun 17 '16 at 15:03
  • $\begingroup$ Can someone come up with the schedule please? $\endgroup$ – Chris Brotherton Jun 17 '16 at 15:34
  • $\begingroup$ And I guess you don't want teams playing each other in more than two sports... and every pair of teams does have to play each other at something. $\endgroup$ – Joffan Jun 17 '16 at 15:40
  • $\begingroup$ Ideally id like every one of the 8 teams to play every sport twice, and play as many different opponents as possible. I know every team will play each team once, and 5 of the teams twice. $\endgroup$ – Chris Brotherton Jun 17 '16 at 15:47
2
$\begingroup$

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:

set of int: Teams = 1..8;  
set of int: Events = 1..6;
set of int: Rounds = 1..12;

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 twice
constraint
     forall(e in Events, t in Teams)(
        2 == 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 < 12)(
       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 < 12))(
       (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    " ++ show(eventName[e]) ++ "" else "" endif ++ 
  if t == 1 then "\t" else "" endif ++
  show(if ret[r,e,t] then teamName[t] else "" endif) 
  | e in Events, r in Rounds, t in Teams ];
$\endgroup$
0
$\begingroup$

In the following arrangement, everyone plays everyone once or twice.
Four teams play all six games twice; the others play one game three times; always against different opponents.
\begin{array}{c|c|l|l} Rounds&Teams&Games\\ 1,2& AB,CD,EF,GH & 2,3,5,6&5,6,2,3 \\ 3,4& BC,DE,FG,HA & 1,6,4,3&4,3,1,6 \\ 5& AC,EG,BD,FH& 2,5,1,4 \\ 6& AG,CE,BH,DF & 5,2,4,1 \\ 7,8& AD,GB,EH,CF& 1,6,4,3&4,3,1,6 \\ 9,10& DG,BE,HC,FA& 2,3,5,6&5,6,2,3 \\ 11,12& AE,BF,CG,DH& 1,2,4,5&4,5,1,2\\ \end{array}

$\endgroup$
  • $\begingroup$ Thank you but that wont work. All teams have to play all six games at least once. Points for each event are different so it wouldn't be fair for total scores. $\endgroup$ – Chris Brotherton Jun 17 '16 at 18:40
  • $\begingroup$ Four teams (A,B,E,F) play six games twice each. Four teams play one game three times, one game once, and four games twice each. $\endgroup$ – Empy2 Jun 17 '16 at 18:41
  • $\begingroup$ You could replace Round 6 with a version of Round 5 but different games; but then you wouldn't get AG,CE,BH or DF $\endgroup$ – Empy2 Jun 17 '16 at 18:47
  • $\begingroup$ Still doesn't work. All teams have to play all six games at least once but no more than twice. $\endgroup$ – Chris Brotherton Jun 17 '16 at 19:38
  • $\begingroup$ If you replace round 6 with AC5,EG2,BD4,FH1 then every team plays every game twice; and plays six of the other seven teams twice each. $\endgroup$ – Empy2 Jun 17 '16 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.