El problema de Kirkman sobre las colegialas

El problema de la colegiala de Kirkman es un problema combinatorio propuesto por Thomas Penington Kirkman en 1850 como Pregunta VI en The Lady's and Gentleman's Diary (una entretenida revista de matemáticas publicada entre 1841 y 1871). El reto dice:

Quince niñas de la escuela caminan tres seguidas durante siete días (todos los días), se requiere distribuirlas en cada caminata para que no haya dos niñas caminando en la misma fila ( Graham, Grötschel, Lovász 1995 ).

Solución

Si las chicas están numeradas del 0 al 14, la siguiente distribución será una de las soluciones [1] :

domingo
_ 		lunes
_ 		martes miércoles jueves Viernes sábado
 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

La solución a este problema es un ejemplo de un sistema triple de Kirkman [2] ; esto significa que es un sistema triple de Steiner que tiene paralelismo , es decir, tiene una partición de los bloques del sistema triple en clases paralelas, que son particiones de puntos en bloques que no se cortan.

Hay siete soluciones no isomórficas al problema de las colegialas [3] . Dos de ellos pueden visualizarse como relaciones entre un tetraedro y sus vértices, aristas y caras [4] . A continuación se proporciona un enfoque que utiliza geometría proyectiva 3D sobre GF(2) .

Resolviendo trillizos XOR

Si las chicas se vuelven a numerar con números binarios de 0001 a 1111, la siguiente distribución es una solución tal que para tres chicas que componen el grupo, XOR bit a bit de los dos números produce el tercero:

domingo
_ 		lunes
_ 		martes miércoles jueves Viernes sábado
0001, 0010, 0011 0001, 0100, 0101 0001, 0110, 0111 0001, 1000, 1001 0001, 1010, 1011 0001, 1100, 1101 0001, 1110, 1111
0100, 1000, 1100 0010, 1000, 1010 0010, 1001, 1011 0010, 1100, 1110 0010, 1101, 1111 0010, 0100, 0110 0010, 0101, 0111
0101, 1010, 1111 0011, 1101, 1110 0011, 1100, 1111 0011, 0101, 0110 0011, 0100, 0111 0011, 1001, 1010 0011, 1000, 1011
0110, 1011, 1101 0110, 1001, 1111 0100, 1010, 1110 0100, 1011, 1111 0101, 1001, 1100 0101, 1011, 1110 0100, 1001, 1101
0111, 1001, 1110 0111, 1011, 1100 0101, 1000, 1101 0111, 1010, 1101 0110, 1000, 1110 0111, 1000, 1111 0110, 1010, 1100

Esta solución tiene una interpretación geométrica relacionada con la geometría de Galois y PG(3,2) . Toma un tetraedro y vuelve a numerar sus vértices como 0001, 0010, 0100 y 1000. Vamos a volver a numerar los seis centros de las aristas como extremos XOR de la arista. Asignamos etiquetas iguales al XOR de tres vértices a los cuatro centros de las caras, y al centro del cuerpo etiquetamos 1111. Entonces hay 35 triples y la solución XOR corresponde exactamente a 35 PG(3,2) directos.

Historia

La primera solución fue publicada por Arthur Cayley [5] . Rápidamente fue seguida por la propia solución de Kirkman [6] , que se presentó como un caso especial de su arreglo combinatorio publicado tres años antes [7] . D. D. Sylvester también investigó el problema y terminó afirmando que Kirkman le robó la idea. El acertijo apareció en varios libros matemáticos entretenidos a principios de siglo por Lucas [8] , Rose Ball [9] , Aarens [10] y Dudeney [11] .

Kirkman explicó a menudo que su extenso artículo ( Kirkman 1847 ) estaba completamente inspirado por el gran interés en el problema [12] .

Geometría de Galois

En 1910 el problema fue considerado por George Conwell con la ayuda de la geometría de Galois [13] .

Se utilizó un campo de Galois GF(2) de dos elementos con cuatro coordenadas homogéneas para formar un PG(3,2) de 15 puntos, 3 puntos en una recta, 7 puntos y 7 rectas en un plano. El plano se puede considerar como un cuadrilátero completo con líneas a través de sus puntos diagonales. Cada punto se encuentra en 7 líneas y hay 35 líneas en total.

Los espacios de línea PG(3,2) están definidos por sus coordenadas Plucker en PG(5,2) con 63 puntos, 35 de los cuales representan líneas en PG(3,2). Estos 35 puntos forman la superficie S , conocida como la cuádrica de Klein . Para cada uno de los 28 puntos que no están en S , hay 6 líneas que pasan por este punto que no intersecan S [14] .

