Problema de las colegialas de Kirkman
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:

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 Wilson 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.

El problema de Sylvester
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. La idea de Denniston fue crear una solución de Kirkman para una sola semana, de tal manera que pudiera permutarse según una permutación específica de la duración del ciclo 13 para crear soluciones separadas para las semanas siguientes. 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. Denniston clasificó así los 455 tripletes en 35 filas de 13 tripletes cada una, siendo cada fila la órbita de un triple dado bajo la permutación. Para construir una solución de Sylvester, ninguna solución de Kirkman de una sola semana podría usar dos tripletes de la misma fila, de lo contrario colisionarían finalmente cuando se aplicara la permutación a uno de ellos. Resolver el problema de Sylvester equivale a encontrar un triplete de cada una de las 35 filas de manera que los 35 tripletes juntos formen una solución de Kirkman. 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. Para organizar los cálculos, etiquetó a las 15 niñas con las letras de la A a la O:

Día 1 ABJ CEM FKL HIN DGO
Día 2 ACH DEI FGM JLN BKO
Día 3 ADL BHM GIK CFN EJO
Día 4 AEG BIL CJK DMN FHO
Día 5 AFI BCD GHJ EKN LMO
Día 6 AKM DFJ EHL BGN CIO
Día 7 BEF CGL DHK IJM ANO

Detuvo la búsqueda en ese punto, sin seguir adelante para verificar la unicidad de la solución.

El compositor minimalista estadounidense Tom Johnson compuso una pieza musical titulada "Kirkman's Ladies" basada en la solución de Denniston.

En 2021, seguía sin saberse si existen otras soluciones no isomorfas al problema de Sylvester o cuántas soluciones hay.

9 colegialas y extensiones
El equivalente del problema de Kirkman para 9 colegialas da como resultado S(2,3,9), un plano afín isomorfo a las siguientes ternas de cada día:
Día 1: 123 456 789
Día 2: 147 258 369
Día 3: 159 267 348
Día 4: 168 249 357

El correspondiente problema de Sylvester requiere 7 sistemas S(2,3,9) diferentes de 12 tripletes cada uno, que juntos cubren todo . 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. 273-285). De hecho, puede haber 7 sistemas S(2,3,9) disjuntos, y todos esos conjuntos de 7 se dividen en dos categorías no isomorfas de tamaños 8640 y 6720, con 42 y 54 automorfismos respectivamente.

Solución 1:
              Día 1          Día 2          Día 3          Día 4
Semana 1    ABC.DEF.GHI    ADG.BEH.CFI    AEI.BFG.CDH    AFH.BDI.CEG
Semana 2    ABD.CEH.FGI    ACF.BGH.DEI    AEG.BCI.DFH    AHI.BEF.CDG
Semana 3    ABE.CDI.FGH    ACG.BDF.EHI    ADH.BGI.CEF    AFI.BCH.DEG
Semana 4    ABF.CEI.DGH    ACD.BHI.EFG    AEH.BCG.DFI    AGI.BDE.CFH
Semana 5    ABG.CDE.FHI    ACH.BEI.DFG    ADI.BCF.EGH    AEF.BDH.CGI
Semana 6    ABH.CDF.EGI    ACI.BDG.EFH    ADE.BFI.CGH    AFG.BCE.DHI
Semana 7    ABI.CFG.DEH    ACE.BFH.DGI    ADF.BEG.CHI    AGH.BCD.EFI
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). Aplicando el 9! = 362880 permutaciones de ABCDEFGHI, hay 362880/42 = 8640 soluciones diferentes, todas isomorfas a la Solución 1.

Solución 2:
              Día 1          Día 2          Día 3          Día 4
Semana 1    ABC.DEF.GHI    ADG.BEH.CFI    AEI.BFG.CDH    AFH.BDI.CEG
Semana 2    ABD.CEH.FGI    ACF.BGH.DEI    AEG.BCI.DFH    AHI.BEF.CDG
Semana 3    ABE.CGH.DFI    ACI.BFH.DEG    ADH.BGI.CEF    AFG.BCD.EHI
Semana 4    ABF.CGI.DEH    ACE.BDG.FHI    ADI.BCH.EFG    AGH.BEI.CDF
Semana 5    ABG.CDI.EFH    ACH.BDF.EGI    ADE.BHI.CFG    AFI.BCE.DGH
Semana 6    ABH.CEI.DFG    ACD.BFI.EGH    AEF.BCG.DHI    AGI.BDE.CFH
Semana 7    ABI.CDE.FGH    ACG.BDH.EFI    ADF.BEG.CHI    AEH.BCF.DGI
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). Aplicando las 9! = 362880 permutaciones de ABCDEFGHI, hay 362880/54 = 6720 soluciones diferentes, todas isomorfas a la Solución 2.

