0
$\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.

$\endgroup$

closed as unclear what you're asking by JMP, f'', Fabich, Engineer Toast, Marius Jul 31 '16 at 5:53

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Can you explain this a little better? I'm not exactly sure what you mean. $\endgroup$ – FrodCube Jul 30 '16 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$ – Glorfindel Jul 30 '16 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 Earnest Jul 30 '16 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$ – user27275 Jul 30 '16 at 21:51
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Awesome, nice insight, and thanks for humoring me! $\endgroup$ – Mike Earnest Jul 30 '16 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$ – Glorfindel Jul 30 '16 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$ – Mike Earnest Jul 30 '16 at 18:23
1
$\begingroup$

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
$\endgroup$

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