Problema de las colegialas de Kirkman
El problema dice: Quince alumnas salen formadas de tres en fondo durante siete días seguidos: se requiere formarlas cada día de manera que al terminar la semana no haya habido dos de ellas que hayan caminado juntas (o sea, en la misma fila) más de una vez.
Los sistemas de Steiner que poseen un paralelismo también se denominan resolubles.
Hay exactamente siete soluciones no isomorfas para el problema de las alumnas, como las enumeró originalmente Frank Nelson Cole en su artículo titulado Kirkman Parades de 1922.
Esta sección se basa en el trabajo recopilatorio realizado en diferentes momentos por Robin Wilson[4] y por Louise Duffield Cummings.
[5] Su cronología es la siguiente: James Joseph Sylvester en 1850 preguntó si se podrían construir 13 sistemas de Kirkman separados formados por 35 tripletas cada uno para utilizar todas las chicas
No se encontró ninguna solución hasta 1974, cuando RHF Denniston resolvió la cuestión con una computadora en la Universidad de Leicester.
Eligió una permutación con un solo ciclo de 13 y dos puntos fijos como (1 2 3 4 5 6 7 8 9 10 11 12 13)(14)(15).
Bajo esta permutación, un triplete como 123 se asignaría a 234, 345,... (11, 12, 13), (12, 13, 1) y (13, 1, 2) antes de repetirse.
Luego programó una computadora Elliott 4130 para que hiciera exactamente esa búsqueda, lo que le llevó 7 horas encontrar esta solución para la primera semana.
[16] El compositor minimalista estadounidense Tom Johnson compuso una pieza musical titulada "Kirkman's Ladies" basada en la solución de Denniston.
[17][18] En 2021, seguía sin saberse si existen otras soluciones no isomorfas al problema de Sylvester o cuántas soluciones hay.
La solución conocida por Bays (1917) fue encontrada nuevamente desde una dirección diferente por Earl Kramer y Dale Mesner en un estudio de 1974, el artículo titulado Intersecciones entre sistemas de Steiner (J Combinatorial Theory, Vol 16, págs.
La solución 1 tiene 42 automorfismos, generados por las permutaciones (A I D C F H)(B G) y (C F D H E I)(B G).
La solución 2 tiene 54 automorfismos, generados por las permutaciones (A B D)(C H E)(F G I) y (A I F D E H)(B G).
Por lo tanto, hay 8640 + 6720 = 15360 soluciones en total, que se dividen en dos categorías no isomorfas.
Todos estos conjuntos de 2 o 5 son respectivamente isomorfos entre sí.
[20] En 1910, George Conwell abordó el problema utilizando la geometría de Galois.
Un plano puede considerarse como un cuadrángulo completo junto con la recta que pasa por sus puntos diagonales.
Estos 35 puntos forman la superficie S conocida como cuádrica de Klein.
[21]: 69 El problema de las colegialas consiste en encontrar siete rectas en el 5-espacio que no se crucen y que dos rectas cualesquiera siempre tengan una héptada en común.
[21]: 74 En PG(3,2), una partición de puntos en rectas se llama una extensión (spread en inglés), y una partición de rectas en extensiones se llama empaquetado o paralelismo.
[24] D. K. Ray-Chaudhuri y R. M. Wilson publicaron una solución completa al caso general en 1968,[15] aunque ya había sido resuelta por Lu Jiaxi (陆家羲) en 1965,[13] pero no se había publicado en ese momento.
[14] Se pueden considerar muchas variaciones del problema básico.
[25] Más recientemente, ha ganado interés un problema similar conocido como problema social del golfista, que trata con 32 golfistas que quieren jugar con diferentes personas cada día en grupos de 4, en el transcurso de 10 días.
grupos donde cada par de niñas debe estar en el mismo grupo en algún momento, pero se quiere usar la menor cantidad de días posible.
Esto se puede utilizar, por ejemplo, para programar un plan de mesa rotativa, en el que cada pareja de invitados debe estar en algún momento en la misma mesa.
