El problema de la colegiala de Kirkman es un problema de combinatoria propuesto por el reverendo Thomas Penyngton Kirkman en 1850 como Consulta VI en The Lady's and Gentleman's Diary (pág. 48). El problema dice:
Quince señoritas en una escuela caminan de tres en fila durante siete días seguidos: es necesario organizarlos todos los días para que no haya dos que caminen dos veces al mismo tiempo. [1]
Solución
Si las niñas están numeradas del 0 al 14, la siguiente disposición es una solución: [2]
Sol. | Lun. | Mar. | Casarse. | Jueves | Vie. | Se sentó. |
---|---|---|---|---|---|---|
0, 5, 10 | 0, 1, 4 | 1, 2, 5 | 4, 5, 8 | 2, 4, 10 | 4, 6, 12 | 10, 12, 3 |
1, 6, 11 | 2, 3, 6 | 3, 4, 7 | 6, 7, 10 | 3, 5, 11 | 5, 7, 13 | 11, 13, 4 |
2, 7, 12 | 7, 8, 11 | 8, 9, 12 | 11, 12, 0 | 6, 8, 14 | 8, 10, 1 | 14, 1, 7 |
3, 8, 13 | 9, 10, 13 | 10, 11, 14 | 13, 14, 2 | 7, 9, 0 | 9, 11, 2 | 0, 2, 8 |
4, 9, 14 | 12, 14, 5 | 13, 0, 6 | 1, 3, 9 | 12, 13, 1 | 14, 0, 3 | 5, 6, 9 |
Una solución a este problema es un ejemplo de un sistema triple Kirkman , [3] que es un sistema triple 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.
Hay siete soluciones no isomórficas para el problema de las alumnas. [4] Dos de estos pueden visualizarse como relaciones entre un tetraedro y sus vértices, aristas y caras. [5] A continuación se da un enfoque que utiliza geometría proyectiva de tres dimensiones sobre GF (2) .
Historia
La primera solución fue publicada por Arthur Cayley . [6] Esto fue seguido poco después por la propia solución de Kirkman [7], que se presentó como un caso especial de sus consideraciones sobre los arreglos combinatorios publicados tres años antes. [8] JJ Sylvester también investigó el problema y terminó declarando que Kirkman le robó la idea. El rompecabezas apareció en varios libros de matemáticas recreativas a principios de siglo de Lucas, [9] Rouse Ball, [10] Ahrens, [11] y Dudeney. [12]
Kirkman se quejaba a menudo del hecho de que su importante artículo ( Kirkman 1847 ) estaba totalmente eclipsado por el interés popular por el problema de las alumnas. [13]
Geometría de Galois
En 1910, George Conwell abordó el problema utilizando la geometría de Galois . [14]
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 a 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 cuádrica de Klein . Para cada uno de los 28 puntos del S hay 6 líneas a través de ella que no lo hacen de intersección S . [14] : 67
Como hay siete días en una semana, la heptada es una parte importante de la solución:
Cuando se eligen dos puntos como A y B de la línea ABC, cada una de las otras cinco líneas que pasan por A se encuentra con solo una de las otras cinco líneas que pasan por B. Los cinco puntos determinados por las intersecciones de estos pares de líneas, junto con los dos puntos A y B los denominamos "heptada". [14] : 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 el grupo alterno en las 8 heptadas. [14] : 69
El problema de la colegiala consiste en encontrar siete líneas en el espacio de cinco que no se crucen y de manera que dos líneas siempre tengan una heptada en común. [14] : 74
Untables y envasado
En PG (3,2), una división de los puntos en líneas se llama extensión , y una división de las líneas en extensiones se llama empaquetamiento o paralelismo . [15] : 66 Hay 56 para untar y 240 envases. Cuando Hirschfeld consideró el problema en su Finite Projective Spaces of Three Dimensions (1985), notó que algunas soluciones corresponden a empaques de PG (3,2), esencialmente como lo describió Conwell anteriormente, [15] : 91 y presentó dos de ellos. [15] : 75
Generalización
El problema se puede generalizar a chicas, donde debe ser un múltiplo impar de 3 (es decir ), caminando en trillizos para días, con el requisito, nuevamente, de que ningún par de niñas caminen en la misma fila dos veces. La solución a esta generalización es un sistema triple 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 3 elementos conjuntos), conocido como sistema triple de Kirkman . [2] Es esta generalización del problema lo que Kirkman discutió primero, mientras que el famoso caso especialsolo se propuso más tarde. [8] Una solución completa al caso general fue publicada por DK Ray-Chaudhuri y RM Wilson en 1968, [16] aunque ya había sido resuelta por Lu Jiaxi ( chino :陆 家 羲) en 1965, [17] pero no había sido publicado en ese momento. [18]
Pueden considerarse 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 [19] utilizando sistemas cuádruples Steiner.
Más recientemente, ha ganado interés un problema similar conocido como el 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. Sin embargo, este término actualmente no se usa comúnmente y la evidencia sugiere que no existe un nombre común para el proceso.
El problema de los revestimientos resolubles considera el chicas, caso de grupos donde cada pareja de niñas debe estar en el mismo grupo en algún momento, pero queremos usar la menor cantidad de días posible. Esto se puede usar, por ejemplo, para programar un plan de mesa giratoria, en el que cada par de invitados debe estar en algún momento en la misma mesa. [20]
El problema de Oberwolfach , de descomponer un grafo completo en copias de bordes separados de un grafo regular de 2 dado , también generaliza el problema de colegiala de Kirkman. El problema de Kirkman es el caso especial del problema de Oberwolfach en el que la gráfica regular 2 consta de cinco triángulos disjuntos. [21]
Otras aplicaciones
- Estrategia de aprendizaje cooperativo para aumentar la interacción dentro de la enseñanza en el aula
- Juego de cartas Dobble [22]
- Diseños progresivos para cenas
- Eventos de Speed Networking
- Competiciones deportivas
- Combinatoria
- RM Wilson
- Dijen K. Ray-Chaudhuri
- Matemáticas discretas
Notas
- ^ Graham, Grötschel y Lovász 1995
- ^ a b Ball y Coxeter 1987 , págs. 287-289
- ^ Weisstein, Eric W. "Problema de colegiala de Kirkman" . MathWorld .
- ^ Cole, FW (1922), "Kirkman Parades", Bulletin of the American Mathematical Society , 28 (9): 435–437, doi : 10.1090 / S0002-9904-1922-03599-9
- ^ Falcone, Giovanni; Pavone, Marco (2011), "El tetraedro de Kirkman y el problema de las quince colegialas", American Mathematical Monthly , 118 (10): 887–900, doi : 10.4169 / amer.math.monthly.118.10.887
- ^ Cayley, A. (1850), "Sobre los arreglos triádicos de siete y quince cosas" , Philosophical Magazine , 37 (247): 50–53, doi : 10.1080 / 14786445008646550
- ^ Kirkman 1850
- ^ a b Kirkman 1847
- ^ Lucas 1883 , págs. 183-188
- ↑ Rouse Ball 1892
- ^ Ahrens 1901
- ↑ Dudeney, 1917
- ↑ Cummings, 1918
- ^ a b c d e Conwell, George M. (1910). "El PG de 3 espacios (3,2) y su Grupo". Annals of Mathematics . 11 (2): 60–76. doi : 10.2307 / 1967582 . JSTOR 1967582 .
- ^ a b c Hirschfeld, JWP (1985), Espacios proyectivos finitos de tres dimensiones , Oxford University Press , ISBN 0-19-853536-8
- ^ Ray-Chaudhuri y Wilson 1971
- ^ Lu 1990
- ^ Colbourn y Dinitz 2007 , p. 13
- ↑ Hartman, 1980
- ^ van Dam, ER, Haemers, WH y Peek, MBM (2003). Revestimientos equitativos resolubles. Revista de diseños combinatorios, 11 (2), 113-123.
- ^ Bryant y Danziger 2011
- ^ McRobbie, Linda Rodríguez. "¡Las matemáticas alucinantes detrás de Spot It !, el amado juego de cartas de la familia" . 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 dos factorizaciones bipartitas de K norte - 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
- Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2a ed.), Boca Raton: Chapman & Hall / CRC, ISBN 978-1-58488-506-1
- Cummings, LD (1918), "Un artículo de Kirkman infravalorado", Boletín de la American Mathematical Society , 24 (7): 336–339, doi : 10.1090 / S0002-9904-1918-03086-3
- Dudeney, HE (1917), Diversiones en matemáticas , Nueva York: Dover
- Dudeney, HE (1958), Diversiones en matemáticas , Matemáticas recreativas de Dover, Mineola, Nueva York : Dover, ISBN 978-0-486-20473-4
- Graham, Ronald L .; Grötschel, Martin ; Lovász, László (1995), Handbook of Combinatorics, Volumen 2 , Cambridge, MA : The MIT Press, ISBN 0-262-07171-1
- Hartman, Alan (1980), "El problema del trombonista de Kirkman", Ars Combinatoria , 10 : 19-26
- Lu, Jiaxi (1990), Obras completas de Lu Jiaxi sobre diseños combinatorios , Huhhot: Inner Mongolia People's Press
- Kirkman, Thomas P. (1847), "Sobre un problema de combinaciones" , The Cambridge and Dublin Mathematical Journal , Macmillan, Barclay y Macmillan, II : 191-204
- Kirkman, Thomas P. (1850), "Nota sobre una pregunta de premio sin respuesta" , The Cambridge and Dublin Mathematical Journal , Macmillan, Barclay y Macmillan, 5 : 255-262
- Lucas, É. (1883), Récréations Mathématiques , 2 , París: Gauthier-Villars, págs. 183–188
- Ray-Chaudhuri, DK; Wilson, RM (1971), "Solución del problema de colegiala de Kirkman, en Combinatoria, Universidad de California, Los Ángeles, 1968 ", Actas de simposios en matemáticas puras , Providence, Rhode Island : American Mathematical Society, XIX : 187-203, doi : 10.1090 / pspum / 019/9959 , ISBN 978-0-8218-1419-2
- Rouse Ball, WW (1892), Recreaciones y ensayos matemáticos , Londres: Macmillan
- Ball, WW Rouse ; Coxeter, HSM (1987) [1974], Recreaciones y ensayos matemáticos (13ª ed.), Dover, págs. 287–289, ISBN 0-486-25357-0
enlaces externos
- Weisstein, Eric W. "Problema de colegiala de Kirkman" . MathWorld .
- Klarreich, Erica (9 de junio de 2015), "Un dilema de diseño resuelto, menos diseños". , Revista Quanta