Kirkmanova školačka problém - Kirkmans schoolgirl problem - Wikipedia

Původní publikace problému

Kirkmanova školačka problém je problém v kombinatorika navrhl Rev. Thomas Penyngton Kirkman v roce 1850 jako Query VI v Dámský a džentlmenský deník (str. 48). Problém uvádí:

Patnáct mladých dám ve škole chodí tři vedle sebe po dobu sedmi dnů za sebou: je třeba je denně upravovat tak, aby žádné dvě neměly chodit dvakrát vedle sebe.^[1]

Řešení

Pokud jsou dívky očíslovány od 0 do 14, následující řešení je jedním z řešení:^[2]

Řešení tohoto problému je příkladem a Trojitý systém Kirkman,^[3] což je Trojitý systém Steiner mít a rovnoběžnost, tj. rozdělení bloků trojitého systému do paralelních tříd, které jsou samy o sobě oddíly bodů do disjunktních bloků.

Existuje sedm ne-izomorfní řešení problému školačky.^[4] Dva z nich lze zobrazit jako vztahy mezi čtyřstěnem a jeho vrcholy, hranami a plochami.^[5]Přístup využívající projektivní geometrii tří dimenzí GF (2) je uveden níže.

Trojité řešení XOR

Pokud jsou dívky očíslovány v binárních číslech 0001 až 1111, následující uspořádání je jedno řešení, takže pro jakékoli tři dívky, které tvoří skupinu, se bitový XOR libovolných dvou rovná třetímu:

Toto řešení má ve spojení s Galoisova geometrie a PG (3,2). Vezměte si čtyřstěn a označte jeho vrcholy jako 0001, 0010, 0100 a 1000. Označte jejích šest středů hran jako XOR vrcholů této hrany. Označte čtyři středy obličeje jako XOR ze tří vrcholů této tváře a střed těla dostane štítek 1111. Potom 35 triád XOR řešení přesně odpovídá 35 řádkům PG (3,2). Každý den odpovídá spreadu a každý týden balení.^[6]

Dějiny

První řešení publikoval Arthur Cayley.^[7] Krátce poté následovalo Kirkmanovo vlastní řešení^[8] který byl uveden jako zvláštní případ jeho úvah o kombinatorických ujednáních zveřejněných před třemi lety.^[9] J. J. Sylvester také prozkoumal problém a nakonec prohlásil, že Kirkman mu ten nápad ukradl. Hádanka se objevila v několika knihách o rekreační matematice na přelomu století od Lucase,^[10] Probudit míč,^[11] Ahrens,^[12] a Dudeney.^[13]

Kirkman si často stěžoval na skutečnost, že jeho podstatná práce (Kirkman 1847 ) byl zcela zastíněn populárním zájmem o problém školačky.^[14]

Galoisova geometrie

V roce 1910 byl problém vyřešen pomocí Galoisova geometrie George Conwell.^[15]

The Galoisovo pole GF (2) se dvěma prvky se používá se čtyřmi homogenní souřadnice tvořit PG (3,2) který má 15 bodů, 3 body na linii, 7 bodů a 7 linií v rovině. Letadlo lze považovat za kompletní čtyřúhelník společně s přímkou ​​procházející jejími úhlopříčnými body Každý bod je na 7 řádcích a celkem je 35 řádků.

Řádky PG (3,2) jsou označeny jejich Plückerovy souřadnice v PG (5,2) s 63 body, z nichž 35 představuje řádky PG (3,2). Těchto 35 bodů tvoří povrch S známý jako Klein quadric. Za každý z 28 bodů off S je v něm 6 čar, které se neprotínají S.^[15]:67

Protože je sedm dní v týdnu, sedlák je důležitou součástí řešení:

Jsou-li vybrány dva body jako A a B přímky ABC, je každé z pěti dalších přímek procházejících A splněno pouze jednou z pěti dalších přímek procházejících B. Pět bodů určených průsečíky těchto dvojic přímek spolu s dva body A a B označíme jako „heptad“.^[15]:68

Heptad je určen libovolnými dvěma body. Každý z 28 bodů off S leží ve dvou heptadech. Existuje 8 heptád. The projektivní lineární skupina PGL (3,2) je izomorfní střídavá skupina na 8 heptadech.^[15]:69

Problém školačky spočívá v nalezení sedmi řádků v 5prostoru, které se neprotínají a takové, že kterékoli dva řádky mají vždy společný znak.^[15]:74

Pomazánky a balení

A rozdělit bodů do linií se nazývá a šíření, a rozdělení spready geometrie se nazývá a balení.^[16]:66 Když Hirschfeld považoval problém za svůj Konečné projektivní prostory tří dimenzí (1985), poznamenal, že některá řešení odpovídají balením PG (3,2), v podstatě tak, jak je popsáno výše Conwellem,^[16]:91 a představil dva z nich.^[16]:75

Zobecnění

