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.^[1]

Publicación original del problema

Soluciones

Una solución a este problema es un ejemplo de un sistema triple de Kirkman,^[2] 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.^[3] 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ón	Grupo de automorfismo	Día 1	Día 2	Día 3	Día 4	Día 5	Día 6	Día 7
Solución I	Orden 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).	ABC DEF GHI JKL MNO	ADG BEH CJM FKN ILO	AEO BIJ CDN FHL GKM	AIM BDL CEK FGO HJN	AFJ BKO CGL DHM EIN	AHK BGN CFI DJO ELM	ALN BFM CHO DIK EGJ
Solución II	Orden 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).	ABC DEF GHI JKL MNO	ADG BEH CJM FKN ILO	AEO BIJ CDN FHL GKM	AFJ BGN CHO DIK ELM	AHK BFM CGL DJO EIN	AIM BDL CEK FGO HJN	ALN BKO CFI DHM EGJ
Solución III	Orden 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)	ABC DEF GHI JKL MNO	ADG BEH CJM FKN ILO	AEO BIM CDK FGL HJN	AFM BGN CHL DJO EIK	AHK BFJ CGO DIN ELM	AIJ BDL CEN FHO GKM	ALN BKO CFI DHM EGJ
Solución IV	Orden 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)	ABC DEF GHI JKL MNO	ADG BEH CJM FKN ILO	AEO BIM CDK FGL HJN	AFM BKO CHL DIN EGJ	AHK BGN CFI DJO ELM	AIJ BDL CEN FHO GKM	ALN BFJ CGO DHM EIK
Solución V	Grupo 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)	ABC DEF GHI JKL MNO	ADG BEJ CHM FKN ILO	AEM BDL CIK FGO HJN	AFH BKM CGL DJO EIN	AIJ BGN CEO DHK FLM	AKO BFI CDN EHL GJM	ALN BHO CFJ DIM EGK
Solución VI	Grupo 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)	ABC DEF GHI JKL MNO	ADG BEJ CHM FKN ILO	AEM BDL CIK FGO HJN	AFH BKM CGL DJO EIN	AIJ BHO CDN EGK FLM	AKO BGN CFJ DIM EHL	ALN BFI CEO DHK GJM
Solución VII	Orden 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)	ABC DEF GHI JKL MNO	ADG BEJ CHM FKN ILO	AEI BDN CJO FHL GKM	AFO BIK CGN DHJ ELM	AHK BFM CDL EGO IJN	AJM BGL CFI DKO EHN	ALN BHO CEK FGJ DIM

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,:

${\displaystyle 15!\times \left({\frac {1}{168}}+{\frac {1}{168}}+{\frac {1}{24}}+{\frac {1}{24}}+{\frac {1}{12}}+{\frac {1}{12}}+{\frac {1}{21}}\right)}$

${\displaystyle =15!\times {\frac {13}{42}}}$

${\displaystyle =404,756,352,000}$

${\displaystyle =2^{10}\times 3^{5}\times 5^{3}\times 7\times 11\times 13^{2}}$.

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^[4] y por Louise Duffield Cummings.^[5] 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 ${\textstyle {\frac {n!}{q!(n-q)!}}\div {\frac {p!}{q!(p-q)!}}}$. 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.^[4]

• En 1847, a la edad de 41 años, Thomas Kirkman publicó su artículo titulado Sobre un problema de combinaciones,(Kirkman, 1847) 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)^[5] (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^[6] 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^[7] 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 ${\textstyle {15 \choose 3}=455}$ tripletas posibles una vez en total, observando que ${\displaystyle 455=13\times 35}$. 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).^[4] 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 siglo XX.

• 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.^[4]

• 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.^[5]

• 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.^[4]

• 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.^[4] 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 siglo XIX y principios del XX, el rompecabezas apareció en varios libros de matemáticas recreativas de Édouard Lucas,^[8] W. W. Rouse Ball,^[9] Wilhelm Ahrens,^[10] y Henry Dudeney.^[11] Durante su vida, Kirkman se quejaría de que su serio trabajo matemático quedó eclipsado por la popularidad del problema de las escolares.^[5] 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",^[5] 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,^[12] 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^[3] 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,^[13] 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.^[14] 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.^[15]

