Problema lui Kirkman despre eleve

Kirkman's Schoolgirl Problem este o problemă combinatorie propusă de Thomas Penington Kirkman în 1850 ca întrebarea VI în The Lady's and Gentleman's Diary (o revistă distractivă de matematică publicată între 1841 și 1871). Provocarea spune:

Cincisprezece fete tinere de la școală merg trei la rând timp de șapte zile (în fiecare zi), este necesar să le distribuiți pentru fiecare plimbare, astfel încât să nu meargă două fete în același rând ( Graham, Grötschel, Lovász 1995 ).

Soluție

Dacă fetele sunt numerotate de la 0 la 14, următoarea distribuție va fi una dintre soluțiile [1] :

duminica
_ 		luni
_ 		marţi miercuri joi vineri sâmbătă
 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

Soluția la această problemă este un exemplu de sistem triplu Kirkman [2] ; aceasta înseamnă că este un sistem triplu Steiner care are paralelism , adică are o partiție a blocurilor sistemului triplu în clase paralele, care sunt partiții de puncte în blocuri care nu se intersectează.

Există șapte soluții non- izomorfe la problema școlilor [3] . Două dintre ele pot fi vizualizate ca relații între un tetraedru și vârfurile, muchiile și fețele acestuia [4] . O abordare folosind geometria proiectivă 3D peste GF(2) este prezentată mai jos.

Rezolvarea tripleților XOR

Dacă fetele sunt renumerotate cu numere binare de la 0001 la 1111, următoarea distribuție este o soluție astfel încât pentru oricare trei fete care alcătuiesc grupul, XOR pe biți a celor două numere dă a treia:

duminica
_ 		luni
_ 		marţi miercuri joi vineri sâmbătă
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

Această soluție are o interpretare geometrică legată de geometria Galois și PG(3,2) . Luați un tetraedru și renumerotați vârfurile sale ca 0001, 0010, 0100 și 1000. Să renumerotăm cele șase centre ale muchiei ca XOR capete ale muchiei. Atribuim etichete egale cu XOR a trei vârfuri la patru centre ale feței și centrului corpului eticheta 1111. Apoi există 35 de triple și soluția XOR corespunde exact la 35 PG direct(3,2).

Istorie

Prima soluție a fost publicată de Arthur Cayley [5] . A fost urmată rapid de propria soluție a lui Kirkman [6] , care a fost dată ca un caz special al aranjamentului său combinatoriu publicat cu trei ani mai devreme [7] . D. D. Sylvester a investigat și el problema și a ajuns să afirme că Kirkman i-a furat ideea. Puzzle-ul a apărut în mai multe cărți distractive de matematică la începutul secolului de Lucas [8] , Rose Ball [9] , Aarens [10] și Dudeney [11] .

Kirkman a explicat adesea că lucrarea sa lungă ( Kirkman 1847 ) a fost în întregime inspirată de marele interes pentru problemă [12] .

Geometrie Galois

În 1910 problema a fost luată în considerare de George Conwell cu ajutorul geometriei Galois [13] .

Un câmp Galois GF(2) cu două elemente a fost folosit cu patru coordonate omogene pentru a forma un PG(3,2) cu 15 puncte, 3 puncte pe o dreaptă, 7 puncte și 7 drepte pe un plan. Planul poate fi considerat ca un patrulater complet cu linii prin punctele sale diagonale. Fiecare punct se află pe 7 linii și sunt în total 35 de linii.

Spațiile linii PG(3,2) sunt definite de coordonatele lor Plucker în PG(5,2) cu 63 de puncte, dintre care 35 reprezintă linii în PG(3,2). Aceste 35 de puncte formează suprafața S , cunoscută sub numele de cvadrica Klein . Pentru fiecare dintre cele 28 de puncte care nu se află pe S , există 6 drepte prin acest punct care nu se intersectează cu S [14] .

Ca număr de zile dintr-o săptămână, șapte joacă un rol important în deciderea:

Dacă se aleg două puncte A și B de pe dreapta ABC, fiecare dintre celelalte cinci drepte prin A intersectează doar una dintre cele cinci drepte care trec prin B. Cele cinci puncte rezultate din intersecția acestor perechi, împreună cu cele două puncte A și B , numim „șapte” ( Conwell 1910 , 68).

Șapte este definit de cele două puncte ale sale. Fiecare dintre cele 28 de puncte din afara S se află pe două șapte. Sunt 8 șapte. Grupul liniar proiectiv PGL(3,2) este izomorf cu grupul alternativ pe 8 șapte [15] .

Problema elevelor constă în găsirea a șapte linii care nu se intersectează în spațiul 5-dimensional, astfel încât oricare două linii să aibă întotdeauna un șapte comun [16] .

Generalizare

Problema poate fi generalizată la eleve, unde ar trebui să fie un număr egal cu produsul unui număr impar cu 3 (adică, ) mergând în tripleți de zile cu condiția, din nou, ca nicio pereche de fete să nu meargă de două ori în același rând. [17] . Soluția acestei generalizări este un sistem triplu Steiner S(2, 3, 6 t + 3) cu paralelism (adică un sistem în care fiecare 6 t + 3 elemente apar exact o dată în fiecare bloc de mulțimi de 3 elemente), cunoscut sub numele de sistemul Kirkman [1] . Aceasta este generalizarea problemei despre care a discutat inițial Kirkman și celebrul caz special pe care l-a discutat mai târziu [7] . Soluția completă a cazului general a fost publicată de D.K. Rei-Chadhuri și R.M. Wilson în 1968 [18] , deși problema fusese deja rezolvată de matematicianul chinez Liu Jaksi (陆家羲) în 1965 [19] , dar la acel moment soluția a fost încă nu a fost publicată [20] .

Au fost luate în considerare mai multe variante ale sarcinii principale. Alan Hartman a rezolvat acest tip de problemă cu cerința ca trei să nu meargă în rânduri de patru de mai multe ori [21] folosind sistemul de cvadruplu al lui Steiner.

Recent, a ieșit la iveală o problemă similară, cunoscută sub numele de „problema terenului de golf”, în care sunt 32 de jucători de golf care vor să joace în fiecare zi oameni diferiți în grupuri de câte 4, timp de 10 zile consecutiv.

Deoarece aceasta este o strategie de regrupare în care toate grupurile sunt ortogonale, acest proces de formare a unor grupuri mici dintr-un grup mare, în care doi oameni nu se încadrează în mai mult de un grup în același timp, poate fi considerat ca o regrupare ortogonală. Cu toate acestea, acest termen este rar folosit și se poate considera că nu există un termen general acceptat pentru acest proces.

Problema Oberwolfach de descompunere a unui graf complet în copii disjunse ale unui graf dat 2-regular generalizează, de asemenea, problema Kirkman despre eleve. Problema Kirkman este un caz special al problemei Oberwolfach, în care un graf 2-regular este format din cinci triunghiuri disjunctive [22] .

Alte aplicații

Note

  1. ↑ 1 2 Rouse Ball, Coxeter, 1987 , p. 287-289.
  2. ↑ Weisstein, Eric W. Kirkman's Schoolgirl Problem  pe site-ul Wolfram MathWorld .
  3. ↑ Cole, 1922 , p. 435–437.
  4. ↑ Falcone, Pavone, 2011 , p. 887–900.
  5. ↑ Cayley, 1850 , p. 50–53.
  6. ↑ Kirkman, 1850 .
  7. ↑ 12 Kirkman , 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 .

Literatură

Link -uri