Problema de les colegialas de Kirkman

Problema de les colegialas de Kirkman

Archiu:Caps block 0 Diary CoverAndPage.jpg

Publicació original del problema

El problema de les colegialas de Kirkman és una qüestió matemàtica de caràcter combinatori proposta per Thomas Kirkman en 1850 en la publicació "The Lady's and Gentleman's Diary" (El Diari de Dames i Cavallers) (Consulta VI; pàgina 48). El problema diu:

Quinze alumnes ixen formades de tres en fondo durant sèt dies seguits: es requerix formar-les cada dia de manera que en terminar la semana no hi haja hagut dos d'elles que hagen caminat juntes (o siga, en la mateixa fila) més d'una volta.

Solucions

Una solució a este problema és un eixemple d'un sistema triple de Kirkman, que es definix com un sistema triple de Steiner que posseïx un paralelisme, és dir, una partició dels blocs del sistema triple en classes paraleles que són a la seua volta particions dels punts en blocs disjuntos. Els sistemes de Steiner que posseïxen un paralelisme també es denominen resolubles.

Hi ha exactament sèt solucions no isomorfas per al problema de les alumnes, com les va enumerar originalment Frank Nelson Cole en el seu artícul titulat Kirkman Parades de 1922. Les sèt solucions es resumixen en la següent taula, en la que es representen a les 15 chiquetes per mig de les lletres de la A a l'O:

Classe de solució	Grup d'automorfisme	Dia 1	Dia 2	Dia 3	Dia 4	Dia 5	Dia 6	Dia 7
Solució I	Orde 168, generat per (A K G I I L B)(C H M J N O D) i (A M L K O C D)(B H N G I I J). Relacionat en 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ó II	Orde 168, generat per (A B I M F C J)(D N H K O L I) i (A J M I B F C)(D H G N K I O). Relacionat en 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ó III	Orde 24, generat per (A H I)(B O K)(C F I)(D J L)(G N M) i (A J B M)(D L I 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ó IV	Orde 24, generat per (A J M)(C F I)(D I K)(H O L) i (A L B O)(C I)(D K I 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ó V	Grup tetraèdric d'orde 12, generat per (A L)(B G)(I O)(F J)(H K)(I M) i (A B C)(D L G)(F J I)(I 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ó VI	Grup tetraèdric d'orde 12, generat per (A L)(B G)(I O)(H K)(F J)(I M) i (A B C)(D L G)(I 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ó VII	Orde 21, generat per (A B L C G D N)(I H K I O J F) i (B G L)(C D N)(I 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 d'automorfismes per a cada solució i de la definició de grup d'automorfismes, el número total de solucions incloses les solucions isomòrfiques és, per tant,:

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

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

$=404,756,352,000$

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

Història

El problema té una llarga i prolija història. Esta secció es basa en el treball recopilatorio realisat en diferents moments per Robin Wilson i per Louise Duffield Cummings. La seua cronologia és la següent:

• En 1844, Wesley Woolhouse, editor per llavors de The Lady's and Gentleman's Diary, va formular la següent pregunta general: "Determinar el número de combinacions que es poden fer en n símbols, agrupant p símbols en cada combinació; en la següent llimitació: que cap combinació de q símbols, que poden aparéixer en qualsevol d'elles, es repetirà en cap atra." Solament es varen rebre dos respostes, una incorrecta i l'atra responent correctament la pregunta en $\frac{n!}{q!(n-q)!}÷\frac{p!}{q!(p-q)!}$. Com no es va demanar res més que el número de combinacions, no es va rebre res sobre les condicions de n, p o q que fan possible conseguir tal solució.

• En 1846, Woolhouse va preguntar: "¿Quantes tríades poden formar-se a partir de n símbols, de modo que cap parell de símbols quede comprés més d'una volta entre elles?". Açò equival a repetir la seua pregunta de 1844 en els valores p = 3 i q = 2.

• En 1847, a l'edat de 41 anys, Thomas Kirkman va publicar el seu artícul titulat Sobre un problema de combinacions,Plantilla:Harv que descrivia i resolia exhaustivament el problema de la construcció de sistemes triples d'orde n a on n = 1 o 3 (mod 6). També va considerar atres valors de n, encara que no va poder generalisar el seu plantejament. Va donar dos seqüències diferents de sistemes triples, una per a n = 7, 15, 19, 27, etc., i una atra per a n = 9, 13, 25, etc. Utilisant estes proposicions, va demostrar que existixen sistemes triples per a "tots" els valors de n = 1 o 3 (mod 6) (no necessàriament resolubles, pero sí sistemes triples en general). També va descriure en detalle els sistemes triples resolubles en eixe artícul, particularment per a n = 9 i 15; Els sistemes triples resolubles ara es coneixen com a sistemes triples de Kirkman. No va poder establir de manera concloent para quina atres valors de n existirien sistemes triples resolubles, problema que no es resoldria fins a la década de 1960 (vore més avall).

• En 1850, Kirkman va plantejar el problema de les 15 colegialas, que es tornaria molt més famós que l'artícul de 1847 que ya havia escrit. Es varen rebre vàries solucions. El propi Kirkman va donar una solució que després es descobriria que era isomorfa a la Solució I anterior. Kirkman va afirmar que era l'única solució possible, pero esta afirmació era incorrecta. Més alvance es va descobrir que la solució d'Arthur Cayley era isomorfa a la Solució II. Abdós solucions podien integrar-se en PG(3,2), encara que eixa geometria no es coneixia en eixe moment. No obstant, en publicar les seues solucions al problema de les escolars, Kirkman es va oblidar de remetre als llectors al seu propi artícul de 1847, i esta omissió tindria greus conseqüències per a l'invenció i la prioritat, com es veu a continuació.

• També en 1850, James Joseph Sylvester va preguntar si podria haver 13 solucions diferents al problema de les 15 alumnes que usaren totes les $(\genfrac{}{}{0ex}{}{15}{3})=455$ tripletas possibles una volta en total, observant que $455=13\times 35$. En atres paraules, ¿és possible que les chiquetes marchen tots els dies durant 13 semanes, de modo que cada dos chiquetes marchen juntes exactament una volta per semana i cada tres chiquetes marchen juntes exactament una volta en el determini de 13 semanes? Este problema era molt més difícil i RHF Denniston finalment proporcionaria una solució utilisant un computador en 1974 (vore més avall).

• En 1852, Robert Richard Anstice va proporcionar una solució cíclica, formada per mig de la construcció de les cinc tripletas del primer dia per a que foren 0Gg, AbC, aDE, cef, BdF en els 15 símbols 0ABCDEFGabcdefg i després canviant cíclicamente cada dia subsegüent per una lletra, deixant 0 sense canvis (les mayúscules permaneixen en mayúscula i les minúscules permaneixen en minúscula). Si les quatre tripletas sense l'element 0 (AbC, aDE, cef, BdF) es prenen i es convertixen de mayúscules a minúscules (abc, ade, cef, bdf) formen lo que més vesprada es cridaria la Configuració de Pasch, que cobraria importància en les tècniques d'eliminació de solucions isomorfas en el XX.

• En 1853, Jakob Steiner, completament ignorant de l'artícul de Kirkman de 1847, va publicar el seu artícul titulat Combinatorische Aufgabe, que reintroducía el concepte de sistemes triples, pero no va mencionar la resolubilidad en classes paraleles separades. Steiner va senyalar que és necessari que n siga 1 o 3 (mod 6), pero va deixar oberta la pregunta d'en quines condicions és possible, sense saber que Kirkman ya havia resolt eixa qüestió en 1847. Com este artícul va ser més àmpliament llegit pel establishment matemàtic europeu, els sistemes triples es varen conéixer més tarde com sistemes triples de Steiner.

• En 1859, Michel Reiss va respondre a les preguntes plantejades per Steiner, utilisant tant una metodologia com una notació tan similar al treball de Kirkman de 1847 (sense reconéixer a Kirkman), que autors posteriors com Louise Cummings ho han considerat un plagi. El propi Kirkman va expressar la seua amargura.

• En 1860, Benjamin Peirce va unificar vàries solucions dispars presentades fins a llavors i va demostrar que hi havia tres possibles estructures de solució cíclica, una corresponent al treball de Anstice, una atra basada en la solució de Kirkman i una atra en la de Cayley.

• En 1861, James Joseph Sylvester va revisar el problema i va tractar d'afirmar que "ell" ho havia inventat i que les seues conferències en Cambridge havien segut la font del treball de Kirkman. Kirkman ràpidament va rebujar estes asseveracions, afirmant que quan va escriure els seus artículs mai havia estat en Cambridge ni havia sentit parlar del treball de Sylvester. Esta disputa de prioritat va provocar una disputa entre Sylvester i Kirkman.

• En 1861-1862, Kirkman va sostindre una atra disputa en Arthur Cayley per un assunt distint (la decisió de Cayley de no publicar una série d'artículs de Kirkman sobre teoria de grups i poliedres, que li varen costar a Kirkman el reconeiximent de la comunitat matemàtica en Europa), lo que va contribuir encara més a la seua condició de marginat pel establishment matemàtic. El seu complet artícul de 1847 en particular va ser oblidat, i molts autors posteriors varen donar crèdit a Steiner o a Reiss, sense conéixer la verdadera història.

• La popularitat del problema de les colegialas en sí no es va vore afectada pels conflictes acadèmics de Kirkman, i a finals de el XIX i principis de el XX, el rompecabezas va aparéixer en varis llibres de matemàtiques recreatives d'Édouard Lucas, W. W. Rouse Ball, Wilhelm Ahrens, i Henry Dudeney. Durant la seua vida, Kirkman es queixaria de que el seu sério treball matemàtic va quedar eclipsat per la popularitat del problema de les escolars. Kirkman va morir en 1895.

• En 1918, Louise Duffield Cummings va tornar a cridar l'atenció sobre el sério treball matemàtic de Kirkman en un artícul titulat "Un artícul de Kirkman infravalorado", que analisava l'història primerenca del problema i corregia l'omissió històrica.

• Aproximadament al mateix temps, Cummings estava treballant en Frank Nelson Cole i Henry Seely White en sistemes triples. Açò va culminar en el seu famós i àmpliament citat artícul de 1919 Classificació completa de sistemes de tríades en 15 elements, que va ser el primer artícul en presentar les 80 solucions del sistema triple de Steiner de tamany 15, i en el que també s'incloïen atres sistemes tant resolubles com no resolubles.

• En 1922, Cole va publicar el seu artícul Kirkman Parades que enumerava per primera volta les sèt solucions no isomorfas al problema de les 15 colegialas, responent aixina a una antiga pregunta sense resoldre des de la década de 1850. Les sèt solucions de Kirkman corresponen a quatre sistemes de Steiner diferents quan s'elimina com a restricció la resolubilidad en classes paraleles. Tres dels sistemes de Steiner tenen dos formes possibles de separar-se en classes paraleles, és dir, dos solucions de Kirkman cada u, mentres que el quarto té solament una, lo que dona sèt solucions de Kirkman en total.

• En la década de 1960, es va demostrar que els sistemes triples de Kirkman existixen per a "tots" els órdens de n = 3 (mod 6). Açò va ser provat per primera volta per Lu Jiaxi (陆家羲) en 1965, i ho va enviar a "Acta Mathematica Sinica", pero la revista va pensar erròneament que el problema ya s'havia resolt anteriorment i va rebujar el seu artícul en 1966, lo que després es va descobrir que era un error greu. Les seues contribucions acadèmiques posteriors varen ser interrompudes per la Revolució Cultural i rebujades novament. En 1968, D. K. Ray-Chaudhuri i R. M. Wilson varen demostrar la teorema generalisada de forma independent.

• En 1974, RHF Denniston va resoldre el problema de Sylvester en construir 13 solucions de Kirkman disjuntas i usar-les per a cobrir les 455 tripletas que es poden formar en les 15 chiques. La seua solució s'analisa a continuació.

Vore també

• Estratègia Aprenentage cooperatiu per a aumentar l'interacció dins de l'ensenyança en l'aula.
• Joc de cartes Dobble
• Sopar progressiu; disseny de colocació de comensals
• Events de contacte ràpit
• Competicions deportives
• Combinatòria
• R M Wilson
• Dijen K. Ray-Chaudhuri
• Matemàtica discreta

Bibliografia

• (1901).«Mathematische Unterhaltungen und Spiele».Teubner.Leipzig:
• (2011).«On bipartite 2-factorizations of $K_n-I$ and the Oberwolfach problem».Journal of Graph Theory.68(1)

22–37.doi:10.1002/jgt.20538.

• (1850).«On the triadic arrangements of seven and fifteen things».Philosophical Magazine.37(247)

50–53.doi:10.1080/14786445008646550.

• (2007).«Handbook of Combinatorial Designs».Chapman & Hall/ CRC.Boca Raton:
• (1922).«Kirkman parades».Bulletin of the American Mathematical Society.28(9)

435–437.doi:10.1090/S0002-9904-1922-03599-9.

• (1918).«An undervalued Kirkman paper».Bulletin of the American Mathematical Society.24(7)

336–339.doi:10.1090/S0002-9904-1918-03086-3.

• (1917).«Amusements in Mathematics».Nature.Dover.100(2512)doi:10.1038/100302a0.
  • «Amusements in Mathematics».Dover.Mineola (Nova York):

• (1995).«Handbook of Combinatorics, Volume 2».The MIT Press.Cambridge (Massachusetts):
• (1980).«Kirkman's trombone player problem».Ars Combinatòria.10

19–26.

• (1990).«Collected Works of Lu Jiaxi on Combinatorial Designs».Inner Mongòlia People's Press.Huhhot:
• (1847).«On a Problem in Combinations».The Cambridge and Dublin Mathematical Journal.Macmillan, Barclay, and Macmillan.II

191–204.

• (1850).«Note on an unanswered prize question».The Cambridge and Dublin Mathematical Journal.Macmillan, Barclay and Macmillan.5

255–262.

• (1883).«Récréations Mathématiques».Gauthier-Villars.Paris:2

183–188.

• (1971).«Solution of Kirkman's schoolgirl problem, in Combinatorics, University of Califòrnia, Los Angeles, 1968».Proceedings of Symposia in Pure Mathematics.American Mathematical Society.XIX

187–203.doi:10.1090/pspum/019/9959.

• (1892).«Mathematical Recreations and Essays».Macmillan.
  • (1987).«Mathematical Recreations and Essays».Dover.

287–289.