Por lo tanto, hay 8640 + 6720 = 15360 soluciones en total, que se dividen en dos categorías no isomorfas.

Además de S(2,3,9), Kramer y Mesner examinaron otros sistemas que podrían derivarse del sistema de Steiner S(5,6,12), y encontraron que podría haber hasta 2 sistemas S(5,6,12) disjuntos, hasta 2 sistemas S(4,5,11) disjuntos y hasta 5 sistemas S(3,4,10) disjuntos. Todos estos conjuntos de 2 o 5 son respectivamente isomorfos entre sí.

Sistemas más grandes
En el , otros autores han visitado análogos del problema de Sylvester bajo términos como sistemas disjuntos de Steiner o sistemas disjuntos Kirkman o LKTS (grandes conjuntos de sistemas triples de Kirkman), para n > 15. También se han investigado conjuntos similares de sistemas de Steiner disjuntos para el sistema de Steiner S(5,8,24), además de los sistemas triples.

Geometría de Galois
En 1910, George Conwell abordó el problema utilizando la geometría de Galois.

El cuerpo finito GF(2) con dos elementos se usa con cuatro coordenadas homogéneas para formar PG(3,2), que tiene 15 puntos, 3 puntos en una recta, 7 puntos y 7 rectas en un plano. Un plano puede considerarse como un cuadrángulo completo junto con la recta que pasa por sus puntos diagonales. Cada punto está en 7 líneas y hay 35 líneas en total.

Las líneas de PG(3,2) se identifican por sus coordenadas plückerianas en PG(5,2) con 63 puntos, 35 de los cuales representan líneas de PG(3,2). Estos 35 puntos forman la superficie S conocida como cuádrica de Klein. Para cada uno de los 28 puntos de S hay 6 rectas que lo atraviesan y que no se cruzan con S.

Como la semana tiene siete días, la héptada es una parte importante de la solución:

Una héptada está determinada por dos de sus puntos cualesquiera. Cada uno de los 28 puntos de S se encuentra en dos héptadas, y hay 8 héptadas. El grupo lineal proyectivo PGL(3,2) es isomorfo al grupo alternante en las 8 héptadas.

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.

Extensiones y empaquetados
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. Hay 56 extensiones y 240 empaquetados. Cuando Hirschfeld consideró el problema en su Espacios proyectivos finitos de tres dimensiones (1985), observó que algunas soluciones corresponden a empaquetamientos de PG(3,2), esencialmente como lo describió Conwell anteriormente, y presentó dos de a ellos.

Generalización
El problema se puede generalizar a  niñas, donde  debe ser un múltiplo impar de 3 (es decir, ), caminando en ternas para cumplir el requisito , nuevamente, de que ningún par de niñas camine en la misma fila dos veces. La solución a esta generalización es un sistema triple de Steiner, un S(2, 3, 6t + 3) con paralelismo (es decir, una en la que cada uno de los 6t + 3 elementos ocurre exactamente una vez en cada bloque de conjuntos de 3 elementos), conocido como "sistema triple de Kirkman". Esto es una generalización del problema que Kirkman discutió primero, mientras que el famoso caso especial  solo se propuso más adelante. D. K. Ray-Chaudhuri y R. M. Wilson publicaron una solución completa al caso general en 1968, aunque ya había sido resuelta por Lu Jiaxi (陆家羲) en 1965, pero no se había publicado en ese momento.

Se pueden considerar muchas variaciones del problema básico. Alan Hartman resuelve un problema de este tipo con el requisito de que ningún trío camine en fila de cuatro más de una vez utilizando sistemas cuádruples de Steiner.

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.

Como se trata de una estrategia de reagrupación en la que todos los grupos son ortogonales, este proceso dentro del problema de organizar un grupo grande en grupos más pequeños donde no hay dos personas que compartan el mismo grupo dos veces puede denominarse reagrupación ortogonal.

El problema de los recubrimientos resolubles considera el caso general de  colegialas,  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.

El problema de Oberwolfach, que consiste en descomponer un grafo completo en copias con ligaduras separadas de un grafo 2-regular determinado, también generaliza el problema de las colegialas de Kirkman, que es el caso especial del problema de Oberwolfach en el que el grafo 2-regular consta de cinco triángulos disjuntos.

Véase también
 Estrategia Aprendizaje cooperativo para aumentar la interacción dentro de la enseñanza en el aula.
 Juego de cartas Dobble
 Cena progresiva; diseño de colocación de comensales
 Eventos de contacto rápido
