Kirkman problem om skolepiger

Kirkman's Schoolgirl Problem er et kombinatorisk problem foreslået af Thomas Penington Kirkman i 1850 som spørgsmål VI i The Lady's and Gentleman's Diary (et underholdende matematikmagasin udgivet mellem 1841 og 1871). Udfordringen siger:

Femten unge piger på skolen går tre i træk i syv dage (hver dag), det er påkrævet at fordele dem for hver gåtur, så der ikke går to piger på samme række ( Graham, Grötschel, Lovász 1995 ).

Løsning

Hvis pigerne er nummereret fra 0 til 14, vil følgende fordeling være en af ​​løsningerne [1] :

søndag
_ 		mandag
_ 		tirsdag onsdag torsdag Fredag lørdag
 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

Løsningen på dette problem er et eksempel på et Kirkman triple system [2] ; dette betyder, at det er et Steiner-tredobbelt system , der har parallelitet , det vil sige, at det har en opdeling af tredobbeltsystemets blokke i parallelle klasser, som er opdelinger af punkter i ikke-skærende blokke.

Der er syv ikke -isomorfe løsninger på problemet med skolepiger [3] . To af dem kan visualiseres som forhold mellem et tetraeder og dets hjørner, kanter og flader [4] . En tilgang, der bruger 3D-projektiv geometri over GF(2) er givet nedenfor.

Løsning af XOR-tripletter

Hvis pigerne omnummereres med binære tal fra 0001 til 1111, er følgende fordeling en løsning, således at for alle tre piger, der udgør gruppen, giver bitvis XOR af de to tal det tredje:

søndag
_ 		mandag
_ 		tirsdag onsdag torsdag Fredag lørdag
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

Denne løsning har en geometrisk fortolkning relateret til Galois geometri og PG(3,2) . Tag et tetraeder og omnummerer dets hjørner til 0001, 0010, 0100 og 1000. Lad os omnummerere de seks kantcentre som XOR-ender af kanten. Vi tildeler mærker svarende til XOR af tre spidser til fire ansigtscentre og mærker 1111 til midten af ​​kroppen. Derefter er der 35 tripler, og XOR-løsningen svarer til nøjagtigt 35 direkte PG(3,2).

Historie

Den første løsning blev udgivet af Arthur Cayley [5] . Den blev hurtigt fulgt op af Kirkmans egen løsning [6] , som blev givet som et særligt tilfælde af hans kombinatoriske arrangement offentliggjort tre år tidligere [7] . D. D. Sylvester undersøgte også problemet og endte med at sige, at Kirkman stjal ideen fra ham. Puslespillet dukkede op i flere underholdende matematiske bøger ved århundredeskiftet af Lucas [8] , Rose Ball [9] , Aarens [10] og Dudeney [11] .

Kirkman forklarede ofte, at hans lange papir ( Kirkman 1847 ) var fuldstændig inspireret af den store interesse for problemet [12] .

Galois geometri

I 1910 blev problemet overvejet af George Conwell ved hjælp af Galois geometri [13] .

Et Galois-felt GF(2) med to elementer blev brugt med fire homogene koordinater til at danne en PG(3,2) med 15 punkter, 3 punkter på en linje, 7 punkter og 7 linjer på en plan. Flyet kan betragtes som en komplet firkant med linjer gennem sine diagonale punkter. Hvert punkt ligger på 7 linjer, og der er 35 linjer i alt.

Linjerummene PG(3,2) er defineret af deres Plucker-koordinater i PG(5,2) med 63 punkter, hvoraf 35 repræsenterer linjer i PG(3,2). Disse 35 punkter danner overfladen S , kendt som Klein quadric . For hvert af de 28 punkter, der ikke er på S , er der 6 linjer gennem dette punkt, som ikke skærer S [14] .

Som antallet af dage i en uge, spiller syv en vigtig rolle i beslutningen:

Hvis der vælges to punkter A og B på linje ABC, skærer hver af de fem andre linjer gennem A kun én af de fem linjer, der går gennem B. De fem punkter, der er resultatet af skæringen af ​​disse par, sammen med de to punkter A og B kalder vi "syv" ( Conwell 1910 , 68).

Syv er defineret ved sine to punkter. Hvert af de 28 punkter uden for S ligger på to syvere. Der er 8 syvere. Den projektive lineære gruppe PGL(3,2) er isomorf til den alternerende gruppe på 8 syvere [15] .

Skolepigeproblemet består i at finde syv ikke-skærende linjer i et 5-dimensionelt rum, således at alle to linjer altid har en fælles syv [16] .

Generalisering

Problemet kan generaliseres til kvindelige studerende, hvor det skal være et tal svarende til produktet af et ulige tal med 3 (dvs. ) gående i trillinger af dage med den betingelse, igen, at ingen piger går i samme række to gange [17] . Løsningen på denne generalisering er et Steiner-tredobbelt system S(2, 3, 6 t + 3) med parallelisme (det vil sige et system, hvor hver 6. t + 3 elementer optræder nøjagtigt én gang i hver blok af 3-elementsæt), kendt som Kirkman-systemet [1] . Dette er generaliseringen af ​​det problem, som Kirkman oprindeligt diskuterede, og det berømte specielle tilfælde, han diskuterede senere [7] . Den fuldstændige løsning af den generelle sag blev offentliggjort af D.K. Rei-Chadhuri og R.M. Wilson i 1968 [18] , selvom problemet allerede var løst af den kinesiske matematiker Liu Jaksi (陆家羲) i 1965 [19] , men på det tidspunkt løsningen blev stadig ikke offentliggjort [20] .

Flere varianter af hovedopgaven blev overvejet. Alan Hartman løste denne type problemer med kravet om, at ingen tre skulle gå i rækker af fire mere end én gang [21] ved at bruge Steiners system med firdobler.

For nylig er et lignende problem dukket op, kendt som "golfbaneproblemet", hvor der er 32 golfspillere, der hver dag ønsker at spille forskellige mennesker i grupper på 4 i 10 sammenhængende dage.

Da dette er en omgrupperingsstrategi, hvor alle grupper er ortogonale, kan denne proces med at danne små grupper fra en stor gruppe, hvor ikke to personer falder ind i mere end én gruppe på samme tid, opfattes som ortogonal omgruppering. Dette udtryk bruges dog sjældent, og det kan anses for, at der ikke er nogen almindeligt accepteret betegnelse for denne proces.

Oberwolfach-problemet med at dekomponere en komplet graf til usammenhængende kopier af en given 2-regulær graf generaliserer også Kirkman-problemet om skolepiger. Kirkman-problemet er et specialtilfælde af Oberwolfach-problemet, hvor en 2-regulær graf består af fem usammenhængende trekanter [22] .

Andre applikationer

Noter

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

Litteratur

Links