¿Pueden 12 equipos de 6 disciplinas jugar 6 rondas sin repetirse?

Question

Considere el siguiente torneo:

Hay 12 equipos, 6 disciplinas y 6 rondas, cada ronda y cada evento ocurren simultáneamente. ¿Es posible crear un torneo de manera que ningún equipo haga la misma disciplina dos veces ni se enfrente a un equipo con el que ya haya jugado? No hay recompensa para los equipos ganadores que se encuentran con equipos ganadores.

Este es un problema real que me molesta bastante. Parece imposible (sobre todo debido a la prueba y error y a algunos intentos de aplicar las matemáticas) pero no puedo probarlo. Dado que no se puede resolver me gustaría, por supuesto, ver el argumento. No sé si existe esa matemática, pero también sería interesante algún tipo de torneo formalizado como el mejor.

Editar: Un ejemplo podría ser (suponiendo que los equipos del 1 al 12 están simplemente numerados)

Ronda 1: Fútbol 1 vs 2, Béisbol 3 vs 4, Baloncesto 5 vs 6, Hockey 7 vs 8, Ultimate 9 vs 10, Fútbol 11 vs 12

Ronda 2: Fútbol 3 contra 6, Béisbol 5 contra 8, Baloncesto 7 contra 10, Hockey 9 contra 12, Ultimate 11 contra 2, Fútbol 1 contra 4 y así sucesivamente.

Así que las disciplinas deben ser preferiblemente simultáneas. Perdón por no haberlo escrito explícitamente la primera vez.

Answer 1

He encontrado una solución publicado por Ian Wakeling en el tablón de anuncios de un torneo Round Robin en 2008.

He comprobado un poco a ojo y luego lo he formateado como hechos Prolog para hacer una comprobación informática:

/*
    Search for 12 team tournament with 6 rounds and 6 venues
    s.t. each team plays once in each round (against one opponent)
    and each venue is used once in each round.
*/

teams([a,b,c,d,e,f,g,h,i,j,k,l]).
rounds([1,2,3,4,5,6]).
venues([1,2,3,4,5,6]).

p(a,g,1,1). p(b,h,1,2). p(c,i,1,3). p(d,l,1,4). p(e,k,1,5). p(f,j,1,6). 
p(b,c,2,1). p(j,g,2,2). p(d,e,2,3). p(h,i,2,4). p(f,a,2,5). p(l,k,2,6). 
p(k,j,3,1). p(c,d,3,2). p(g,h,3,3). p(e,f,3,4). p(i,l,3,5). p(a,b,3,6). 
p(e,l,4,1). p(f,k,4,2). p(a,j,4,3). p(b,g,4,4). p(c,h,4,5). p(d,i,4,6). 
p(f,i,5,1). p(a,l,5,2). p(b,k,5,3). p(c,j,5,4). p(d,g,5,5). p(e,h,5,6). 
p(d,h,6,1). p(e,i,6,2). p(f,l,6,3). p(a,k,6,4). p(b,j,6,5). p(c,g,6,6). 

Como es preceptivo, cada equipo juega una vez en cada ronda y una vez en cada sede, y cada equipo tiene seis rivales distintos. Naturalmente, los papeles de Ronda y Sede ("disciplina") son intercambiables.

Como se observa en el post de la BB enlazado, dicho programa es un Diseño de Howell $H(n,2n)$ para $n=6$ . También puede identificarse como un SOMA $(2,n)$ , acrónimo de "simple orthogonal multi-arrays", según la historia relatada en esta disertación de 2006 de John Arhin . La similitud con los cuadrados latinos mutuamente ortogonales no es casualidad, ya que los MOLS son útiles para construir SOMA.

De hecho, la existencia de $H(n,2n)$ diseños para todos $n > 2$ se establece mediante el ejemplo anterior junto con la construcción de tales diseños mediante la combinación (superposición) de dos cuadrados latinos mutuamente ortogonales (MOLS) de tamaño $n\times n$ con conjuntos de símbolos disjuntos (por lo que los pares de símbolos de $2n$ posibilidades). Esta es una observación de Hung y Mendelsohn (1974), Sobre los diseños de Howell utilizando el hecho de que los pares MOLS existen para todos los $n \neq 2,6$ . Como comentó Neil en la Pregunta, no hay $H(2,4)$ pero el ejemplo aquí lo demuestra, $H(6,12)$ existen a pesar de la inexistencia de un par de MOLS de orden $n=6$ .

Answer 2

Suponiendo que en una ronda los doce equipos se separen en seis parejas, entonces es posible.

Una vía es simplemente hacer que cada pareja juegue la misma disciplina en la misma ronda, con una disciplina diferente en juego cada ronda. Luego se rotan los emparejamientos de los equipos, de modo que cada equipo se empareja con una pareja diferente.

$$\begin{array}{ccccccccccc} 1 & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 4 & \rightarrow & 5 & \rightarrow & 6 \\ \uparrow &&&&&&&&&&\downarrow \\ 12 & \leftarrow & 11 & \leftarrow & 10 & \leftarrow & 9 & \leftarrow & 8 & \leftarrow & 7 \end{array}$$