Kirkman probléma az iskoláslányokról

A Kirkman's Schoolgirl Problem egy kombinatorikus probléma, amelyet Thomas Penington Kirkman javasolt 1850-ben a The Lady's and Gentleman's Diary (1841 és 1871 között megjelent szórakoztató matematikai magazin) VI. kérdéseként . A kihívás így szól:

Tizenöt fiatal lány az iskolában hét napon keresztül (minden nap) egymás után hármat sétál, minden sétához el kell osztani, hogy ne járjon két lány egy sorban ( Graham, Grötschel, Lovász 1995 ).

Megoldás

Ha a lányokat 0-tól 14-ig számozzuk, akkor a következő eloszlás lesz az egyik megoldás [1] :

vasárnap_
_ 		hétfő_
_ 		kedd szerda csütörtök péntek szombat
 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

A probléma megoldása egy Kirkman-hármas rendszer [2] példája ; ez azt jelenti, hogy ez egy Steiner hármas rendszer , amelynek párhuzamossága van, vagyis a hármas rendszer blokkjait párhuzamos osztályokra osztja, amelyek pontok partíciói nem metsző blokkokra.

Az iskoláslányok problémájára hét nem izomorf megoldás létezik [3] . Ezek közül kettő egy tetraéder és annak csúcsai, élei és lapjai közötti kapcsolatként is megjeleníthető [4] . Az alábbiakban egy 3D projektív geometriát használó megközelítést adunk meg GF(2) felett.

XOR tripletek megoldása

Ha a lányokat bináris számokkal 0001-ről 1111-re számozzuk át, a következő eloszlás olyan megoldás, hogy a csoportot alkotó bármely három lány esetében a két szám bitenkénti XOR-ja a harmadikat adja:

vasárnap_
_ 		hétfő_
_ 		kedd szerda csütörtök péntek szombat
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

Ennek a megoldásnak van egy geometriai értelmezése a Galois-geometriához és a PG(3,2) függvényhez . Vegyünk egy tetraédert , és számozzuk át a csúcsait 0001-re, 0010-re, 0100-ra és 1000-re. Számozzuk át a hat élközéppontot az él XOR végeivé. Négy arcközépponthoz három csúcs XOR-jával egyenlő címkéket rendelünk, a test középpontjához pedig az 1111-es címkét, majd 35 tripla van, és az XOR megoldás pontosan 35 direkt PG(3,2)-nek felel meg.

Történelem

Az első megoldást Arthur Cayley publikálta [5] . Ezt gyorsan követte Kirkman saját megoldása [6] , amelyet három évvel korábban publikált kombinatorikus elrendezésének speciális eseteként adtak meg [7] . D. D. Sylvester is kivizsgálta a problémát, és végül kijelentette, hogy Kirkman ellopta tőle az ötletet. A feladvány több szórakoztató matematikai könyvben is megjelent a századfordulón Lucas [8] , Rose Ball [9] , Aarens [10] és Dudeney [11] írói .

Kirkman gyakran magyarázta, hogy hosszú dolgozatát ( Kirkman 1847 ) teljes mértékben a probléma iránti nagy érdeklődés ihlette [12] .

Galois geometria

1910-ben a problémát George Conwell vizsgálta meg a Galois-geometria [13] segítségével .

A két elemű GF(2) Galois-mezőt négy homogén koordinátával egy PG(3,2) 15 pontból, egy egyenesen 3 pontból, egy síkon 7 pontból és 7 egyenesből álló PG(3,2) létrehozására használtuk. A síkot teljes négyszögnek tekinthetjük, amelynek átlós pontjain áthaladó vonalak vannak. Minden pont 7 vonalon fekszik, és összesen 35 vonal van.

A PG(3,2) vonaltereket a PG(5,2) Plucker-koordinátái határozzák meg , 63 ponttal, amelyek közül 35 a PG(3,2) vonalait jelenti. Ez a 35 pont alkotja az S felületet , amelyet Klein-négyzetként ismerünk . Az S -en kívüli 28 pont mindegyikéhez 6 olyan egyenes van ezen a ponton keresztül, amelyek nem metszik S -t [14] .

A hét napjainak számaként hét fontos szerepet játszik a döntésben:

Ha két A és B pontot választunk az ABC egyenesen, akkor az A-n átmenő öt másik egyenes mindegyike a B-n átmenő öt egyenes közül csak egyet metszi. Az e párok metszéspontjából származó öt pont a két A és B ponttal együtt "hét"-nek nevezzük ( Conwell 1910 , 68).

A hetet a két pontja határozza meg. Az S - n kívüli 28 pont mindegyike két hetesen fekszik. 8 hetes van. A projektív lineáris csoport PGL(3,2) izomorf a 8 hetes váltakozó csoportjával [15] .

Az iskoláslány-probléma abból áll, hogy hét nem metsző egyenest találunk az 5 dimenziós térben úgy, hogy bármely két egyenesnek mindig legyen közös hete [16] .

Általánosítás

A probléma általánosítható diáklányokra, ahol olyan számnak kell lennie, amely egy páratlan szám 3-mal (azaz ) szorzatával egyenlő a napok hármasában sétálva azzal a feltétellel, hogy egyetlen lánypár sem jár kétszer ugyanabban a sorban. [17] . Ennek az általánosításnak a megoldása egy Steiner hármas rendszer S(2, 3, 6 t + 3) párhuzamossággal (azaz olyan rendszer, amelyben minden 6 t + 3 elem pontosan egyszer jelenik meg a 3 elemű halmazok minden blokkjában), Kirkman-rendszerként ismert [1] . Ez az általánosítása annak a problémának, amelyet Kirkman eredetileg tárgyalt, és a híres speciális esetet , amelyet később tárgyalt [7] . Az általános eset teljes megoldását D. K. Rei-Chadhuri és R. M. Wilson publikálta 1968-ban [18] , bár a problémát Liu Jaksi (陆家羲) kínai matematikus már 1965-ben megoldotta [19] , de ekkor a megoldást még mindig nem tették közzé [20] .

A fő feladat több változatát is mérlegelték. Alan Hartman a Steiner-féle négyes rendszert használva megoldotta ezt a fajta problémát azzal a követelménnyel, hogy három négyes sorban ne sétáljon többször [21] .

A közelmúltban napvilágot látott egy hasonló probléma, az úgynevezett "golfpálya-probléma", amelyben 32 golfozó van, aki minden nap más emberrel szeretne játszani 4 fős csoportokban, 10 egymást követő napon.

Mivel ez egy olyan átcsoportosítási stratégia, amelyben minden csoport ortogonális, ezért ezt a folyamatot, amikor egy nagy csoportból kis csoportokat alakítanak ki, amelyben két ember nem esik egyszerre több csoportba, ortogonális átcsoportosításnak tekinthető. Ezt a kifejezést azonban ritkán használják, és úgy tekinthetjük, hogy erre a folyamatra nincs általánosan elfogadott kifejezés.

Az Oberwolfach-probléma , amely egy teljes gráfot egy adott 2-reguláris gráf diszjunkt másolataira bont, szintén általánosítja az iskoláslányokra vonatkozó Kirkman-problémát. A Kirkman-probléma az Oberwolfach-probléma speciális esete, amelyben egy 2-reguláris gráf öt diszjunkt háromszögből áll [22] .

Egyéb alkalmazások

Jegyzetek

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

Irodalom

Linkek