thumb|right|300px|Publicación original del problema
El problema de las colegialas de Kirkman es una cuestión matemática de carácter combinatorio propuesta por Thomas Kirkman en 1850 en la publicación "The Lady's and Gentleman's Diary" (El Diario de Damas y Caballeros) (Consulta VI; página 48). 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.
Soluciones Una solución a este problema es un ejemplo de un sistema triple de Kirkman, que se define como un sistema triple de Steiner que posee un paralelismo, es decir, una partición de los bloques del sistema triple en clases paralelas que son a su vez particiones de los puntos en bloques disjuntos. 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. Las siete soluciones se resumen en la siguiente tabla, en la que se representan a las 15 niñas mediante las letras de la A a la O:
Clase de soluciónGrupo de automorfismoDía 1Día 2Día 3Día 4Día 5Día 6Día 7Solución IOrden 168, generado por(A K G E I L B)(C H M J N O D)y(A M L K O C D)(B H N G I E J).Relacionado con PG(3,2).ABCDEFGHIJKLMNOADGBEHCJMFKNILOAEOBIJCDNFHLGKMAIMBDLCEKFGOHJNAFJBKOCGLDHMEINAHKBGNCFIDJOELMALNBFMCHODIKEGJSolución IIOrden 168, generado por(A B I M F C J)(D N H K O L E)y(A J M I B F C)(D H G N K E O).Relacionado con PG(3,2).ABCDEFGHIJKLMNOADGBEHCJMFKNILOAEOBIJCDNFHLGKMAFJBGNCHODIKELMAHKBFMCGLDJOEINAIMBDLCEKFGOHJNALNBKOCFIDHMEGJSolución IIIOrden 24, generado por(A H E)(B O K)(C F I)(D J L)(G N M)y(A J B M)(D L E O)(F I)(G K H N)ABCDEFGHIJKLMNOADGBEHCJMFKNILOAEOBIMCDKFGLHJNAFMBGNCHLDJOEIKAHKBFJCGODINELMAIJBDLCENFHOGKMALNBKOCFIDHMEGJSolución IVOrden 24, generado por(A J M)(C F I)(D E K)(H O L)y(A L B O)(C I)(D K E N)(G J H M)ABCDEFGHIJKLMNOADGBEHCJMFKNILOAEOBIMCDKFGLHJNAFMBKOCHLDINEGJAHKBGNCFIDJOELMAIJBDLCENFHOGKMALNBFJCGODHMEIKSolución VGrupo tetraédrico de orden 12,generado por(A L)(B G)(E O)(F J)(H K)(I M)y(A B C)(D L G)(F J I)(E K H)ABCDEFGHIJKLMNOADGBEJCHMFKNILOAEMBDLCIKFGOHJNAFHBKMCGLDJOEINAIJBGNCEODHKFLMAKOBFICDNEHLGJMALNBHOCFJDIMEGKSolución VIGrupo tetraédrico de orden 12,generado por(A L)(B G)(E O)(H K)(F J)(I M)y(A B C)(D L G)(E K H)(F J I)ABCDEFGHIJKLMNOADGBEJCHMFKNILOAEMBDLCIKFGOHJNAFHBKMCGLDJOEINAIJBHOCDNEGKFLMAKOBGNCFJDIMEHLALNBFICEODHKGJMSolución VIIOrden 21, generado por(A B L C G D N)(E H K I O J F)y(B G L)(C D N)(E F K)(H I O)ABCDEFGHIJKLMNOADGBEJCHMFKNILOAEIBDNCJOFHLGKMAFOBIKCGNDHJELMAHKBFMCDLEGOIJNAJMBGLCFIDKOEHNALNBHOCEKFGJDIM
A partir del número de automorfismos para cada solución y de la definición de grupo de automorfismos, el número total de soluciones incluidas las soluciones isomórficas es, por tanto,:
.
Historia
El problema tiene una larga y prolija historia. Esta sección se basa en el trabajo recopilatorio realizado en diferentes momentos por Robin WilsonThe Early History of Block Designs by Robin Wilson, Dept of Pure Mathematics, The Open University, UK y por Louise Duffield Cummings. Su cronología es la siguiente:
En 1844, Wesley Woolhouse, editor por entonces de The Lady's and Gentleman's Diary, formuló la siguiente pregunta general: "Determinar el número de combinaciones que se pueden hacer con n símbolos, agrupando p símbolos en cada combinación; con la siguiente limitación: que ninguna combinación de q símbolos, que pueden aparecer en cualquiera de ellas, se repetirá en ninguna otra." Solo se recibieron dos respuestas, una incorrecta y la otra respondiendo correctamente la pregunta con . Como no se pidió nada más que el número de combinaciones, no se recibió nada acerca de las condiciones de n, p o q que hacen posible lograr tal solución.
En 1846, Woolhouse preguntó: "¿Cuántas tríadas pueden formarse a partir de n símbolos, de modo que ningún par de símbolos quede comprendido más de una vez entre ellas?". Esto equivale a repetir su pregunta de 1844 con los valores p = 3 y q = 2.
En 1847, a la edad de 41 años, Thomas Kirkman publicó su artículo titulado Sobre un problema de combinaciones, que describía y resolvía exhaustivamente el problema de la construcción de sistemas triples de orden n donde n = 1 o 3 (mod 6). También consideró otros valores de n, aunque no pudo generalizar su planteamiento. Dio dos secuencias diferentes de sistemas triples, una para n = 7, 15, 19, 27, etc., y otra para n = 9, 13, 25, etc. Utilizando estas proposiciones, demostró que existen sistemas triples para "todos" los valores de n = 1 o 3 (mod 6) (no necesariamente resolubles, pero sí sistemas triples en general). También describió en detalle los sistemas triples resolubles en ese artículo, particularmente para n = 9 y 15; Los sistemas triples resolubles ahora se conocen como sistemas triples de Kirkman. No pudo establecer de manera concluyente para qué otros valores de n existirían sistemas triples resolubles, problema que no se resolvería hasta la década de 1960 (véase más abajo).
En 1850, Kirkman planteó el problema de las 15 colegialas, que se volvería mucho más famoso que el artículo de 1847 que ya había escrito. Se recibieron varias soluciones. El propio Kirkman dio una solución que luego se descubriría que era isomorfa a la Solución I anterior. Kirkman afirmó que era la única solución posible, pero esta afirmación era incorrecta. Más adelante se descubrió que la solución de Arthur Cayley era isomorfa a la Solución II. Ambas soluciones podían integrarse en PG(3,2), aunque esa geometría no se conocía en ese momento. Sin embargo, al publicar sus soluciones al problema de las escolares, Kirkman se olvidó de remitir a los lectores a su propio artículo de 1847, y esta omisión tendría graves consecuencias para la invención y la prioridad, como se ve a continuación.
También en 1850, James Joseph Sylvester preguntó si podría haber 13 soluciones diferentes al problema de las 15 alumnas que usasen todas las tripletas posibles una vez en total, observando que . En otras palabras, ¿es posible que las niñas marchen todos los días durante 13 semanas, de modo que cada dos niñas marchen juntas exactamente una vez por semana y cada tres niñas marchen juntas exactamente una vez en el plazo de 13 semanas? Este problema era mucho más difícil y RHF Denniston finalmente proporcionaría una solución utilizando un computador en 1974 (véase más abajo).
En 1852, Robert Richard Anstice proporcionó una solución cíclica, formada mediante la construcción de las cinco tripletas del primer día para que fueran 0Gg, AbC, aDE, cef, BdF en los 15 símbolos 0ABCDEFGabcdefg y luego cambiando cíclicamente cada día subsiguiente por una letra, dejando 0 sin cambios (las mayúsculas permanecen en mayúscula y las minúsculas permanecen en minúscula). Si las cuatro tripletas sin el elemento 0 (AbC, aDE, cef, BdF) se toman y se convierten de mayúsculas a minúsculas (abc, ade, cef, bdf) forman lo que más tarde se llamaría la Configuración de Pasch, que cobraría importancia en las técnicas de eliminación de soluciones isomorfas en el .
En 1853, Jakob Steiner, completamente ignorante del artículo de Kirkman de 1847, publicó su artículo titulado Combinatorische Aufgabe, que reintroducía el concepto de sistemas triples, pero no mencionó la resolubilidad en clases paralelas separadas. Steiner señaló que es necesario que n sea 1 o 3 (mod 6), pero dejó abierta la pregunta de en qué condiciones es posible, sin saber que Kirkman ya había resuelto esa cuestión en 1847. Como este artículo fue más ampliamente leído por el establishment matemático europeo, los sistemas triples se conocieron más tarde como sistemas triples de Steiner.
En 1859, Michel Reiss respondió a las preguntas planteadas por Steiner, utilizando tanto una metodología como una notación tan similar al trabajo de Kirkman de 1847 (sin reconocer a Kirkman), que autores posteriores como Louise Cummings lo han considerado un plagio. El propio Kirkman expresó su amargura.
En 1860, Benjamin Peirce unificó varias soluciones dispares presentadas hasta entonces y demostró que había tres posibles estructuras de solución cíclica, una correspondiente al trabajo de Anstice, otra basada en la solución de Kirkman y otra en la de Cayley.
En 1861, James Joseph Sylvester revisó el problema y trató de afirmar que "él" lo había inventado y que sus conferencias en Cambridge habían sido la fuente del trabajo de Kirkman. Kirkman rápidamente rechazó estas aseveraciones, afirmando que cuando escribió sus artículos nunca había estado en Cambridge ni había oído hablar del trabajo de Sylvester. Esta disputa de prioridad provocó una disputa entre Sylvester y Kirkman.
En 1861-1862, Kirkman sostuvo otra disputa con Arthur Cayley por un asunto distinto (la decisión de Cayley de no publicar una serie de artículos de Kirkman sobre teoría de grupos y poliedros, que le costaron a Kirkman el reconocimiento de la comunidad matemática en Europa), lo que contribuyó aún más a su condición de marginado por el establishment matemático. Su completo artículo de 1847 en particular fue olvidado, y muchos autores posteriores dieron crédito a Steiner o a Reiss, sin conocer la verdadera historia.
La popularidad del problema de las colegialas en sí no se vio afectada por los conflictos académicos de Kirkman, y a finales del y principios del , el rompecabezas apareció en varios libros de matemáticas recreativas de Édouard Lucas, W. W. Rouse Ball, Wilhelm Ahrens, y Henry Dudeney. Durante su vida, Kirkman se quejaría de que su serio trabajo matemático quedó eclipsado por la popularidad del problema de las escolares. Kirkman murió en 1895.
En 1918, Louise Duffield Cummings volvió a llamar la atención sobre el serio trabajo matemático de Kirkman en un artículo titulado "Un artículo de Kirkman infravalorado", que analizaba la historia temprana del problema y corregía la omisión histórica.
Aproximadamente al mismo tiempo, Cummings estaba trabajando con Frank Nelson Cole y Henry Seely White en sistemas triples. Esto culminó en su famoso y ampliamente citado artículo de 1919 Clasificación completa de sistemas de tríadas en 15 elementos, que fue el primer artículo en presentar las 80 soluciones del sistema triple de Steiner de tamaño 15, y en el que también se incluían otros sistemas tanto resolubles como no resolubles.
En 1922, Cole publicó su artículo Kirkman Parades que enumeraba por primera vez las siete soluciones no isomorfas al problema de las 15 colegialas, respondiendo así a una antigua pregunta sin resolver desde la década de 1850. Las siete soluciones de Kirkman corresponden a cuatro sistemas de Steiner diferentes cuando se elimina como restricción la resolubilidad en clases paralelas. Tres de los sistemas de Steiner tienen dos formas posibles de separarse en clases paralelas, es decir, dos soluciones de Kirkman cada uno, mientras que el cuarto tiene solo una, lo que da siete soluciones de Kirkman en total.
En la década de 1960, se demostró que los sistemas triples de Kirkman existen para "todos" los órdenes de n = 3 (mod 6). Esto fue probado por primera vez por Lu Jiaxi (陆家羲) en 1965, y lo envió a "Acta Mathematica Sinica", pero la revista pensó erróneamente que el problema ya se había resuelto anteriormente y rechazó su artículo en 1966, lo que luego se descubrió que era un error grave. Sus contribuciones académicas posteriores fueron interrumpidas por la Revolución Cultural y rechazadas nuevamente. En 1968, D. K. Ray-Chaudhuri y R. M. Wilson demostraron el teorema generalizado de forma independiente.
En 1974, RHF Denniston resolvió el problema de Sylvester al construir 13 soluciones de Kirkman disjuntas y usarlas para cubrir las 455 tripletas que se pueden formar con las 15 chicas. Su solución se analiza a continuación.