El dilema de la programación óptima (Un problema matemático de libro de texto IRL)?

Question

Estoy tratando de resolver un problema de programación para un campamento de niños.

Tengo 12 equipos (de la A a la L), 6 deportes para que jueguen, y 6 periodos para que jueguen (de P1 a P6).

                 P1-P2-P3-P4-P5-P6
Soccer          |AB|KJ|IF|GB|EJ|CF|
Football        |CD|AL|KH|ID|GL|EH|
Kick-ball       |EF|CB|AJ|KF|IB|GJ|
Volley Ball     |GH|ED|CL|AH|KD|IL|
Hockey          |IJ|GF|EB|CJ|AF|KB|
Water Polo      |KL|IH|GD|EL|CH|AD|

Así es como se clasifican los horarios:

1: Los equipos sólo pueden jugar un partido por periodo.

2: Se otorgan dos puntos por cada deporte diferente que practique un equipo

3: Se resta un punto cada vez que se repite un enfrentamiento entre equipos (por ejemplo, el equipo C juega dos veces contra el equipo F)

Con este sistema, un calendario perfecto (en el que todos los equipos jugasen todos los deportes y nunca compitiesen dos veces contra el mismo equipo) tendría una puntuación de 144.

Answer 1

                 P1-P2-P3-P4-P5-P6
Soccer          |AG|BH|CI|DL|EK|FJ|
Football        |BC|JG|DE|HI|FA|LK|
Kick-ball       |KJ|CD|GH|EF|IL|AB|
Volley Ball     |EL|FK|AJ|BG|CH|DI|
Hockey          |FI|AL|BK|CJ|DG|EH|
Water Polo      |DH|EI|FL|AK|BJ|CG|

@Vince Kroon es incorrecto. Aquí, he reformateado su horario usando la información de esta respuesta mencionado por @Kevin Costello.

@Vince Kroon tenía razón al decir que este problema es irresoluble para $n = 2$ pero es, sin embargo, solucionable para cualquier n donde $n>2$ .

Answer 2

Conseguir una puntuación perfecta (todos los equipos jugando todos los deportes sin repeticiones en los enfrentamientos) no es posible con los parámetros que tienes.

Tl;dr Estás rellenando una cuadrícula de tamaño $(n/2)^2.$ pero cada equipo sólo tiene $n-1$ posibles competidores, ya que los equipos no pueden jugar ellos mismos. Se podría resolver este problema eliminando uno de los periodos, añadiendo un deporte extra, creando un equipo adicional o dividiendo a los campistas en un número par de equipos.

Para demostrarlo, imaginemos que sólo hay 4 equipos (de la A a la D), 2 periodos y 2 deportes. Empieza a rellenar el gráfico.

  1   2
1|AB|  |
2|CD|  |

Como puedes ver, he rellenado la primera columna. Desgraciadamente, sólo quedan dos plazas en la fila 2, por lo que A y B deben ir allí si todos los equipos van a jugar todos los deportes.Del mismo modo, C y D deben ir en la fila 1.

Sin embargo, en una cuadrícula de 3 por 3, este problema se puede resolver.

|AB|CE|DF|
|CD|AF|BE|
|EF|BD|AC|

Dado que esta rejilla resuelta es 1/4 de la rejilla que estás intentando resolver, vamos a intentar usarla para que tu rejilla funcione.

|AB|CE|DF|
|CD|AF|BE|
|EF|BD|AC|

|GH|IK|JL|
|IJ|GL|HK|
|KL|HJ|GI|

Arriba he mostrado un segundo tablero resuelto hecho desplazando todas las letras de la primera cuadrícula hacia abajo 6 letras(por ejemplo A=G, B=H...). Esto es la mitad del programa.

Pero ahora, si se intenta rellenar la segunda mitad del horario, se vuelve al problema planteado en el ejemplo de 2 por 2. De la A a la F no pueden utilizarse en las filas 1 a 3, y de la G a la L no pueden utilizarse en las filas 4 a 6. Dicho esto, debemos reorganizar los equipos A a F para que compitan en las filas 4 a 6, y reorganizar los equipos G a L para que compitan en las filas 1 a 3.

|AB|CE|DF| |GK|LH|IJ|
|CD|AF|BE| |IH|GJ|LK|
|EF|BD|AC| |KJ|IL|GH|

|GH|IK|JL| |AE|FB|CD|
|IJ|GL|HK| |CB|AD|FE|
|KL|HJ|GI| |ED|CF|AB|
                   ^
                  Repeated match-ups

Aquí he rellenado la cuadrícula con el número mínimo de repeticiones (6), y he elegido repetir los emparejamientos de las primeras columnas en la última fila para que el máximo de veces entre las repeticiones. Como puedes ver, eliminar el último periodo resolvería el problema por completo, al igual que eliminar alguno de los deportes. Alternativamente, podría dividir a los niños en un número impar de equipos.