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

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

$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)$

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

$=404,756,352,000$

$=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 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 n!/q!(n−q)! ÷ p!/q!(p−q)! {\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.
* 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) (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 (15/3)=455{\textstyle {15 \choose 3}=455} tripletas posibles una vez en total, observando que $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). 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.
* 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 siglo XIX y principios del XX, 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 (15/3)=455{\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. 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:

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:

El correspondiente problema de Sylvester requiere 7 sistemas S(2,3,9) diferentes de 12 tripletes cada uno, que juntos cubren todo (9/3)=84{\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.

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.

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. 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.^{:67}$

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.^{: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.^{: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.^{: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,^{:91}$ y presentó dos de a $ellos.^{:75}$

## Generalización

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

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.

