Kirkmanův problém o školačkách

Kirkman's Schoolgirl Problem je kombinatorický problém navržený Thomasem Peningtonem Kirkmanem v roce 1850 jako otázka VI v Deníku dámy a gentlemana (zábavný matematický časopis vydávaný mezi lety 1841 a 1871). Výzva říká:

Patnáct mladých dívek ve škole chodí tři za sebou po sedm dní (každý den), je nutné je rozdělit na každou procházku tak, aby nechodily dvě dívky ve stejné řadě ( Graham, Grötschel, Lovász 1995 ).

Řešení

Pokud jsou dívky očíslovány od 0 do 14, bude jedním z řešení následující rozdělení [1] :

neděle
_ 		pondělí
_ 		úterý středa Čtvrtek pátek sobota
 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

Řešením tohoto problému je příklad Kirkmanova trojitého systému [2] ; to znamená, že se jedná o Steinerův trojitý systém , který má paralelismus , to znamená, že má rozdělení bloků trojného systému do paralelních tříd, což jsou rozdělení bodů do neprotínajících se bloků.

Existuje sedm neizomorfních řešení problému školaček [3] . Dva z nich lze zobrazit jako vztahy mezi čtyřstěnem a jeho vrcholy, hranami a plochami [4] . Níže je uveden přístup využívající 3D projektivní geometrii přes GF(2) .

Řešení trojic XOR

Pokud jsou dívky přečíslovány binárními čísly od 0001 do 1111, je následující rozdělení řešením takové, že pro všechny tři dívky, které tvoří skupinu, bitový XOR těchto dvou čísel dává třetí:

neděle
_ 		pondělí
_ 		úterý středa Čtvrtek pátek sobota
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

Toto řešení má geometrickou interpretaci související s Galoisovou geometrií a PG(3,2) . Vezměte čtyřstěn a přečíslujte jeho vrcholy na 0001, 0010, 0100 a 1000. Přečíslujme šest středů hran jako XOR konce hrany. Čtyřem středům obličeje přiřadíme štítky rovné XOR tří vrcholů a středu těla štítek 1111. Pak je 35 trojic a řešení XOR odpovídá přesně 35 přímým PG(3,2).

Historie

První řešení publikoval Arthur Cayley [5] . Rychle bylo následováno Kirkmanovým vlastním řešením [6] , které bylo uvedeno jako zvláštní případ jeho kombinatorického uspořádání publikovaného o tři roky dříve [7] . D. D. Sylvester také problém prošetřil a nakonec prohlásil, že Kirkman mu nápad ukradl. Hádanka se objevila v několika zábavných matematických knihách na přelomu století od Lucase [8] , Rose Ball [9] , Aarense [10] a Dudeneyho [11] .

Kirkman často vysvětloval, že jeho dlouhý článek ( Kirkman 1847 ) byl zcela inspirován velkým zájmem o tento problém [12] .

Galoisova geometrie

V roce 1910 se tímto problémem zabýval George Conwell s pomocí Galoisovy geometrie [13] .

Galoisovo pole GF(2) se dvěma prvky bylo použito se čtyřmi homogenními souřadnicemi k vytvoření PG(3,2) s 15 body, 3 body na přímce, 7 body a 7 přímkami na rovině. Rovinu lze považovat za úplný čtyřúhelník s přímkami procházejícími jejími diagonálními body. Každý bod leží na 7 úsecích a celkem je jich 35.

Řádkové prostory PG(3,2) jsou definovány svými Pluckerovými souřadnicemi v PG(5,2) s 63 body, z nichž 35 představuje čáry v PG(3,2). Těchto 35 bodů tvoří povrch S , známý jako Kleinova kvadrika . Pro každý z 28 bodů, které nejsou na S , vede tímto bodem 6 čar, které S neprotínají [14] .

Jako počet dní v týdnu hraje sedm důležitou roli při rozhodování:

Pokud jsou vybrány dva body A a B na přímce ABC, každá z pěti dalších přímek procházejících A protíná pouze jednu z pěti přímek procházejících bodem B. Pět bodů vzniklých průnikem těchto dvojic spolu se dvěma body A a B , nazýváme „sedm“ ( Conwell 1910 , 68).

Sedmička je definována svými dvěma body. Každý z 28 bodů mimo S leží na dvou sedmičkách. Sedmiček je 8. Projektivní lineární grupa PGL(3,2) je izomorfní s alternující grupou na 8 sedmičkách [15] .

Problém školačky spočívá v nalezení sedmi neprotínajících se čar v 5-rozměrném prostoru tak, že jakékoli dvě čáry mají vždy společných sedm [16] .

Generalizace

Problém lze zobecnit na studentky, kde by mělo být číslo rovné součinu lichého čísla o 3 (tj. ) chůze v trojicích dnů opět s podmínkou, že žádná dvojice dívek nechodí dvakrát ve stejné řadě [17] . Řešením tohoto zobecnění je Steinerova trojná soustava S(2, 3, 6 t + 3) s paralelismem (tedy soustava, ve které se každých 6 t + 3 prvky objeví právě jednou v každém bloku 3prvkových množin), známý jako Kirkmanův systém [1] . Toto je zobecnění problému, o kterém Kirkman původně diskutoval, a slavný zvláštní případ , o kterém později mluvil [7] . Kompletní řešení obecného případu publikovali D. K. Rei-Chadhuri a R. M. Wilson v roce 1968 [18] , i když problém již řešil čínský matematik Liu Jaksi (陆家羲) v roce 1965 [19] , ale v té době již řešení bylo stále nebylo publikováno [20] .

Bylo zvažováno několik variant hlavního úkolu. Alan Hartman vyřešil tento typ problému požadavkem, aby žádní tři nechodili v řadách po čtyřech více než jednou [21] pomocí Steinerova systému čtveřice.

Nedávno vyšel najevo podobný problém, známý jako „problém golfového hřiště“, ve kterém je 32 golfistů, kteří chtějí hrát každý den s různými lidmi ve skupinách po 4 po dobu 10 po sobě jdoucích dnů.

Vzhledem k tomu, že se jedná o strategii přeskupování, kde jsou všechny skupiny ortogonální, lze tento proces vytváření malých skupin z velké skupiny, ve kterém žádní dva lidé nespadají do více než jedné skupiny současně, považovat za ortogonální přeskupování. Tento termín se však používá jen zřídka a lze mít za to, že pro tento proces neexistuje žádný obecně uznávaný termín.

Oberwolfachovský problém rozkladu kompletního grafu na disjunktní kopie daného 2-regulárního grafu také zobecňuje Kirkmanův problém o školačkách. Kirkmanův problém je speciálním případem Oberwolfachského problému, ve kterém se 2-pravidelný graf skládá z pěti disjunktních trojúhelníků [22] .

Jiné aplikace

Poznámky

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

Literatura

Odkazy