Quince señoritas caminan en una escuela de tres en tres durante siete días seguidos: es necesario organizarlas diariamente de tal manera que ninguna de ellas camine dos veces en fila. [2]
Soluciones
Una solución a este problema es un ejemplo de un sistema triple de Kirkman , [3] que es un sistema triple de Steiner que tiene 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. Dichos sistemas de Steiner que tienen un paralelismo también se denominan resolubles .
Hay exactamente siete soluciones no isomorfas para el problema de la colegiala, como las enumeró originalmente Frank Nelson Cole en Kirkman Parades en 1922. [4] Las siete soluciones se resumen en la siguiente tabla, que indica las 15 niñas con las letras A a O.
A partir del número de automorfismos para cada solución y de la definición de un grupo de automorfismos, el número total de soluciones, incluidas las soluciones isomorfas, es por lo tanto:
.
Historia
Publicación original del problema
El problema tiene una larga historia. Esta sección se basa en trabajos históricos realizados en diferentes momentos por Robin Wilson [5] y por Louise Duffield Cummings [6] . La historia es la siguiente:
En 1844, Wesley Woolhouse , editor de The Lady's and Gentleman's Diary en ese momento, hizo la pregunta general: "Determine el número de combinaciones que se pueden hacer a partir de n símbolos, p símbolos en cada uno; con esta limitación, que ninguna combinación de q símbolos, que pueda aparecer en cualquiera de ellos, se repetirá en ningún otro". Solo se recibieron dos respuestas, una incorrecta y la otra respondiendo correctamente a la pregunta con . Como la pregunta no pedía nada más que el número de combinaciones, no se recibió nada sobre las condiciones en n , p o q cuando se podría lograr tal solución.
En 1846, Woolhouse preguntó: "¿Cuántas tríadas se pueden formar a partir de n símbolos, de modo que ningún par de símbolos esté comprendido más de una vez entre ellas?". Esto equivale a repetir su pregunta de 1844 con los valores p = 3 y q = 2. [5]
En 1847, a la edad de 41 años, Thomas Kirkman publicó su artículo titulado On a Problem in Combined Systems (Kirkman 1847) que describía y resolvía exhaustivamente el problema de construir sistemas triples de orden n donde n = 1 o 3 ( mod 6). También consideró otros valores de n aunque el equilibrio perfecto no fuera posible. Dio dos secuencias diferentes de sistemas triples, una para n = 7, 15, 19, 27, etc., y otra para n = 9, 13, 25, etc. Usando estas proposiciones, demostró que los sistemas triples existen para todos los valores de n = 1 o 3 (mod 6) [7] (no necesariamente los resolubles, pero los sistemas triples en general). También describió los sistemas triples resolubles en detalle en ese artículo, particularmente para n = 9 y 15; los sistemas triples resolubles ahora se conocen como sistemas triples de Kirkman. No pudo decir de manera concluyente para qué otros valores de n existirían sistemas triples resolubles ; Ese problema no se resolvería hasta la década de 1960 (véase más adelante).
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 [8] que más tarde se descubriría que era isomorfa a la Solución I anterior. Kirkman afirmó que era la única solución posible, pero eso era incorrecto. La solución de Arthur Cayley [9] se descubriría más tarde que era isomorfa a la Solución II. Ambas soluciones podrían incluirse 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 colegialas, Kirkman olvidó 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 colegialas que utilizarían todos los triples exactamente una vez en total, observando que . En 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 período de 13 semanas? Este problema era mucho más difícil, y RHF Denniston finalmente proporcionaría una solución computacional en 1974 (ver más abajo).
En 1852, Robert Richard Anstice proporcionó una solución cíclica , hecha construyendo los cinco triples del primer día para que fueran 0Gg, AbC, aDE, cef, BdF en los 15 símbolos 0ABCDEFGabcdefg y luego desplazando cíclicamente cada día subsiguiente en una letra mientras se dejaba el 0 sin cambios (las mayúsculas permanecían mayúsculas y las minúsculas permanecían minúsculas). [5] Si se toman los cuatro triples sin el elemento 0 ( AbC, aDE, cef, BdF ) y se convierten las mayúsculas en minúsculas ( abc, ade, cef, bdf ), forman lo que más tarde se llamaría la configuración de Pasch . [10] La configuración de Pasch se volvería importante en las técnicas de rechazo de isomorfos en el siglo XX.
En 1853, Jakob Steiner , completamente inconsciente del artículo de Kirkman de 1847, publicó su artículo titulado Combinatorische Aufgabe , que reintrodujo 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 cuándo se realizaría esto, sin saber que Kirkman ya había resuelto esa cuestión en 1847. A medida que este artículo fue leído más ampliamente por el establishment matemático europeo, los sistemas triples más tarde se conocieron como sistemas triples de Steiner . [5]
En 1859, Michel Reiss respondió a las preguntas planteadas por Steiner, utilizando una metodología y una notación tan similares al trabajo de Kirkman de 1847 (sin reconocer a Kirkman), que autores posteriores como Louise Cummings lo han denunciado por plagio . [11] El propio Kirkman expresó su amargura.
En 1860, Benjamin Peirce unificó varias soluciones dispares presentadas hasta el momento y demostró que había tres posibles estructuras de solución cíclica: una correspondiente al trabajo de Anstice, una basada en la solución de Kirkman y otra en la de Cayley. [5]
En 1861, James Joseph Sylvester volvió a plantear 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ó sus afirmaciones, afirmando que cuando escribió sus artículos nunca había estado en Cambridge ni había oído hablar del trabajo de Sylvester. [5] Esta disputa de prioridad condujo a un enfrentamiento entre Sylvester y Kirkman.
En 1861-1862, Kirkman tuvo un altercado con Arthur Cayley por un asunto no relacionado (Cayley decidió no publicar una serie de artículos de Kirkman sobre la teoría de grupos y los poliedros , lo que le costó el reconocimiento de la comunidad matemática europea), lo que contribuyó aún más a que el mundo de las matemáticas lo marginara. Su exhaustivo artículo de 1847, en particular, cayó en el olvido, y muchos autores posteriores le dieron crédito a Steiner o a Reiss, sin conocer la historia.
La popularidad del rompecabezas de la colegiala en sí no se vio afectada por los conflictos académicos de Kirkman, y a fines del siglo XIX y principios del XX el rompecabezas apareció en varios libros de matemáticas recreativas de Édouard Lucas , [12] Rouse Ball , [13] Wilhelm Ahrens , [14] y Henry Dudeney . [15] Durante su vida, Kirkman se quejaría de que su trabajo matemático serio se viera eclipsado por la popularidad del problema de la colegiala. [16] Kirkman murió en 1895.
En 1918, el serio trabajo matemático de Kirkman volvió a recibir mayor atención por parte de Louise Duffield Cummings en un artículo titulado An Undervalued Kirkman Paper [17] que analizaba la historia temprana del campo y corregía la omisión histórica.
Casi al mismo tiempo, Cummings trabajaba 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 [18] , que fue el primer artículo en el que se exponían las 80 soluciones del sistema triple de Steiner de tamaño 15. Estas incluían sistemas resolubles y no resolubles.
En 1922, Cole publicó su artículo Kirkman Parades [4], en el que se enumeraban por primera vez las siete soluciones no isomorfas del problema de las 15 colegialas, respondiendo así a una pregunta que se planteaba 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 capacidad de resolución en clases paralelas. Tres de los sistemas de Steiner tienen dos formas posibles de separarse en clases paralelas, lo que significa 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 n = 3 (mod 6). Esto fue demostrado por primera vez por Lu Jiaxi ( chino :陆家羲) en 1965, [19] y lo envió a Acta Mathematica Sinica , pero la revista pensó erróneamente que el problema ya había sido resuelto y rechazó su artículo en 1966, lo que más tarde se descubrió que era un grave error. [20] Sus contribuciones académicas posteriores se vieron interrumpidas por la Revolución Cultural y fueron rechazadas nuevamente. En 1968, el teorema generalizado fue demostrado de forma independiente por DK Ray-Chaudhuri y RM Wilson . [21]
En 1974, RHF Denniston resolvió el problema de Sylvester de construir 13 soluciones disjuntas de Kirkman y usarlas para cubrir los 455 triples de las 15 chicas. [22] Su solución se analiza a continuación.
El problema de Sylvester
En 1850, James Joseph Sylvester preguntó si se podían construir 13 sistemas Kirkman disjuntos de 35 triples cada uno para utilizar todos los triples en 15 niñas. No se encontró ninguna solución hasta 1974, cuando RHF Denniston, de la Universidad de Leicester, la construyó con una computadora. [22] La idea de Denniston fue crear una solución Kirkman de una sola semana de tal manera que pudiera permutarse de acuerdo con una permutación específica de longitud de ciclo 13 para crear soluciones disjuntas para las semanas posteriores; 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 triple como 123 se mapearía a 234, 345, ... (11, 12, 13), (12, 13, 1) y (13, 1, 2) antes de repetirse. Denniston clasificó así los 455 triples en 35 filas de 13 triples cada una, siendo cada fila la órbita de un triple dado bajo la permutación. [22] Para construir una solución de Sylvester, ninguna solución de Kirkman de una sola semana podría utilizar dos triples de la misma fila, de lo contrario, eventualmente colisionarían cuando se aplicara la permutación a uno de ellos. Resolver el problema de Sylvester es equivalente a encontrar un triple de cada una de las 35 filas de modo que los 35 triples juntos formen una solución de Kirkman. Luego le pidió a una computadora Elliott 4130 que hiciera exactamente esa búsqueda, lo que le llevó 7 horas encontrar esta solución de la primera semana, [22] etiquetando a las 15 niñas con las letras A a O :
Día 1 ABJ CEM FKL HIN DGODía 2 ACH DEI FGM JLN BKODía 3 ADL BHM GIK CFN EJODía 4 AEG BIL CJK DMN FHODía 5 AFI BCD GHJ EKN LMODía 6 AKM DFJ EHL BGN CIODía 7 BEF CGL DHK IJM ANO
Detuvo la búsqueda en ese punto, sin intentar establecer la unicidad. [22]
El compositor minimalista estadounidense Tom Johnson compuso una pieza musical llamada Kirkman's Ladies basada en la solución de Denniston. [23] [24]
A partir de 2021, no se sabe si existen otras soluciones no isomorfas para el problema de Sylvester, ni 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 en cada día:
El problema de Sylvester correspondiente pide 7 sistemas S(2,3,9) diferentes de 12 triples cada uno, que juntos cubran todos los triples. Esta solución era conocida por Bays (1917), que fue encontrada nuevamente desde una dirección diferente por Earl Kramer y Dale Mesner en un artículo de 1974 titulado Intersections Among Steiner Systems (J Combinatorial Theory, Vol 16 pp 273-285). De hecho, puede haber 7 sistemas S(2,3,9) disjuntos, y todos esos conjuntos de 7 caen 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 las 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 de S(5,6,12) y descubrieron 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 isomorfos entre sí, respectivamente.
Sistemas más grandes e investigación continua
En el siglo XXI, otros autores han tratado análogos del problema de Sylvester bajo términos como "sistemas Steiner disjuntos" o "sistemas Kirkman disjuntos" o "LKTS" (Grandes conjuntos de sistemas triples de Kirkman), para n > 15. [25] También se han investigado conjuntos similares de sistemas Steiner disjuntos para el sistema Steiner S(5,8,24) además de los sistemas triples. [26]
Geometría de Galois
En 1910, el problema fue abordado utilizando la geometría de Galois por George Conwell. [27]
El campo de Galois GF(2) con dos elementos se utiliza con cuatro coordenadas homogéneas para formar PG(3,2) que tiene 15 puntos, 3 puntos en una línea, 7 puntos y 7 líneas en un plano. Un plano puede considerarse un cuadrilátero completo junto con la línea 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 de Plücker 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 la cuádrica de Klein . Para cada uno de los 28 puntos de S hay 6 líneas que lo pasan y que no intersecan a S. [27] : 67
Como hay siete días en la semana, la heptada 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, los designamos como una "heptada". [27] : 68
Una heptada está determinada por dos de sus puntos. Cada uno de los 28 puntos de S se encuentra en dos heptadas. Hay 8 heptadas. El grupo lineal proyectivo PGL(3,2) es isomorfo al grupo alternado de las 8 heptadas. [27] : 69
El problema de la colegiala consiste en encontrar siete líneas en el espacio 5 que no se intersequen y tales que dos líneas cualesquiera tengan siempre una heptada en común. [27] : 74
Spreads y embalajes
En PG(3,2), una partición de los puntos en líneas se llama extensión , y una partición de las líneas en extensiones se llama empaquetamiento o paralelismo . [28] : 66 Hay 56 extensiones y 240 empaquetamientos. Cuando Hirschfeld consideró el problema en sus Espacios proyectivos finitos de tres dimensiones (1985), notó que algunas soluciones corresponden a empaquetamientos de PG(3,2), esencialmente como lo describió Conwell anteriormente, [28] : 91 y presentó dos de ellos. [28] : 75
Generalización
El problema se puede generalizar a las niñas, donde debe ser un múltiplo impar de 3 (es decir ), que caminan en tríos durante días, con el requisito, de nuevo, 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, 6 t + 3) con paralelismo (es decir, uno en el que cada uno de los 6 t + 3 elementos ocurre exactamente una vez en cada bloque de conjuntos de 3 elementos), conocido como un sistema triple de Kirkman . [29] Esta es la generalización del problema que Kirkman discutió primero, mientras que el famoso caso especial solo se propuso más tarde. [30] Una solución completa al caso general fue publicada por DK Ray-Chaudhuri y RM Wilson en 1968, [31] aunque ya había sido resuelta por Lu Jiaxi ( chino :陆家羲) en 1965, [32] pero no había sido publicada en ese momento. [33]
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 una fila de cuatro más de una vez [34] utilizando sistemas cuádruples de Steiner.
Más recientemente, ha ganado interés un problema similar conocido como el Problema del Golfista Social , que trata de 32 golfistas que quieren jugar con diferentes personas cada día en grupos de 4, a lo largo de 10 días.
Como se trata de una estrategia de reagrupamiento en la que todos los grupos son ortogonales, este proceso dentro del problema de organizar un grupo grande en grupos más pequeños en los que no hay dos personas que compartan el mismo grupo dos veces puede denominarse reagrupamiento ortogonal. [35]
El problema de coberturas resolubles considera el caso general de grupos de chicas, donde cada par de chicas debe estar en el mismo grupo en algún momento, pero queremos utilizar la menor cantidad de días posible. Esto se puede utilizar, por ejemplo, para programar un plan de mesas rotativas, en el que cada par de invitados debe estar en algún momento en la misma mesa. [36]
El problema de Oberwolfach , que consiste en descomponer un grafo completo en copias disjuntas de un grafo 2 - regular dado , también generaliza el problema de la colegiala de Kirkman. El problema de Kirkman es el caso especial del problema de Oberwolfach en el que el grafo 2-regular consta de cinco triángulos disjuntos. [37]
^ Cole, FN; Cummings, Louise D.; White, HS (1917). "La enumeración completa de sistemas de tríadas en 15 elementos". Actas de la Academia Nacional de Ciencias . 3 (3): 197–199. Bibcode :1917PNAS....3..197C. doi : 10.1073/pnas.3.3.197 . PMC 1091209 . PMID 16576216.
^ Lu 1990
^ Colbourn y Dinitz 2007, pág. 13
^ Ray-Chaudhuri y Wilson 1971
^ abcde Denniston, RHF (1974). "El problema de Sylvester de las 15 colegialas". Matemáticas discretas . 9 (3): 229–233. doi : 10.1016/0012-365X(74)90004-1 .
^ Audio de Las damas de Kirkman
^ Johnson, Tom; Jedrzejewski, Franck (2014). "Las damas de Kirkman, un diseño combinatorio". Mirando los números . págs. 37–55. doi :10.1007/978-3-0348-0554-4_4. ISBN978-3-0348-0553-7.
^ Zhou, Junling; Chang, Yanxun (2014). "Un nuevo resultado sobre el problema de Sylvester". Matemáticas discretas . 331 : 15–19. doi :10.1016/j.disc.2014.04.022.
^ Araya, Makoto y Harada, Masaaki. (2010). Diseños de sistemas Steiner mutuamente disjuntos S(5, 8, 24) y 5-(24, 12, 48). Electr. J. Comb.. 17.
^ abcde Conwell, George M. (1910). "El espacio tridimensional PG(3,2) y su grupo". Anales de Matemáticas . 11 (2): 60–76. doi :10.2307/1967582. JSTOR 1967582.
^ Banchero, Matías; Robledo, Franco; Romero, Pablo; Sartor, Pablo; Servetti, Camilo (2021). "Reagrupamiento ortogonal de máxima diversidad de estudiantes de MBA mediante una heurística GRASP/VND". Variable Neighborhood Search . Lecture Notes in Computer Science. Vol. 12559. págs. 58–70. doi :10.1007/978-3-030-69625-2_5. ISBN978-3-030-69624-5. Número de identificación del sujeto 232314621.
^ Van Dam, Edwin R.; Haemers, Willem H.; Peek, Maurice BM (2003). "Coberturas resolubles equitativas". Revista de diseños combinatorios . 11 (2): 113–123. doi : 10.1002/jcd.10024 . S2CID 120596961.
^ Bryant y Danziger 2011
^ McRobbie, Linda Rodríguez. "Las matemáticas alucinantes detrás de Spot It!, el querido juego de cartas familiar". Revista Smithsonian . Consultado el 1 de marzo de 2020 .
Referencias
Ahrens, W. (1901), Mathematische Unterhaltungen und Spiele , Leipzig: Teubner
Bryant, Darryn; Danziger, Peter (2011), "Sobre las factorizaciones bipartitas de K n − I {\displaystyle K_{n}-I} y el problema de Oberwolfach" (PDF) , Journal of Graph Theory , 68 (1): 22–37, doi :10.1002/jgt.20538, MR 2833961, S2CID 7478839
Cayley, A. (1850), "Sobre los arreglos triádicos de siete y quince cosas", Philosophical Magazine , 37 (247): 50–53, doi :10.1080/14786445008646550
Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2.ª ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
Cole, FN (1922), "Desfiles de Kirkman", Boletín de la Sociedad Matemática Americana , 28 (9): 435–437, doi : 10.1090/S0002-9904-1922-03599-9
Cummings, LD (1918), "Un artículo de Kirkman infravalorado", Boletín de la Sociedad Matemática Americana , 24 (7): 336–339, doi : 10.1090/S0002-9904-1918-03086-3
Dudeney, HE (1917), "Diversiones en matemáticas", Nature , 100 (2512), Nueva York: Dover: 302, Bibcode :1917Natur.100..302., doi :10.1038/100302a0, S2CID 10245524
Ray-Chaudhuri, DK; Wilson, RM (1971), "Solución del problema de la colegiala de Kirkman, en Combinatoria, Universidad de California, Los Ángeles, 1968 ", Actas de simposios sobre matemáticas puras , XIX , Providence, Rhode Island : American Mathematical Society: 187–203, doi :10.1090/pspum/019/9959, ISBN 978-0-8218-1419-2
