Mi grupo de golf tiene 12 miembros jugando 4 rondas. ¿Cómo se pueden organizar los foursomes para maximizar la mezcla? Como mínimo, ¿puede cada miembro jugar al menos una ronda con cualquier otro miembro? Si no, ¿qué es lo más cerca que podemos hacer?

Creo que el recocido simulado es una buena manera de resolver este problema, pero haré los cálculos de todos modos.

Hay 66 pares de golfistas, y un total de 6 * 3 * 4 = 72 pares que podemos programar. Nuestro objetivo es minimizar los pares duplicados (en el cronograma de Anders hay 13 duplicados en total).

Suponga que la primera ronda es ABCD | EFGH | IJKL.

Para la segunda ronda, debe haber al menos un duplicado en cada grupo (porque para 4 personas, 2 deben haber jugado juntas en la primera ronda).

En la tercera ronda, nuevamente tenemos al menos un duplicado en cada cuarteto (debido a la superposición con la ronda 1). Pero obtenemos 3 más aplicando la misma lógica a la superposición con la ronda 2. ¿Podemos hacer algo mejor que 6 duplicados en la ronda 3 (y 9 en la ronda 4, para un total de 18)? Sí, obligando a los múltiples duplicados en cada cuarteto a coincidir.

Dado lo anterior, naturalmente querrás que ciertos 3 pares jueguen juntos en las 4 rondas. Esto llevaría a 9 duplicados totales. Desafortunadamente, este tipo de restricción fuerza duplicados adicionales en otros lugares, como veremos más adelante.

Supongamos que la función f (k, l) representa “la menor cantidad de duplicados alcanzables con k pares que juegan 3 veces y l pares que juegan 4 veces”. Entonces f (2,1)> = 13 por la siguiente lógica. La ronda 2 tiene 3 duplicados con la ronda 1, la ronda 3 tiene los mismos 3 duplicados que las rondas 2 y 1, y la ronda 4 tiene un cuarteto con solo un duplicado y dos cuartetos con 3 nuevos duplicados cada uno. El ejemplo de Anders cumple este límite.

f (3,1) no es mejor ya que solo obtenemos el “beneficio de duplicados coincidentes” para k + l <= 3. Realmente solo necesitamos demostrar que f (1,2)> = 13. Como el beneficio de un duplicado coincidente adicional es -1, forzar cualquier otra duplicación mostrará el límite. Vamos a intentarlo:
¿¿Automóvil club británico?? ¿¿Cama y desayuno?? Cc ??
¿¿Automóvil club británico?? ¿¿Cama y desayuno?? Cc ??
¿¿Automóvil club británico?? ¿¿Cama y desayuno?? Cc ??
¿¿Automóvil club británico?? ¿¿Cama y desayuno?? ????

Podemos asignar las 3 primeras rondas con avidez, ya que cualquier asignación a la ronda 1 implica las otras dos:
AaXx BbYy CcZz
AaYz BbZx CcXy
AaZy BbXz CcYx
¿¿Automóvil club británico?? ¿¿Cama y desayuno?? ????

En la ronda 4, se supone que los primeros dos foursomes no tienen duplicados adicionales. Pero deben hacerlo: Aa solo no ha jugado con BbCc y Bb solo no ha jugado con AaCc. Como Aa y Bb ya se usan en esta ronda, debe haber dos duplicados adicionales que salgan de los primeros dos foursomes. Entonces f (1,2)> = 14.

Por lo tanto, la solución de Anders es óptima. Por cierto, f (0,0) es, supongo, 18, es decir, se reconocen 5 pares menos, pero ninguno se triplica. John Sommer ha encontrado una solución de esta forma.

Todavía no tengo un método riguroso para determinar el mejor equipo, pero he creado una hoja de cálculo Googl Doc con un conjunto propuesto de miembros del equipo y algunos cálculos para evaluar la mezcla de compañeros de equipo para que pueda ver qué tan bien le está yendo con la creación de equipos. para cada ronda para minimizar la cantidad de veces que los jugadores juegan en los mismos equipos.

El ejemplo en la hoja de cálculo tiene 36 combinaciones de un miembro jugando solo una vez con otro miembro y 18 donde juegan con el mismo miembro del equipo dos veces. Ninguno en este ejemplo tiene un miembro del equipo jugando con otro más de dos veces.

Esta es la combinación que tengo hasta ahora:
ABCD EFGH IJKL
ADEI BFGK CHJL
BCHI AEGJ DFKL
CDGK BEHL AFIJ

En la hoja de cálculo puede cambiar los equipos y ver los nuevos resultados de la mezcla.

Use este enlace y descargue o copie en su propio Google Doc para experimentar.
https://spreadsheets.google.com/ …

Encuentre en: http://www.mathpages.com/home/km… (gracias a google)

“Suponga que está planeando un torneo de golf en el que 12 jugadores jugarán una ronda por día durante 4 días. Debe decidir cómo dividir a los 12 jugadores en 3 cuartetos cada día, y desea elegir los cuatro para minimizar la cantidad de parejas repetidas. Idealmente, le gustaría tener cada pareja de jugadores juntas en el mismo cuarteto solo una vez, pero eso obviamente no es posible con las condiciones de este problema, por lo que el objetivo es minimizar las parejas repetidas Y hacer el calendario lo más simétrico posible para los 12 jugadores ¿Cuál es la “mejor” solución (la más distribuida equitativamente)?

En este caso, no es obvio, a priori, cómo caracterizar con precisión la “mejor” solución, ya que minimizar el número de pares repetidos no necesariamente da una solución simétrica. Un enfoque es pensar en un poliedro bastante simétrico con propiedades adecuadas. El dodecaedro rómbico viene a la mente, porque tiene 12 caras, cada una de las cuales tiene 4 vecinos, y hay 3 pares duales de particiones mutuamente excluyentes de las 12 caras en tres conjuntos de cuatro. Aquí está la gráfica de este sólido Los únicos pares de caras cuyos conjuntos de vecinos son mutuamente excluyentes son [(1,10), (2,8)], [(3,6), (4,7)], [(5,11), (9 , 12)]. El mayor número de caras que son mutuamente no vecinas es cuatro, y cada cara es miembro de exactamente tres de estos conjuntos. Esto da las particiones

1 2 8 10/1 2 9 11/1 3 7 8
3 4 5 9/3 4 6 7/2 4 6 10
6 7 11 12/5 8 10 12/5 5 11 12

Para dar una cuarta partición, observe que “1” y “10” ya están emparejados dos veces con “2” y dos veces con “8”, y estos son los conjuntos duales de caras opuestas [(1,10), (2, 8)]. Además, las caras opuestas “1” y “10” ya están emparejadas una vez entre sí. Existen emparejamientos similares para los otros dos conjuntos duales. Esto sugiere que creamos tres nuevos foursomes combinando pares no duales. Hay ocho formas distintas de hacer esto. Por ejemplo, si combinamos (1,10) con (4,7), y combinamos (2,8) con (9,12), y así sucesivamente, tenemos
1 4 7 10/2 8 9 12/3 5 6 11

Usando esta partición para la cuarta ronda, el horario de cada jugador incluye cuatro “dobles” y cuatro “individuales”. No hay dos personas en el mismo cuarteto más de dos veces, y cada persona juega (al menos una vez) con exactamente 8 (de los 11) otros jugadores. ¿Es esto lo mejor que se puede hacer? ”

Esto te da, con LETRAS y reordenando:
ABCD EFGH IJKL
ABHK EFIJ GCDL
AEJC BFID GHKL
AFJD BCHL EGIK