• 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.^[16] 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 ${\textstyle {15 \choose 3}=455}$. No se encontró ninguna solución hasta 1974, cuando RHF Denniston resolvió la cuestión con una computadora en la Universidad de Leicester.^[16] 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.^[16] 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.^[16] 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.^[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.

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 ${\textstyle {9 \choose 3}=84}$. 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 siglo XXI, 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.^[19] 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.^[20]

Geometría de Galois

En 1910, George Conwell abordó el problema utilizando la geometría de Galois.^[21]

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.^[21]: 67

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

Cuando se eligen dos puntos como A y B de la recta ABC, cada una de las otras cinco rectas que pasan por A se cruza con sólo una de las otras cinco rectas que pasan por B. Los cinco puntos determinados por las intersecciones de estos pares de rectas, junto con los dos puntos A y B se denominan una "héptada".^[21]: 68

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.^[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

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.^[22]: 66 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,^[22]: 91 y presentó dos de a ellos.^[22]: 75

Generalización

El problema se puede generalizar a ${\displaystyle n}$ niñas, donde ${\displaystyle n}$ debe ser un múltiplo impar de 3 (es decir, ${\displaystyle n\equiv 3{\pmod {6}}}$), caminando en ternas para cumplir el requisito ${\textstyle {\frac {1}{2}}(n-1)}$, 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".^[23] Esto es una generalización del problema que Kirkman discutió primero, mientras que el famoso caso especial ${\displaystyle n=15}$ solo se propuso más adelante.^[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. 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.^[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.

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.^[26]

El problema de los recubrimientos resolubles considera el caso general de ${\displaystyle n}$ colegialas, ${\displaystyle g}$ 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.^[27]

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.^[28]

Véase también

• Estrategia Aprendizaje cooperativo para aumentar la interacción dentro de la enseñanza en el aula.
• Juego de cartas Dobble^[29]
• 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

1. Graham, Grötschel y Lovász, 1995
2. Weisstein, Eric W. «Kirkman's Schoolgirl Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
3. Cole, 1922
4. The Early History of Block Designs by Robin Wilson, Dept of Pure Mathematics, The Open University, UK
5. Cummings, 1918
6. Kirkman, 1850
7. Cayley, 1850
8. Lucas, 1883
9. Rouse Ball, 1892
10. Ahrens, 1901
11. Dudeney, 1917
12. Cole, F. N.; Cummings, Louise D.; White, H. S. (1917). «The Complete Enumeration of Triad Systems in 15 Elements». Proceedings of the National Academy of Sciences 3 (3): 197-199. Bibcode:1917PNAS....3..197C. PMC 1091209. PMID 16576216. doi:10.1073/pnas.3.3.197.
13. Lu, 1990
14. Colbourn y Dinitz, 2007, p. 13
15. Ray-Chaudhuri y Wilson, 1971
16. Denniston, R.H.F. (1974). «Sylvester's problem of the 15 schoolgirls». Discrete Mathematics 9 (3): 229-233. doi:10.1016/0012-365X(74)90004-1.
17. Kirkman's Ladies audio
18. Johnson, Tom; Jedrzejewski, Franck (2014). «Kirkman's Ladies, A Combinatorial Design». Looking at Numbers. pp. 37-55. ISBN 978-3-0348-0553-7. doi:10.1007/978-3-0348-0554-4_4.
19. Zhou, Junling; Chang, Yanxun (2014). «A new result on Sylvester's problem». Discrete Mathematics 331: 15-19. doi:10.1016/j.disc.2014.04.022.
20. Araya, Makoto & Harada, Masaaki. (2010). Mutually Disjoint Steiner Systems S(5, 8, 24) and 5-(24, 12, 48) Designs. Electr. J. Comb.. 17.
21. Conwell, George M. (1910). «The 3-space PG(3,2) and its Group». Annals of Mathematics 11 (2): 60-76. JSTOR 1967582. doi:10.2307/1967582.
22. Hirschfeld, J.W.P. (1985), Finite Projective Spaces of Three Dimensions, Oxford University Press, ISBN 0-19-853536-8.
23. Ball y Coxeter, 1987, pp. 287−289
24. Kirkman, 1847
25. Hartman, 1980
26. Banchero, Matías; Robledo, Franco; Romero, Pablo; Sartor, Pablo; Servetti, Camilo (2021). «Max-Diversity Orthogonal Regrouping of MBA Students Using a GRASP/VND Heuristic». Variable Neighborhood Search. Lecture Notes in Computer Science 12559. pp. 58-70. ISBN 978-3-030-69624-5. S2CID 232314621. doi:10.1007/978-3-030-69625-2_5.
27. Van Dam, Edwin R.; Haemers, Willem H.; Peek, Maurice B. M. (2003). «Equitable resolvable coverings». Journal of Combinatorial Designs 11 (2): 113-123. S2CID 120596961. doi:10.1002/jcd.10024.
28. Bryant y Danziger, 2011
29. McRobbie, Linda Rodriguez. «The Mind-Bending Math Behind Spot It!, the Beloved Family Card Game». Smithsonian Magazine (en inglés). Consultado el 1 de marzo de 2020.

Bibliografía

• Ahrens, W. (1901), Mathematische Unterhaltungen und Spiele, Leipzig: Teubner.
• Bryant, Darryn; Danziger, Peter (2011), «On bipartite 2-factorizations of ${\displaystyle K_{n}-I}$ and the Oberwolfach problem», Journal of Graph Theory 68 (1): 22-37, MR 2833961, S2CID 7478839, doi:10.1002/jgt.20538.
• Cayley, A. (1850), «On the triadic arrangements of seven and fifteen things», Philosophical Magazine 37 (247): 50-53, doi:10.1080/14786445008646550.
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd edición), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1.
• Cole, F.N. (1922), «Kirkman parades», Bulletin of the American Mathematical Society 28 (9): 435-437, doi:10.1090/S0002-9904-1922-03599-9.
• Cummings, L.D. (1918), «An undervalued Kirkman paper», Bulletin of the American Mathematical Society 24 (7): 336-339, doi:10.1090/S0002-9904-1918-03086-3.
• Dudeney, H.E. (1917), «Amusements in Mathematics», Nature (New York: Dover) 100 (2512): 302, Bibcode:1917Natur.100..302., S2CID 10245524, doi:10.1038/100302a0.
  • Dudeney, H.E. (1958), Amusements in Mathematics, Dover Recreational Math, Mineola (Nueva York): Dover, ISBN 978-0-486-20473-4.
• Graham, Ronald L.; Grötschel, Martin; Lovász, László (1995), Handbook of Combinatorics, Volume 2, Cambridge (Massachusetts): The MIT Press, ISBN 0-262-07171-1.
• Hartman, Alan (1980), «Kirkman's trombone player problem», Ars Combinatoria 10: 19-26.
• Lu, Jiaxi (1990), Collected Works of Lu Jiaxi on Combinatorial Designs, Huhhot: Inner Mongolia People's Press.
• Kirkman, Thomas P. (1847), «On a Problem in Combinations», The Cambridge and Dublin Mathematical Journal (Macmillan, Barclay, and Macmillan) II: 191-204.
• Kirkman, Thomas P. (1850), «Note on an unanswered prize question», The Cambridge and Dublin Mathematical Journal (Macmillan, Barclay and Macmillan) 5: 255-262.
• Lucas, É. (1883), Récréations Mathématiques 2, Paris: Gauthier-Villars, pp. 183-188.
• Ray-Chaudhuri, D.K.; Wilson, R.M. (1971), «Solution of Kirkman's schoolgirl problem, in Combinatorics, University of California, Los Angeles, 1968», Proceedings of Symposia in Pure Mathematics (Providence (Rhode Island): American Mathematical Society) XIX: 187-203, ISBN 978-0-8218-1419-2, doi:10.1090/pspum/019/9959.
• Rouse Ball, W.W. (1892), Mathematical Recreations and Essays, London: Macmillan.
  • Ball, W.W. Rouse; Coxeter, H.S.M. (1987) [1974], Mathematical Recreations and Essays (13th edición), Dover, pp. 287-289, ISBN 0-486-25357-0.

Enlaces externos

• Weisstein, Eric W. «Kirkman's schoolgirl problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
• Klarreich, Erica (9 de junio de 2015), «A design dilemma solved, minus designs.», Quanta Magazine.
• String (marzo de 2015): solución visualizada, Stack Exchange

• Datos: Q966333