So I have to arrange a rotation schedule for a tournament. We're aiming for 32 teams. There will be 8 stations and 4 teams competing simultaneously at each station. We want all 32 teams to hit each station once, but not play the same teams twice. I was hoping to set up a template so if the teams go up or down it will be an easy fix.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Can you explain this a little better? I'm not exactly sure what you mean. $\endgroup$– FrodCubeJul 30, 2016 at 17:06
-
2$\begingroup$ With no other restrictions, it is quite simple, you can just rotate them if you place all stations in a circle. You probably mean that two teams never face each other twice. Then, it is 'simply' a task of constructing 4 mutually orthogonal 8x8 Latin squares - which is possible, because 7 is the maximum according to OEIS. $\endgroup$– GlorfindelJul 30, 2016 at 17:22
-
1$\begingroup$ @Glorfindel Can you elaborate on how that would work in an answer? Here is a pastebin with 4 MOLS of order 8. $\endgroup$– Mike EarnestJul 30, 2016 at 17:49
-
1$\begingroup$ So I have to arrange a rotation schedule for a tournament. We're aiming for 32 teams. There will be 8 stations and 4 teams competing simultaneously at each station. We want all 32 teams to hit each station once but not play the same teams twice. I was hoping to set up a template so if the teams go up or down it will be an easy fix. This is for the person that needed more detail. Hopefully, this helps $\endgroup$– user27275Jul 30, 2016 at 21:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
Assuming that two teams may never face each other twice (otherwise, it is trivial), here is a solution. Thanks to @MikeEarnest for providing me with the necessary mutually orthogonal Latin squares. Let S1, S2 ... S8 denote the stations, and R1, R2 ... R8 denote the rounds. For convenience, we number the teams A, B, C, D plus a number from 1 to 8. The following configuration would work:
S1 S2 S3 S4 S5 S6 S7 S8
R1 A7 A6 A5 A4 A3 A2 A1 A8
R2 A6 A7 A4 A5 A2 A3 A8 A1
R3 A5 A4 A7 A6 A1 A8 A3 A2
R4 A4 A5 A6 A7 A8 A1 A2 A3
R5 A3 A2 A1 A8 A7 A6 A5 A4
R6 A2 A3 A8 A1 A6 A7 A4 A5
R7 A1 A8 A3 A2 A5 A4 A7 A6
R8 A8 A1 A2 A3 A4 A5 A6 A7
R1 B7 B5 B3 B1 B4 B6 B8 B2
R2 B6 B4 B2 B8 B5 B7 B1 B3
R3 B5 B7 B1 B3 B6 B4 B2 B8
R4 B4 B6 B8 B2 B7 B5 B3 B1
R5 B3 B1 B7 B5 B8 B2 B4 B6
R6 B2 B8 B6 B4 B1 B3 B5 B7
R7 B1 B3 B5 B7 B2 B8 B6 B4
R8 B8 B2 B4 B6 B3 B1 B7 B5
R1 C7 C4 C1 C2 C8 C3 C6 C5
R2 C6 C5 C8 C3 C1 C2 C7 C4
R3 C5 C6 C3 C8 C2 C1 C4 C7
R4 C4 C7 C2 C1 C3 C8 C5 C6
R5 C3 C8 C5 C6 C4 C7 C2 C1
R6 C2 C1 C4 C7 C5 C6 C3 C8
R7 C1 C2 C7 C4 C6 C5 C8 C3
R8 C8 C3 C6 C5 C7 C4 C1 C2
R1 D7 D3 D4 D8 D1 D5 D2 D6
R2 D6 D2 D5 D1 D8 D4 D3 D7
R3 D5 D1 D6 D2 D3 D7 D8 D4
R4 D4 D8 D7 D3 D2 D6 D1 D5
R5 D3 D7 D8 D4 D5 D1 D6 D2
R6 D2 D6 D1 D5 D4 D8 D7 D3
R7 D1 D5 D2 D6 D7 D3 D4 D8
R8 D8 D4 D3 D7 D6 D2 D5 D1
Because every square is a Latin square, each team will visit each station during all the rounds. Each round, you have one A-team (pun intended) and one team from B, C and D on one station. Because they're mutually orthogonal, teams will never face each other in two different rounds. One of the most striking results of this field of combinatorics is that a slightly different configuration, with 12 teams and 6 stations cannot be solved. This is Euler's Thirty-six officers problem.
answered Jul 30, 2016 at 18:02
-
$\begingroup$ Awesome, nice insight, and thanks for humoring me! $\endgroup$ Jul 30, 2016 at 18:14
-
$\begingroup$ You're welcome. Somehow I didn't like this part of the Discrete Mathematics course I took. Or maybe I just liked the other parts better. $\endgroup$ Jul 30, 2016 at 18:16
-
$\begingroup$ Yes, combinatorial design feels pretty clunky, it isn't fun to learn about IMO. But it's very cool seeing it used to solve real world problems $\endgroup$ Jul 30, 2016 at 18:23
$\begingroup$
$\endgroup$
Here is an easier to read (but far less insightful) presentation of Glorinfidel's answer. The teams are numbered 1-32. Every row is a list of matches which can happen concurrently.
Station 1 Station 2 Station 3 Station 4 Station 5 Station 6 Station 7 Station 8 1, 9,17,25 │ 2,11,20,29 │ 3,13,23,28 │ 4,15,22,32 │ 5,12,24,31 │ 6,10,21,27 │ 7,16,18,30 │ 8,14,19,26 2,10,18,26 │ 1,12,19,30 │ 4,14,24,27 │ 3,16,21,31 │ 6,11,23,32 │ 5, 9,22,28 │ 8,15,17,29 │ 7,13,20,25 3,11,19,27 │ 4, 9,18,31 │ 1,15,21,26 │ 2,13,24,30 │ 7,10,22,29 │ 8,12,23,25 │ 5,14,20,32 │ 6,16,17,28 4,12,20,28 │ 3,10,17,32 │ 2,16,22,25 │ 1,14,23,29 │ 8, 9,21,30 │ 7,11,24,26 │ 6,13,19,31 │ 5,15,18,27 5,13,21,29 │ 6,15,24,25 │ 7, 9,19,32 │ 8,11,18,28 │ 1,16,20,27 │ 2,14,17,31 │ 3,12,22,26 │ 4,10,23,30 6,14,22,30 │ 5,16,23,26 │ 8,10,20,31 │ 7,12,17,27 │ 2,15,19,28 │ 1,13,18,32 │ 4,11,21,25 │ 3, 9,24,29 7,15,23,31 │ 8,13,22,27 │ 5,11,17,30 │ 6, 9,20,26 │ 3,14,18,25 │ 4,16,19,29 │ 1,10,24,28 │ 2,12,21,32 8,16,24,32 │ 7,14,21,28 │ 6,12,18,29 │ 5,10,19,25 │ 4,13,17,26 │ 3,15,20,30 │ 2, 9,23,27 │ 1,11,22,31
answered Jul 30, 2016 at 19:01