Problém lze zobecnit na ${ displaystyle n}$ děvčata, kde ${ displaystyle n}$ musí být lichý násobek 3 (tj ${ displaystyle n equiv 3 { pmod {6}}}$), chůzi v trojicích pro ${ displaystyle { frac {1} {2}} (n-1)}$ dní, opět s požadavkem, aby žádná dvojice dívek nechodila dvakrát ve stejné řadě. Řešením této generalizace je a Trojitý systém Steiner, S (2, 3, 6t + 3) s paralelismem (to je ten, ve kterém každý z 6t + 3 prvky se vyskytují přesně jednou v každém bloku 3-prvkových sad), známém jako a Trojitý systém Kirkman.^[2] Právě toto zobecnění problému Kirkman diskutoval jako první, zatímco slavný speciální případ ${ displaystyle n = 15}$ bylo navrženo až později.^[9] Kompletní řešení obecného případu zveřejnil D. K. Ray-Chaudhuri a R. M. Wilson v roce 1968,^[17] ačkoli to již bylo vyřešeno Lu Jiaxi (čínština : 陆 家 羲) v roce 1965,^[18] ale nebyl publikován v té době.^[19]

Lze uvažovat o mnoha variantách základního problému. Alan Hartman řeší problém tohoto typu s požadavkem, aby žádná trojice nechodila ve čtyřech vícekrát^[20] pomocí čtyřnásobných systémů Steiner.

V poslední době vzbudil zájem podobný problém známý jako Social Golfer Problem, který se zabývá 32 golfisty, kteří chtějí každý den hrát s různými lidmi ve skupinách po 4, v průběhu 10 dnů.

Jelikož se jedná o strategii přeskupování, kde jsou všechny skupiny ortogonální, lze tento proces v rámci problému organizování velké skupiny do menších skupin, kde žádní dva lidé nesdílejí stejnou skupinu dvakrát, označovat jako ortogonální přeskupení. Tento termín se však v současné době běžně nepoužívá a důkazy naznačují, že neexistuje žádný běžný název procesu.

Problém Vyřešitelné krytiny považuje za obecný ${ displaystyle n}$ dívky, ${ displaystyle g}$ skupinový případ, kdy každá dvojice dívek musí být v určitém okamžiku ve stejné skupině, ale chceme využít co nejméně dní. To lze například použít k naplánování plánu rotujícího stolu, ve kterém musí být každá dvojice hostů v určitém okamžiku u stejného stolu.^[21]

The Oberwolfachův problém, rozkladu a kompletní graf do okrajově disjunktních kopií daného 2-pravidelný graf, také zobecňuje problém Kirkmanovy školy. Kirkmanovým problémem je zvláštní případ Oberwolfachova problému, ve kterém se 2-regulární graf skládá z pěti disjunktních trojúhelníků.^[22]

Další aplikace

• Kooperativní učení strategie pro zvýšení interakce v rámci výuky ve třídě
• Dobble karetní hra^[23]
• Progresivní večeře party vzory
• Rychlost vytváření sítí Události
• Sportovní soutěže

Poznámky

Reference

• Ahrens, W. (1901), Mathematische Unterhaltungen und Spiele, Lipsko: Teubner
• Bryant, Darryn; Danziger, Peter (2011), "O bipartitních 2-faktorizacích ${ displaystyle K_ {n} -I}$ a problém Oberwolfach “ (PDF), Journal of Graph Theory, 68 (1): 22–37, doi:10,1002 / jgt.20538, PAN  2833961
• Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Příručka kombinatorických vzorů (2. vyd.), Boca Raton: Chapman & Hall / CRC, ISBN  978-1-58488-506-1
• Cummings, L.D. (1918), „Podhodnocený Kirkmanův papír“, Bulletin of the American Mathematical Society, 24 (7): 336–339, doi:10.1090 / S0002-9904-1918-03086-3
• Dudeney, H.E. (1917), Zábava v matematice, New York: Dover
  • Dudeney, H.E. (1958), Zábava v matematice, Dover Rekreační matematika, Mineola, New York Dover, ISBN  978-0-486-20473-4
• Graham, Ronald L.; Grötschel, Martin; Lovász, László (1995), Handbook of Combinatorics, Volume 2, Cambridge, MA: MIT Press, ISBN  0-262-07171-1
• Hartman, Alan (1980), „Kirkmanův problém s pozounem“, Ars Combinatoria, 10: 19–26
• Lu, Jiaxi (1990), Sebraná díla Lu Jiaxiho na kombinatorických designech„Huhhot: Lidový tisk ve vnitřním Mongolsku
• Kirkman, Thomas P. (1847), „Na problém v kombinaci“, Cambridge a Dublin Mathematical Journal, Macmillan, Barclay a Macmillan, II: 191–204
• Kirkman, Thomas P. (1850), „Poznámka k nezodpovězené otázce ohledně ceny“, Cambridge a Dublin Mathematical Journal, Macmillan, Barclay a Macmillan, 5: 255–262
• Lucas, E. (1883), Récréations Mathématiques, 2, Paříž: Gauthier-Villars, s. 183–188
• Ray-Chaudhuri, D.K .; Wilson, R.M. (1971), „Solution of Kirkman's schoolgirl problem, in Combinatorics, University of California, Los Angeles, 1968", Proceedings of Symposia in Pure Mathematics, Providence, Rhode Island: American Mathematical Society, XIX: 187–203, doi:10.1090 / pspum / 019/9959, ISBN  978-0-8218-1419-2
• Rouse Ball, W.W. (1892), Matematické rekreace a eseje, Londýn: Macmillan
  • Ball, W.W. Probudit; Coxeter, H.S.M. (1987) [1974], Matematické rekreace a eseje (13. vyd.), Dover, s. 287–289, ISBN  0-486-25357-0

externí odkazy

• Weisstein, Eric W. „Kirkmanova školačka problém“. MathWorld.
• Klarreich, Erica (9. června 2015), „Vyřešeno dilema designu, mínus designy.“, Časopis Quanta