Competiciones deportivas
Combinatoria
R M Wilson
Dijen K. Ray-Chaudhuri
Matemática discreta

Referencias

Bibliografía

Enlaces externos

String (marzo de 2015): solución visualizada, Stack Exchange

Problemas matemáticos
Problemas de matemática recreativa
Combinatoria
Ciencia y tecnología de Reino Unido del siglo XIX
Ciencia de 1850
Reino Unido  en 1850
Kirkman, problema
El problema de las colegialas de Kirkman es una cuestión matemática de carácter combinatorio propuesta por Thomas Kirkman enen la publicación " The Lady's and Gentleman's Diary " ( El Diario de Damas y Caballeros ) ( Consulta VI ; página El problema dice : Quince alumnas salen formadas de tres en fondo durante siete días seguidos : se requiere formar las 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 Las siete soluciones se resumen en la siguiente tabla , en la que se representan a lasniñas mediante las letras de la A a la O : 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 Wilson y por Louise Duffield Cummings . Su cronología es la siguiente : En 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 Woolhouse preguntó : " ¿ Cuántas tríadas pueden formar se 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 decon los valores p =y q = En a la edad deañ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 =o( mod También consideró otros valores de n , aunque no pudo generalizar su planteamiento . Dio dos secuencias diferentes de sistemas triples , una para n = etc. , y otra para n = etc . Utilizando estas proposiciones , demostró que existen sistemas triples para " todos " los valores de n =o( mod( 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 =y 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( vea se más abajo ) . En Kirkman planteó el problema de lascolegialas , que se volvería mucho más famoso que el artículo deque 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 integrar se 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 y esta omisión tendría graves consecuencias para la invención y la prioridad , como se ve a continuación . También en James Joseph Sylvester preguntó si podría habersoluciones diferentes al problema de lasalumnas 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 durantesemanas , 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 desemanas ? Este problema era mucho más difícil y RHF Denniston finalmente proporcionaría una solución utilizando un computador en( vea se más abajo ) . En Robert Richard Anstice proporcionó una solución cíclica , formada mediante la construcción de las cinco tripletas del primer día para que fuerang , AbC , aDE , cef , BdF en lossímbolosBCDEFGabcdefg y luego cambiando cíclicamente cada día subsiguiente por una letra , dejandosin cambios ( las mayúsculas permanecen en mayúscula y las minúsculas permanecen en minúscula ) . Si las cuatro tripletas sin el elemento( 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 Jakob Steiner , completamente ignorante del artículo de Kirkman de 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 seao( mod pero dejó abierta la pregunta de en qué condiciones es posible , sin saber que Kirkman ya había resuelto esa cuestión en 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 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( sin reconocer a Kirkman ) , que autores posteriores como Louise Cummings lo han considerado un plagio . El propio Kirkman expresó su amargura . En 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 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 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 deen 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 En 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 deClasificación completa de sistemas de tríadas enelementos , que fue el primer artículo en presentar lassoluciones del sistema triple de Steiner de tamaño y en el que también se incluían otros sistemas tanto resolubles como no resolubles . En Cole publicó su artículo Kirkman Parades que enumeraba por primera vez las siete soluciones no isomorfas al problema de lascolegialas , respondiendo así a una antigua pregunta sin resolver desde la década de 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 separar se 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 se demostró que los sistemas triples de Kirkman existen para " todos " los órdenes de n =( mod Esto fue probado por primera vez por Lu Jiaxi ( 陆家羲 ) en 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 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 D. K. Ray-Chaudhuri y R. M. Wilson demostraron el teorema generalizado de forma independiente . En RHF Denniston resolvió el problema de Sylvester al construirsoluciones de Kirkman disjuntas y usar las para cubrir lastripletas que se pueden formar con laschicas . Su solución se analiza a continuación . El problema de Sylvester James Joseph Sylvester enpreguntó si se podrían construirsistemas de Kirkman separados formados portripletas cada uno para utilizar todas las chicas \ . No se encontró ninguna solución hasta cuando RHF Denniston resolvió la cuestión con una computadora en la Universidad de Leicester . La idea de Denniston fue crear una solución de Kirkman para una sola semana , de tal manera que pudiera permutar se según una permutación específica de la duración del ciclopara crear soluciones separadas para las semanas siguientes . Eligió una permutación con un solo ciclo dey dos puntos fijos como2468101214 ) ( 15 ) . Bajo esta permutación , un triplete comose asignaría a ...yantes de repetir se . Denniston clasificó así lostripletes enfilas detripletes cada una , siendo cada fila la órbita de un triple dado bajo la permutación . Para construir una solución de Sylvester , ninguna solución de Kirkman de una sola semana podría usar dos tripletes de la misma fila , de lo contrario colisionarían finalmente cuando se aplicara la permutación a uno de ellos . Resolver el problema de Sylvester equivale a encontrar un triplete de cada una de lasfilas de manera que lostripletes juntos formen una solución de Kirkman . Luego programó una computadora Elliottpara que hiciera exactamente esa búsqueda , lo que le llevóhoras encontrar esta solución para la primera semana . Para organizar los cálculos , etiquetó a lasniñas con las letras de la A a la O: DíaABJ CEM FKL HIN DGO DíaACH DEI FGM JLN BKO DíaADL BHM GIK CFN EJO DíaAEG BIL CJK DMN FHO DíaAFI BCD GHJ EKN LMO DíaAKM DFJ EHL BGN CIO DíaBEF CGL DHK IJM ANO Detuvo la búsqueda en ese punto , sin seguir adelante para verificar la unicidad de la solución . El compositor minimalista estadounidense Tom Johnson compuso una pieza musical titulada " Kirkman's Ladies " basada en la solución de Denniston . En seguía sin saber se si existen otras soluciones no isomorfas al problema de Sylvester o cuántas soluciones hay . 9 colegialas y extensiones El equivalente del problema de Kirkman paracolegialas da como resultado S( 2,3,9 ) , un plano afín isomorfo a las siguientes ternas de cada día : Día456 Día258 Día267 Día249 El correspondiente problema de Sylvester requieresistemas S( 2,3,9 ) diferentes detripletes cada uno , que juntos cubren todo \ . La solución conocida por Baysfue encontrada nuevamente desde una dirección diferente por Earl Kramer y Dale Mesner en un estudio de el artículo titulado Intersecciones entre sistemas de Steiner ( J Combinatorial Theory , Vol págs . De hecho , puede habersistemas S( 2,3,9 ) disjuntos , y todos esos conjuntos dese dividen en dos categorías no isomorfas de tamañosy conyautomorfismos respectivamente . Solución Día Día Día Día 4 Semana ABC.DEF.GHI ADG.BEH.CFI AEI.BFG.CDH AFH.BDI.CEG Semana ABD.CEH.FGI ACF.BGH.DEI AEG.BCI.DFH AHI.BEF.CDG Semana ABE.CDI.FGH ACG.BDF.EHI ADH.BGI.CEF AFI.BCH.DEG Semana ABF.CEI.DGH ACD.BHI.EFG AEH.BCG.DFI AGI.BDE.CFH Semana ABG.CDE.FHI ACH.BEI.DFG ADI.BCF.EGH AEF.BDH.CGI Semana ABH.CDF.EGI ACI.BDG.EFH ADE.BFI.CGH AFG.BCE.DHI Semana ABI.CFG.DEH ACE.BFH.DGI ADF.BEG.CHI AGH.BCD.EFI La solucióntieneautomorfismos , generados por las permutaciones ( A I D C F H ) ( B G ) y ( C F D H E I ) ( B G ) . Aplicando el =permutaciones de ABCDEFGHI , hay42 =soluciones diferentes , todas isomorfas a la Solución Solución Día Día Día Día 4 Semana ABC.DEF.GHI ADG.BEH.CFI AEI.BFG.CDH AFH.BDI.CEG Semana ABD.CEH.FGI ACF.BGH.DEI AEG.BCI.DFH AHI.BEF.CDG Semana ABE.CGH.DFI ACI.BFH.DEG ADH.BGI.CEF AFG.BCD.EHI Semana ABF.CGI.DEH ACE.BDG.FHI ADI.BCH.EFG AGH.BEI.CDF Semana ABG.CDI.EFH ACH.BDF.EGI ADE.BHI.CFG AFI.BCE.DGH Semana ABH.CEI.DFG ACD.BFI.EGH AEF.BCG.DHI AGI.BDE.CFH Semana ABI.CDE.FGH ACG.BDH.EFI ADF.BEG.CHI AEH.BCF.DGI La solucióntieneautomorfismos , generados por las permutaciones ( A B D ) ( C H E ) ( F G I ) y ( A I F D E H ) ( B G ) . Aplicando las =permutaciones de ABCDEFGHI , hay54 =soluciones diferentes , todas isomorfas a la Solución Por lo tanto , hay+=soluciones en total , que se dividen en dos categorías no isomorfas . Además de S( 2,3,9 ) , Kramer y Mesner examinaron otros sistemas que podrían derivar se del sistema de Steiner S( 5,6,12 ) , y encontraron que podría haber hastasistemas S( 5,6,12 ) disjuntos , hastasistemas S( 4,5,11 ) disjuntos y hastasistemas S( 3,4,10 ) disjuntos . Todos estos conjuntos deoson respectivamente isomorfos entre sí . Sistemas más grandes En el , otros autores han visitado análogos del problema de Sylvester bajo términos como sistemas disjuntos de Steiner o sistemas disjuntos Kirkman o LKTS ( grandes conjuntos de sistemas triples de Kirkman ) , para n > También se han investigado conjuntos similares de sistemas de Steiner disjuntos para el sistema de Steiner S( 5,8,24 ) , además de los sistemas triples . Geometría de Galois En George Conwell abordó el problema utilizando la geometría de Galois . El cuerpo finito GF( 2 ) con dos elementos se usa con cuatro coordenadas homogéneas para formar PG( 3,2 ) , que tienepuntos,puntos en una recta,puntos yrectas en un plano . Un plano puede considerar se como un cuadrángulo completo junto con la recta que pasa por sus puntos diagonales . Cada punto está enlíneas y haylíneas en total . Las líneas de PG( 3,2 ) se identifican por sus coordenadas plückerianas en PG( 5,2 ) conpuntos,de los cuales representan líneas de PG( 3,2 ) . Estospuntos forman la superficie S conocida como cuádrica de Klein . Para cada uno de lospuntos de S hayrectas que lo atraviesan y que no se cruzan con S. Como la semana tiene siete días , la héptada es una parte importante de la solución : Una héptada está determinada por dos de sus puntos cualesquiera . Cada uno de lospuntos de S se encuentra en dos héptadas , y hayhéptadas . El grupo lineal proyectivo PGL( 3,2 ) es isomorfo al grupo alternante en lashéptadas . El problema de las colegialas consiste en encontrar siete rectas en elespacio que no se crucen y que dos rectas cualesquiera siempre tengan una héptada en común . Extensiones y empaquetados 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 . Hayextensiones yempaquetados . Cuando Hirschfeld consideró el problema en su Espacios proyectivos finitos de tres dimensiones observó que algunas soluciones corresponden a empaquetamientos de PG( 3,2 ) , esencialmente como lo describió Conwell anteriormente , y presentó dos de a ellos . Generalización El problema se puede generalizar a niñas , donde debe ser un múltiplo impar de( es decir , ) , caminando en ternas para cumplir el requisito , nuevamente , de que ningún par de niñas camine en la misma fila dos veces . La solución a esta generalización es un sistema triple de Steiner , un S( 2 , +con paralelismo ( es decir , una en la que cada uno de los +elementos ocurre exactamente una vez en cada bloque de conjuntos deelementos ) , conocido como " sistema triple de Kirkman " . Esto es una generalización del problema que Kirkman discutió primero , mientras que el famoso caso especial solo se propuso más adelante . D. K. Ray-Chaudhuri y R. M. Wilson publicaron una solución completa al caso general en aunque ya había sido resuelta por Lu Jiaxi ( 陆家羲 ) en pero no se había publicado en ese momento . Se pueden considerar muchas variaciones del problema básico . Alan Hartman resuelve un problema de este tipo con el requisito de que ningún trío camine en fila de cuatro más de una vez utilizando sistemas cuádruples de Steiner . Más recientemente , ha ganado interés un problema similar conocido como problema social del golfista , que trata congolfistas que quieren jugar con diferentes personas cada día en grupos de en el transcurso dedías . Como se trata de una estrategia de reagrupación en la que todos los grupos son ortogonales , este proceso dentro del problema de organizar un grupo grande en grupos más pequeños donde no hay dos personas que compartan el mismo grupo dos veces puede denominar se reagrupación ortogonal . El problema de los recubrimientos resolubles considera el caso general de colegialas , 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 . El problema de Oberwolfach , que consiste en descomponer un grafo completo en copias con ligaduras separadas de un graforegular determinado , también generaliza el problema de las colegialas de Kirkman , que es el caso especial del problema de Oberwolfach en el que el graforegular consta de cinco triángulos disjuntos . Vea se también Estrategia Aprendizaje cooperativo para aumentar la interacción dentro de la enseñanza en el aula . Juego de cartas Dobble Cena progresiva ; diseño de colocación de comensales Eventos de contacto rápido Competiciones deportivas Combinatoria R M Wilson Dijen K. Ray-Chaudhuri Matemática discreta Referencias Bibliografía Enlaces externos String ( marzo de solución visualizada , Stack Exchange Problemas matemáticos Problemas de matemática recreativa Combinatoria Ciencia y tecnología de Reino Unido del siglo XIX Ciencia de Reino Unido en Kirkman , problema