Problema del golfista social - Quintetos

Question

Escribí un artículo sobre el Problema del Golfista Social, que plantea preguntas como:

Cada día, 16 personas juegan Munchkin en grupos de cuatro simultáneamente. ¿Cuántos días pueden jugar sin que dos personas jueguen juntas más de una vez? torneo

Recopilé las mejores soluciones conocidas para parejas, tríos y cuartetos en la Demostración del Problema del Golfista Social. Para recopilar estos datos, tuve que leer cientos de libros y artículos. A menudo, una respuesta se daba en una notación difícil para mí, o hacía referencia a un artículo previo, o simplemente era "obvia".

Ahora que soy considerado un "experto", me han preguntado sobre quintetos y sextetos, y para un mayor número de grupos. No recuerdo haber visto soluciones para ninguno de los problemas a continuación en los artículos que examiné, pero es posible que las haya pasado por alto.

• 30 juegan en grupos de 3 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 33 juegan en grupos de 3 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 36 juegan en grupos de 3 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 40 juegan en grupos de 4 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 44 juegan en grupos de 4 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 48 juegan en grupos de 4 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 52 juegan en grupos de 4 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 25 juegan en grupos de 5 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 30 juegan en grupos de 5 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 35 juegan en grupos de 5 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 40 juegan en grupos de 5 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 45 juegan en grupos de 5 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 50 juegan en grupos de 5 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 55 juegan en grupos de 5 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 60 juegan en grupos de 5 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 36 juegan en grupos de 6 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 42 juegan en grupos de 6 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 48 juegan en grupos de 6 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 54 juegan en grupos de 6 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 60 juegan en grupos de 6 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 66 juegan en grupos de 6 cada día. Nadie juega junto más de una vez. ¿Cuántos días?
• 72 juegan en grupos de 6 cada día. Nadie juega junto más de una vez. ¿Cuántos días?

¿Alguien tiene soluciones para alguno de estos?

Answer 1

¿Has visto a Ivan Dotu y Pascal Van Hentenryck, Programando golfistas sociales localmente? Ellos afirman

que 45 golfistas en grupos de 5 pueden jugar 7 días;

que 54 golfistas en grupos de 6 pueden jugar 6 días;

que 50 golfistas en grupos de 5 pueden jugar 8 días;

y algunos otros resultados que van más allá de los límites de tu pregunta. Pero en realidad no presentan ninguna instancia de las soluciones, solo su algoritmo y el tiempo que les tomó encontrar las instancias.

Answer 2

No tengo muchos consejos específicos sobre quintetos, pero tal vez la información a continuación sea útil de todas formas.

Algunas de las soluciones que estás buscando corresponden a las condiciones necesarias para diseños de bloques incompletos balanceados resolubles y, si existe un RBIBD, entonces esto llevará inmediatamente a una solución con el número máximo de días. Los elementos en esta categoría son:

• 33 juegan en grupos de 3 durante 16 días - el estudiado Sistema Triple de Kirkman
• 40 juegan en grupos de 4 durante 13 días - ver Kageyama (1972)
• 52 juegan en grupos de 4 durante 17 días - ver Lam & Miao (1999) Lema 5.3
• 25 juegan en grupos de 5 durante 6 días - ver comentario arriba
• 45 juegan en grupos de 5 durante <=11 días - RBIBD es un problema abierto
• 36 juegan en grupos de 6 durante <7 días - RBIBD no existe
• 66 juegan en grupos de 6 durante <=13 días - RBIBD es un problema abierto

Además de lo anterior, puedo ofrecer ejemplos de lo siguiente:

• 30 juegan en grupos de 3 durante 14 días [máximo]
• 36 juegan en grupos de 3 durante 17 días [máximo]
• 44 juegan en grupos de 4 durante 13 días
• 48 juegan en grupos de 4 durante 14 días [ver Ge y Lam (2003) Lema 3.1]
• 45 juegan en grupos de 5 durante 9 días.

También he estado confundido por la extensa literatura sobre este tema. Siento que 44/4/14 días, y 48/4/15 días deberían ser ambos posibles, pero aún no he encontrado una construcción.

Referencias:

Ge & Lam (2003) "Diseños resolubles dividibles en grupo con tamaño de bloque cuatro y tamaño de grupo seis"; Matemáticas discretas, 268, 139 - 151.

Kageyama (1972) "Una encuesta de soluciones resolubles de diseños de bloques incompletos balanceados"; Rev. Inst. Internat. Statist., 40, 269–273.

Lam & Miao (1999) "Sobre Diseños de Steiner Cíclicamente Resolubles Ciclos de 2"; Journal of Combinatorial Theory, Series A 85, 194-207.

Answer 3

Se estudia el Problema del Golfista Social con triples y un número impar de grupos utilizando Sistemas Triples de Kirkman. Esta página afirma que $6n+3$ golfistas jugando en tripletes pueden jugar durante $3n+1$ días (para todo $n$ no negativo). Esto está demostrado en el siguiente artículo (aunque no lo he comprobado yo mismo).

• Solución del problema de las escolares de Kirkman, Ray-Chaudhuri y Wilson, 1971. En Proc. of Symp. in Pure Math, Vol 19.

EDIT:

Hice más investigaciones. Si $6n \ge 18$ jugadores están jugando en tripletes, pueden jugar durante $3n-1$ días. Esto se deriva del estudio de Sistemas Triples de Kirkman Casi. La prueba está repartida en varios artículos, el siguiente artículo los cita:

• Sistemas Triples de Kirkman Casi de orden 18 y sistemas triples de Hanani de orden 19, Charles J.Colbourn et al. Discrete Mathematics 2011 311:827-834.

Además, si $12n+4$ jugadores juegan en grupos de 4, pueden jugar durante $4n+1$ días. Esto está demostrado en

• Sobre diseños resolubles, Haim Hanani, D.K. Ray-Chaudhuri, Richard M. Wilson Discrete Mathematics, 1972, 3:343-357.

Además, Existencia Asintótica de Sistemas Kirkman Casi, Hao Chen, Wen-Song Chu hace las siguientes afirmaciones (citando otros artículos para las dos primeras afirmaciones y probando la tercera)

• Si $12n\ge24$ jugadores juegan en grupos de 4, pueden jugar durante $4n-1$ días, excepto posiblemente para $12n\in\{84, 132, 264, 372, 456, 552, 660, 804, 852\}$.
• Para un tamaño de grupo fijo $k$ para todos menos finitos $n \equiv k \mod k(k-1)$ tenemos que $n$ golfistas pueden jugar el número óptimo de días $\frac{n-1}{k-1}$.
• Para un tamaño de grupo fijo $k$ para todos menos finitos $n \equiv 0 \mod k(k-1)$ tenemos que $n$ golfistas pueden jugar el número óptimo de días $\frac{n}{k-1}-1$.

Esto responde a las siguientes preguntas:

• 30 juegan en grupos de 3 durante 14 días.
• 33 juegan en grupos de 3 durante 16 días.
• 36 juegan en grupos de 3 durante 17 días.
• 40 juegan en grupos de 4 durante 13 días.
• 48 juegan en grupos de 4 durante 15 días.
• 52 juegan en grupos de 4 durante 17 días.

Answer 4

Un nuevo documento (Dic 2020) sobre este tema utiliza la simetría para abordar el problema, y publica soluciones para grupos de hasta 50 participantes: Programación de asignación de grupos de Breakout y el Problema del Golfista Social con tamaños de grupo adyacentes