[Math] 36 Teams split into 4 groups of 9. There are 9 events and 9 rounds. A teams must face all other teams in the other groups.

combinatorics

Okay here is my problem. I am not sure if this is possible or not as the 8 hours i have spent on this havn't been the best.

There are 4 groups of 9 teams. So we have teams A1 to A9, B1 to B9, C1 to C9, D1 to D9.
The are 9 rounds of 9 different events. Each event can hold 1 team from each group. How do i make it so that each team faces every other team that isn't in their group exactly once and no team twice. And every team goes to each event once and no event twice.

Some background, this is for a school event where our school has 4 different houses. I have been put in charge of setting together the timetable for the day and the way the teams mvoe around the events. There is no way i am able to just have 2 houses face each other at an event as 4 teams from different houses has to compete at each event. Principle wants 9 teams for each house to compete.

Is this possible? If this isnt possible, would it be possible if the number of teams went down to 8 with the number of events go down to 8 and rounds go down to 8 also?

Thanks

Best Answer

Consider a $9\times9$ array, where the row represents the event and the column represents the round. For each house, arrange the $9$ copies numbers from $1$ to $9$ in the array, so that each number appears once in each row and each column. That is, make a $9\times9$ Latin square. Call these arrays $(a_{ij}),(b_{ij}),(c_{ij}),(d_{ij})$ for groups A,B,C,D, respectively.

If $a_ij=m$ for example, it means that team $A_m$ will play event $i$ in round $j$. Now suppose that arrays $(a_{ij}),(b_{ij})$ are orthogonal, that is if $$a_{ij}=a_{mn}=x$$ and $$b_{ij}=b_{mn}=y$$ then $$x=y.$$ Then $A_x$ meets team $B_y$ at most once, and since $A_x$ must meets $9$ different teams, it meets team $B_y$ exactly once.

We see that the conditions can be fulfilled if and only if there exist $4$ pairwise orthogonal Latin squares. Since $9=3^2$ is a prime power, it is known that there exist $8$ pairwise orthogonal Latin squares, and the answer is "yes."

The construction is described here.

EDIT

On reflection, I think I should have included a specific construction. Here is a set of $8$ mutually orthogonal $9\times9$ Latin squares, the maximum possible.

$$\begin{array}{|c|c c c|c c c|c c c|}\hline&1&2&3&4&5&6&7&8&9\\ \hline 1 &11111111&56489723&98765432&69358247&72634859&24973568&85296374&37542986&43827695\\ 2 &22222222&64597831&79846513&47169358&83415967&35781649&96374185&18653794&51938476\\ 3 &33333333&45678912&87954621&58247169&91526748&16892457&74185296&29461875&62719584\\ \hline4 &44444444&89723156&32198765&93682571&15967283&57316892&28539617&61875329&76251938\\ 5 &55555555&97831264&13279846&71493682&26748391&68124973&39617428&42986137&84362719\\ 6 &66666666&78912345&21387954&82571493&34859172&49235781&17428539&53794218&95143827\\ \hline7 &77777777&23156489&65432198&36925814&48391526&81649235&52863941&94218653&19584362\\ 8 &88888888&31264597&46513279&14736925&59172634&92457316&63941752&75329461&27695143\\ 9 &99999999&12345678&54621387&25814736&67283415&73568124&41752863&86137542&38476251\\ \hline\end{array}$$

The rows represent rounds, and the columns represent events. The table is for $8$ houses, say $A,B,C,D,E,F,G,H.$ The sequence indicates which teams from each house will compete in a particular event in a given round. For example, at row $3$, column $4$ we find $58247169$. The interpretation of this is that in round $3$, the teams that compete in event $4$ are $$A_5,B_8,C_2,D_4,E_7,F_1,G_6,\text{ and }H_9$$

In the instant case, where there are only $4$ houses, the last $4$ digits or each table entry can simply be ignored.

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