Como el número de días en una semana, siete juega un papel importante para decidir:

Si se eligen dos puntos A y B en la línea ABC, cada una de las otras cinco líneas que pasan por A corta solo una de las cinco líneas que pasan por B. Los cinco puntos resultantes de la intersección de estos pares, junto con los dos puntos A y B , llamamos "siete" ( Conwell 1910 , 68).

Siete se define por sus dos puntos. Cada uno de los 28 puntos fuera de S se encuentra en dos sietes. Hay 8 sietes. El grupo lineal proyectivo PGL(3,2) es isomorfo al grupo alterno en 8 sietes [15] .

El problema de la colegiala consiste en encontrar siete líneas que no se intersecan en un espacio de 5 dimensiones de modo que dos líneas cualesquiera siempre tengan un siete común [16] .

Generalización

El problema se puede generalizar a las alumnas, donde debería ser un número igual al producto de un número impar por 3 (es decir, ) caminando en tríos de días con la condición, de nuevo, de que ningún par de niñas caminen en la misma fila dos veces [17] . La solución a esta generalización es un sistema triple de Steiner S(2, 3, 6 t + 3) con paralelismo (es decir, un sistema en el que cada 6 t + 3 elementos aparecen exactamente una vez en cada bloque de conjuntos de 3 elementos), conocido como el sistema Kirkman [1] . Esta es la generalización del problema que Kirkman discutió originalmente, y el famoso caso especial que discutió más tarde [7] . La solución completa del caso general fue publicada por D.K. Rei-Chadhuri y R.M. Wilson en 1968 [18] , aunque el problema ya había sido resuelto por el matemático chino Liu Jaksi (陆家羲) en 1965 [19] , pero en ese momento el la solución aún no se había publicado [20] .

Se consideraron varias variantes de la tarea principal. Alan Hartman resolvió este tipo de problema con el requisito de que tres no caminen en filas de cuatro más de una vez [21] usando el sistema de cuádruples de Steiner.

Recientemente ha salido a la luz un problema similar, conocido como el “problema del campo de golf”, en el que hay 32 golfistas que quieren jugar cada día con diferentes personas en grupos de 4 durante 10 días consecutivos.

Dado que se trata de una estrategia de reagrupación en la que todos los grupos son ortogonales, este proceso de formación de pequeños grupos a partir de un grupo grande, en el que dos personas no pertenecen a más de un grupo al mismo tiempo, puede considerarse una reagrupación ortogonal. Sin embargo, este término rara vez se usa y se puede considerar que no existe un término generalmente aceptado para este proceso.

El problema de Oberwolfach de descomponer un gráfico completo en copias separadas de un gráfico de 2 regulares dado también generaliza el problema de Kirkman sobre las colegialas. El problema de Kirkman es un caso especial del problema de Oberwolfach, en el que un gráfico de 2 regulares consta de cinco triángulos disjuntos [22] .

Otras aplicaciones

Notas

  1. ↑ 1 2 Rouse Ball, Coxeter, 1987 , p. 287-289.
  2. ↑ Weisstein, Problema de la colegiala de Eric W. Kirkman  en el sitio web Wolfram MathWorld .
  3. ↑ Cole, 1922 , pág. 435–437.
  4. ↑ Falcone, Pavone, 2011 , p. 887–900.
  5. ↑ Cayley, 1850 , pág. 50–53.
  6. ↑ Kirkman, 1850 .
  7. ↑ 12 Kirkman , 1847 .
  8. ↑ Lucas, 1883 , pág. 183–188.
  9. ↑ Rouse Ball, 1892 .
  10. ↑ Ahrens, 1901 .
  11. ↑ Dudeney, 1917 .
  12. ↑ Cummings, 1918 .
  13. ↑ Conwell, 1910 , pág. 60–76.
  14. ↑ Conwell, 1910 , pág. 67.
  15. ↑ Conwell, 1910 , pág. 69.
  16. ↑ Conwell, 1910 , pág. 74.
  17. ↑ Tarakanov, 1985 , pág. 109.
  18. ↑ Ray-Chaudhuri, Wilson, 1971 .
  19. ↑ Lu, 1990 .
  20. ↑ Colbourn, Dinitz, 2007 , pág. 13
  21. ↑ Hartmann, 1980 .
  22. ↑ Bryant, Danziger, 2011 .

Literatura

Enlaces