Využití teorie grup při řešení hlavolamů

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Tomáš Pavlík Využití teorie grup při řešení hlavolamů Katedra algebry

Vedoucí bakalářské práce: Mgr. Jakub Opršal Studijní program: Matematika Studijní obor: obecná matematika

Praha 2012

Poděkování. Rád bych zde poděkoval svému vedoucímu bakalářské práce Mgr. Jakubovi Opršalovi za cenné rady a připomínky, kterými přispěl k vypracování této práce.

Prohlašuji, že jsem tuto bakalářskou práci vypracoval samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle §60 odst. 1 autorského zákona. V ........ dne ............

Podpis autora

Název práce: Využití teorie grup při řešení hlavolamů Autor: Tomáš Pavlík Katedra: Katedra algebry Vedoucí bakalářské práce: Mgr. Jakub Opršal, Katedra algebry Abstrakt: Tato bakalářská práce se zabývá teorií hlavolamů a jejím propojení s teorií grup. Cílem práce je zavést pojem hlavolamu do matematiky a využít známé teorie o grupách k jeho vyřešení, zvláštní pozornost bude zaměřena na řešitelné grupy. Vše je proloženo množstvím praktických příkladů pro lepší pochopení této problematiky. Klíčová slova: hlavolam, teorie grup, permutační grupa, řešitelné grupa

Title: Use of group theory to solve puzzles Author: Tomáš Pavlík Department: Katedra algebry Supervisor: Mgr. Jakub Opršal, Katedra algebry Abstract: This thesis studies the theory of combinatorical puzzles and its connection to the group theory. The aim of this work is to introduce the concept of puzzle to mathematics and to use group theory to solve it, special attention will be focused on solvable groups. Everything is interspersed with a number of practical examples to better understand the topic. Keywords: puzzle, group theory, permutation group, solvable group

Obsah 1 Úvod

2

2 Řešení hlavolamů 2.1 Permutační hlavolamy . . . . . . . . . . . . . . . . . . . . . . . .

3 6

3 Hlavolamy s řešitelnou grupou 3.1 Generátory podgrupy . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Algoritmus na řešení řešitelných grup . . . . . . . . . . . . . . . .

9 12 13

4 Hlavolam IQ 139 4.1 Grupa a řešení hlavolamu . . . . . . . . . . . . . . . . . . . . . . 4.2 Algoritmus na řešení a nejmenší počet tahů . . . . . . . . . . . .

14 14 15

5 Hlavolamy typu puk 5.1 Sudé puky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Liché puky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Hledání řešení . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 19 22

6 Neregulární hlavolamy 6.1 Zjednodušování hlavolamů . . . . . . . . . . . . . . . . . . . . . . 6.2 Obtížnost hlavolamů . . . . . . . . . . . . . . . . . . . . . . . . .

23 23 24

7 Božské číslo hlavolamu IQ 139 7.1 Popis algoritmu pro generování 7.2 Popis algoritmu pro hledání . . 7.3 Výsledky . . . . . . . . . . . . . 7.4 Modifikace na ostatní hlavolamy

25 25 26 26 26

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Doslov

27

Seznam použité literatury

28

1

1. Úvod Budeme se zabývat mechanickými hlavolamy, kde mohou být jednotlivé dílky natočeny do různých poloh. Zamíchaný hlavolam vždy skládáme do konkrétní polohy pomocí posloupnosti povolených pohybů. Ty jsou definovány designem hlavolamu. Jedním z nejznámějších hlavolamů je bezpochyby Rubikova kostka, kterou vymyslel Ernő Rubik v roce 1974. Od té doby se vytvořilo mnoho jejích modifikací. Jsou verze, kde je kostka rozřezána na víc části nebo dokonce nepravidelně. Kromě toho jsou i různé obdoby ve tvaru například čtyřstěnu nebo dvanáctistěnu. Ani po téměř čtyřiceti letech nejsou ještě odhalena všechna tajemství Rubikovy kostky. Uveďme zde jeden z dlouho otevřených problémů. Úkolem je určit nejmenší počet tahů, na které jde tento hlavolam složit v nejhorším možném zamíchání. V rámci desítek let se odhady na toto číslo stále zlepšovali za pomocí sofistikovaných algoritmů a teorie grup. V roce 2010, když byl odhad dvacet až dvacet dva tahů, se pánové Rokicki, Kociemba, Davidson a Dethridge rozhodli vyřešit úlohu hrubou silou. Napsali tedy program, který měl za úkol projít všechna možná zamíchání a pro každé z nich určit nejmenší počet potřebných tahů na složení. I když byl program maximálně optimalizovaný a využíval všechny symetrie kostky, běžel by na běžném počítači desítky let. Za pomoci společnosti Google a jejich silných počítačů výpočet trval jen několik týdnů a tím našli hledané číslo, které je 20. To je známé jako God’s number. Mnoho dalších otázek okolo Rubikovy kostky zůstává nezodpovězených. [5] My se ale budeme zabývat jinou, méně známou třídou hlavolamů. Půjde o hlavolamy podobné IQ 139, který je popsaný v kapitole 4. Navíc budeme hledat řešení obecných hlavolamů. Je těžké říci, co dělá hlavolam těžkým. Pokusíme se propojit obtížnost hlavolamu se strukturou grupy, kterou hlavolam tvoří. Zvláště se budeme zabývat řešitelnými grupami. Tento pojem zavedl Galois pro grupy, kde každá řešitelná grupa odpovídá polynomu, který je řešitelný v radikálech [3].

2

2. Řešení hlavolamů V této kapitole si zadefinujeme pojem hlavolamu a budeme se zabývat otázkou jeho vyřešení. Budeme používat základní definice z teorie grup, které lze najít například v [2]. Pro zavedení hlavolamu si připomeňme pojem stabilizátoru a orbity. Definice 2.1. Nechť G ≤ Sym(M ), pak Gm = {g ∈ G : g(m) = m} nazýváme stabilizátorem prvku m ∈ M a Om = {g(m)|g ∈ G} nazýváme orbitou prvku m ∈ M. Definice 2.2. Grupu G ≤ Sym(M ) nazveme semiregulární pokud Gm = 1 pro všechna m ∈ M . Definice 2.3. Prvotní hlavolam definujeme jako uspořádanou trojici (U, B, e), pro kterou platí e ∈ U a B ⊂ Sym(U ), kde U je konečná množina všech možných stavů hlavolamu, B je množina povolených tahů na hlavolamu a e zastupuje stav hlavolamu, kdy je ve vyřešené poloze. U všech hlavolamů budeme předpokládat, že každý tah lze i vrátit. Příklad. Na ukázku si vezměme klasickou Rubikovu kostku. Pak je U množina všech možných zamíchání kostky, kde e ∈ U je správně složená kostka a B jsou povolené tahy – to jsou tři různá otočení na každé stěně. To dává celkem 18 možných tahů a každý z nich chápeme jako zobrazení, kde každému stavu přiřadíme stav po tom, co provedeme daný tah. Prvotní hlavolam je struktura, kterou dostaneme spolu s fyzickým hlavolamem. Není těžké určit množinu všech stavů, tahů a vyřešený stav hlavolamu pouhým pohledem. Pro lepší práci si zavedeme trochu odlišnou strukturu, se kterou půjde lépe pracovat. Definice 2.4. Nechť (U, B, e) je prvotní hlavolam. Najdeme grupu všech posloupností tahů G = hBi ≤ Sym(U ) a orbitu S = Oe ⊂ U . Pak hlavolam definujeme jako uspořádanou trojici (G, B, S), kde G i B chápeme jako restrikci jen na Oe a S jako množinu s prvkem e. Grupě G říkáme grupa hlavolamu a B nazýváme množinou generátorů (nebo také tahů) hlavolamu a S nazýváme množinou řešitelných stavů. Pro hlavolam (G, B, S) tedy platí, že hBi = G ≤ Sym(S) a navíc je G tranzitivní. Z definice orbity je zřejmé, že pro každý řešitelný stav s ∈ S existuje posloupnost tahů b1 , b2 , . . . , bn ∈ B tak, že b1 b2 . . . bn (e) = s. Konečné posloupnosti generátorů budeme říkat postup. Věta 2.5. Mějme hlavolam (G, B, S), kde G je semiregulární grupa. Potom existuje bijekce z S na G. Důkaz. Definujme funkci f : G → Oe , f : g 7→ g(e). Nechť pro spor f není prostá. Existují dva různé g, h ∈ G tak, že g(e) = h(e). Pak (h−1 g)(e) = e a to je spor se semiregularitou G. Dále f je na, neboť pro každé m ∈ Oe existuje g ∈ G tak, že g(e) = m. 3

Grupu G pak můžeme ztotožnit s množinou všech řešitelných stavů. Takovým hlavolamům říkáme regulární a značíme je pouze (G, B). Těmto hlavolamům se budeme věnovat hlavně, proto když neřekneme jinak, budeme myslet regulární hlavolam. Příklad. Ukážeme si jak může vypadat tento popis na hlavolamu, který je známý jako Loydova patnáctka. Jde o desku 4x4 s patnácti očíslovanými kameny a jedním volným polem. Povolený tah je přesunutí kamenu na prázdné pole sousedící hranou. Hlavolam je vyřešený, když jdou čísla popořadě a volné místo je vpravo dole. Definujme si stavy jako všechny permutace na patnácti polích, když je prázdné místo vpravo dole. Tah potom bude libovolná konečná sekvence přesouvaní kamenů, která končí hned když je prázdné místo opět vpravo dole. Tento hlavolam je regulární, neboť tahy jsou permutace na množině kamenů. Později dokážeme, že grupa tohoto hlavolamu je izomorfní s A15 , což je tedy i množina všech řešitelných stavů. Často budeme potřebovat vyjádřit množinu tahů a jejich inverzí, proto zave¯ = B ∪ B −1 . deme značení B Pokud dostaneme do ruky nějaký fyzický hlavolam, budeme ho chtít nejdříve převést do formy, se kterou budeme umět dále pracovat. Jde tedy o proces, kde k prvotnímu hlavolamu chceme nalézt odpovídající hlavolam (G, B, S). Problém. Nalezení grupy hlavolamu. Vstup: Prvotní hlavolam (U, B, e) Výstup: Grupa hlavolamu G = hBi Pokud navíc budeme předpokládat, že univerzum U je množina stavů hlavolamu s operací skládání tak, že tvoří grupu a zároveň B ⊂ U . Pak se problém redukuje na nalezení grupy hBi = G ≤ U , ta odpovídá všem řešitelným stavům. Tento problém se vpodstatě zabývá určováním řešitelnosti stavů hlavolamu. Příklad. Vezměme si například Rubikovu kostku klasického rozměru 3x3x3. Navíc nám nebude nezáležet na správné orientaci kostiček, ale pouze na jejich správném umístění. Univerzum U si můžeme zvolit jako symetrickou grupu na všech dvaceti šesti kostičkách S26 . Generátorů bude celkem 18 – tři různé pohyby na každé stěně. Nyní chceme pro každou permutaci z S26 zjistit, zda existuje postup, který ji generuje. Zde je například jasné, že každá permutace, kde nejsou středové kostičky stěn na svých místech, je neřešitelná, protože žádný z generátorů s nimy nehýbe. Tím dostáváme lepší horní odhad na grupu řešitelných stavů G ≤ S20 . Dále budeme chtít umět ke každému řešitelnému stavu najít posloupnost tahů, jejichž aplikací vyřešíme hlavolam v daném stavu. Problém. Nalezení řešení hlavolamu. Vstup: hlavolam (G, B), g ∈ G ¯ kde b1 b2 . . . bn = g Výstup: b1 , b2 , . . . , bn ∈ B, Už víme, že pro každý řešitelný stav existuje postup, který ho generuje. Tato úloha spočívá v nalezení této posloupnosti konstruktivně. Jde tedy o úlohu, kdy je zadán hlavolam (G, B) a řešitelný stav g ∈ G a výstup je postup b1 b2 . . . bn = g. Převrácením této posloupnosti a nahrazení tahů za inverzní pak dostaneme inverzní postup, který nás ze stavu g dostane do identity a tedy vyřeší hlavolam. Pro neregulární hlavolam (G, B, S) jde úloha formulovat tak, že pro dané s ∈ S hledáme posloupnost b1 b2 . . . bn (e) = s. 4

Příklad. Uvažujme hlavolam ve formě čtyř rozlišitelných bodů v rozích čtverce, kde přípustný tah je prohození dvou sousedních vrcholů. Jediné správné řešení je když všechny body jsou na svém původním místě. Definujme tedy univerzum jako permutační grupu na čtyřech bodech U = S4 . A generátory jsou B = {a, b, c, d}, kde a = (1, 2) = a−1 , b = (2, 3) = b−1 , c = (3, 4) = c−1 , d = (4, 1) = d−1 . Nalezněme nyní grupu hlavolamu G = hBi. Najdeme postupy, které generují zbylé dvě transpozice v S4 , to jsou například aba = (1, 3), cdc = (1, 4). Nyní víme, že G obsahuje všechny své transpozice, a tedy musí být symetrická G = S4 . Vyřešení toho hlavolamu není problém, když si uvědomíme, že jsme grupu G našli konstruktivně. Mějme zadanou permutaci g ∈ G = S4 , tu umíme rozložit na složení konečného počtu transpozic. Všechny transpozice umíme vygenerovat, takže stačí postupně transpozice nahrazovat za nalezené postupy. Věta 2.6. Nechť (G, B) je hlavolam. Pak pro každý stav g ∈ G existuje n ≤ |G| a prvky bi ∈ B, i = 1, . . . , n, že g = b1 b2 . . . bn . Důkaz. Platí hBi = G, tedy existuje alespoň jedna posloupnost bi ∈ B, i = 1, . . . , m b1 b2 . . . bm = g. Najdeme nejkratší takovou a pro spor předpokládejme, že m > |G|. Označme gi = b1 b2 . . . bi pro i ≤ m. Z Dirichletova principu vyplývá, že existují k 6= l tak, že gk = gl , BÚNO nechť k < l. Pak bk+1 bk+2 . . . bl = id a tedy existuje kratší posloupnost b1 . . . bk bl+1 . . . bm = g, což je spor. Tato věta říká, že pro každý řešitelný stav hlavolamu, můžeme najít postup, který jej generuje a ten je dlouhý nejvíce |G| tahů. Pro neregulární hlavolam pak obdobná věta odhaduje délku postupu číslem |S|. Věta 2.7. Buď (G, B) hlavolam. Pak existují b1 , b2 , . . . , bn ∈ B tak, že ∀g ∈ G∃i ≥ 0 : g = b1 b2 . . . bi . Důkaz. Všechny prvky G si libovolně seřadíme do posloupnosti g1 , g2 , . . . g|G| . Po−1 tom prvních 2n−1 prvků posloupnosti g1 , g1−1 , g2 , g2−1 , . . . , g|G| , g|G| generuje prvek −1 −1 −1 gn pro všechna n = 1, 2, . . . , |G|. Každý z prvků (g1 ), (g1 g2 ), (g2 g3 ), . . . , (g|G| ) lze nahradit posloupností tahů, čímž jsme hotovi. Předchozí věta říká, že pro každý hlavolam existuje postup, který ho v průběhu vyřeší nehledě na počáteční stav. Tato konstrukční metoda nám však udělá postup hodně dlouhý. Má však smysl hledat kratší postupy a nejkratší postup. Je jasné, že nejkratší postup bude mít délku alespoň |G|−1. Najít nejkratší postup je velmi těžký úkol, kterému se zde nebudeme věnovat. Například pro Rubikovu kostku není známý. Platí i obdobná verze této věty pro neregulární hlavolam (G, B, S), kde si seřadíme všechny stavy do posloupnosti s1 , s2 , . . . s|S| . Z definice S víme, že G ≤ Sym(S) je tranzitivní a tedy existuje gi ∈ G tak, že gi (si ) = si+1 pro i = 1, 2, . . . , |S| − 1. Pak máme řadu prvků g1 , g2 , . . . g|S|−1 , která posouvá stav e postupně do všech řešitelných stavů. Opět stačí nahradit jednotlivé prvky generátory. 5

2.1

Permutační hlavolamy

Většina hlavolamů se skládá z několika dílků, které je možné mezi sebou prohazovat. Proto se budeme zabývat hlavně permutačními grupami a jejich vlastnostmi. Množinu pohyblivých dílků hlavolamu budeme běžně označovat M . Permutační hlavolam definujeme tak, že platí B ⊂ Sym(M ). Množina všech stavů je pak U = Sym(M ) a G ≤ Sym(M ). Zároveň jde však o regulární hlavolam, tedy množina všech řešitelných stavů je G. Definice 2.8. Permutační grupa G ≤ Sym(M ) je k-tranzitivní, pokud pro každou uspořádanou k-tici po dvou různých prvků v M existuje zobrazení z G, které ji zobrazí na libovolnou jinou uspořádanou k-tici po dvou různých prvků z M . Lemma 2.9. Permutační grupa G ≤ Sym(M ) je k-tranzitivní, právě když existují po dvou různé prvky c1 , c2 , . . . , ck ⊂ M takové, že pro libovolné po dvou různé b1 , b2 , . . . , bk ∈ M existuje p ∈ G tak, že p(bi ) = ci pro všechna i = 1, . . . , k. [8] Důkaz. Implikace zleva doprava je triviální, zpětnou dokážeme jednoduše. Najdeme p a q tak, že p(ai ) = ci , q(bi ) = ci pro všechna i = 1, . . . , k. Potom hledaná permutace z definice tranzitivnosti je q −1 p. Toto lemma budeme využívat na hlavolamech tak, že pokud umíme přesunout libovolných k dílků hlavolamu do k předem daných pozic, pak je umíme přesunout na libovolné pozice v hlavolamu. Sílu tohoto lemmatu si předvedeme na hlavolamu Loydova patnáctka, který jsme popsali nazačátku této kapitoly. Dokažme tedy, že je 3-tranzitivní. Podle lemmatu stačí dostat libovolné kameny na místa prvních tří kamenů. Na obrázku cesta značí pohyb prázdného pole po desce, takový tah je potom cyklus na prvcích v opačném směru. Opakováním těchto cyklů tedy můžeme dostat libovolný dílek na dané pole.

(a) 1-tranzitivita

(b) 2-tranzitivita

(c) 3-tranzitivita

Poznámka. Pokud by se obecně cesta protla sama se sebou, pak už to nemusí být jeden cyklus, ale jiná permutace. Věta 2.10. Pokud je permutační grupa G k-tranzitivní pro k > 5, pak je G symetrická nebo alternující. [1] Tato věta je velmi těžká, a její důkaz zde uvádět nebudeme. Důkaz využívá klasifikace konečných jednoduchých grup a je potřeba projít mnoho různých možností. 6

Lemma 2.11. Množina všech trojcyklů v Sn generuje An Důkaz. Každý prvek z An lze vyjádřit jako složení sudého počtu transpozic. Stačí dokázat, že libovolné dvě transpozice se dají vyjádřit pomocí trojcyklů. Mějme tedy transpozice (a1 , a2 ), (b1 , b2 ). Pokud se rovnají, jsme hotovi. Pokud jsou všechny prvky různé, pak (a1 , a2 ) · (b1 , b2 ) = (b1 , b2 , a1 ) · (a1 , a2 , b2 ). Pokud jsou dva prvky stejné BÚNO a1 = b1 , pak (a1 , a2 ) · (b1 , b2 ) = (a1 , b2 , a2 ). Lemma 2.12. Nechť grupa G ≤ Sym(M ) je k-tranzitivní a obsahuje cyklus délky k pro k > 1, pak je G alternující nebo symetrická. Důkaz. 1. krok: G obsahuje všechny cykly délky n. Nechť {bi }ni=1 ∈ M . Víme že existuje {ai }ni=1 ∈ M taková, že (a1 , . . . , an ) = c ∈ G. Z n-tranzitivity plyne, že existuje p ∈ G takové, že p(ai ) = bi pro i = 1, . . . , n. Pak p · c · p−1 = (b1 , . . . , bn ) ∈ G. 2.krok: G obsahuje všechny trojcykly. Nechť b1 , b2 , b3 ∈ M . Zvolme b4 , . . . , bn ∈ M libovolně, aby byla posloupnost po dvou disjunktní. Pak (b1 , b2 , b3 ) = (b3 , b2 , b1 , bn , bn−1 , . . . , b4 ) · (b1 , b3 , b2 , b4 , b5 , . . . , bn ) ∈ G. 3. krok: Z předchozího lemmatu plyne, že G ≥ Alt(M ). Pokud G obsahuje lichou permutaci, pak G 6= Alt(M ) a je tedy symetrická, protože Alt(M ) je maximální podgrupa v Sym(M ). Pokud žádnou lichou permutaci neobsahuje pak je alternující. Poznámka. Poslední krok předchozího důkazu lze také provést následovně. Nechť p ∈ G a q ∈ Sym(M ) jsou liché permutace. Pak r = p · q ∈ G, protože je sudá. Tedy q = p−1 r ∈ G, z čehož plyne, že G je symetrická. Nyní můžeme už nalézt grupu G Loydovy patnáctky. Dokázali jsme, že je 3tranzitivní, a existuje trojcyklus (viz obrázek 2.1). Z předchozího lemmatu plyne, že G je alternující nebo symetrická. Dokažme, že každý tah je sudá permutace. Uvažujme nachvíli, že prázdné pole je kámen s číslem 16. Každý tah si pak můžeme vyjádřit jako složení transpozic, kde jeden prvek je vždy kámen 16. Počet transpozic bude sudý, protože si můžeme hrací desku obarvit šachovnicově a při každé transpozici se změní barva pole na kterém je kámen 16. Z definice tahu víme, že kámen 16 skončí opět vpravo dole, tedy je to permutace na patnácti prvcích, která je navíc sudá. Grupa hlavolamu je tedy A15 .

Obrázek 2.1: trojcyklus na patnáctce

7

Definice 2.13. Nechť G a H jsou grupy a f : G → Aut(H) je zobrazení. Semidirektní součin G ⋉f H je grupa definovaná na množině G × H s binární operací (g1 , h1 ) · (g2 , h2 ) = (g1 g2 , h1 f (g1 )(h2 )), inverzí (g, h)−1 = (g −1 , f (g)−1 (h−1 )) a jednotkovým prvkem (1, 1). Definice 2.14. Nechť M = {m1 , m2 , . . . , mn } a G ≤ Sym(M ), Gi jsou grupy pro všechna 1 ≤ i ≤ n. Označme G1 × G2 × · · · × Gn = H. Pak G ⋉ H definujeme jako G ⋉f H, kde f zobrazí permutaci z G do permutace složek na H, což je automorfismus na H právě když platí: Gi 6= Gj ⇒ ∀p ∈ Gp(mi ) 6= mj , neboli že v rámci každé orbity G jsou příslušné grupy orientací shodné. Při hledání grupy hlavolamu budeme často potřebovat vyjádřit různou orientaci dílků hlavolamu. Na to použijeme právě semidirektní součin. G bude grupa permutací na množině M a H bude direktní součin grup orientací jednotlivých dílků, to budou většinou Z2 nebo Z3 , podle počtu možných natočení. Na příkladu Rubikovy kostky klasického rozměru 3x3x3 mají všechny rohové kostičky tři možné orientace a všechny hranové kostičky mají dvě možné orientace. Zároveň rohové i hranové kostičky tvoří orbitu. Grupa všech řešitelných stavů je pak podgrupa (S8 ⋉ Z38 ) × (S12 ⋉ Z212 ). Poznámka. Grupa všech řešitelných stavů Rubikovy kostky je ve skutečnosti izomorfní s (Z37 × Z211 ) ⋊ ((A8 × A12 ) ⋊ Z2 ). [4]

8

3. Hlavolamy s řešitelnou grupou Nyní se budeme na chvíli zabývat hlavolamy, které mají řešitelnou grupu. Poznámka. Abelovské grupy budeme uvádět v aditivní notaci. U cyklických grup Zn , je prvek 1 ∈ Zn generátor grupy a 0 je jednotkový prvek. Definice 3.1. Pro a, b ∈ G definujeme komutátor [a, b] jako a−1 b−1 ab. Jsou-li A, B podgrupy grupy G, tak [A, B] označuje podgrupu generovanou množinou {[a, b]; a ∈ A, b ∈ B}. Grupě [G, G] se říká komutant G a označuje se G′ . Definice 3.2. Grupa G se nazývá řešitelná, jestliže G(n) = 1 pro nějaké n ≥ 0. Nejmenší takové n se nazývá stupeň řešitelnosti grupy G. Věta 3.3. Grupa G je řešitelná, právě když existuje subnormální řada G = G0 ⊲ G1 ⊲ · · · ⊲ Gn = 1, jejíž všechny faktory jsou abelovské. [7] Věta 3.4. Nechť grupa G má podgrupu izomorfní s A5 , pak G není řešitelná. [3] Důkaz. Dokažme nejdřív, že A′5 = A5 . Zvolme si libovolný trojcyklus, BÚNO (1, 2, 3). Nechť a = (1, 2)(4, 5), b = (2, 3)(4, 5) potom aba−1 b−1 = abab = (1, 2, 3) ∈ A′5 . Z toho plyne, že A′5 obsahuje všechny trojcykly a proto je alternující. Grupa A5 tedy není řešitelná a zbytek důkazu plyne z předchozí věty. Věta 3.5. Nechť H ≤ G. Je-li G řešitelná, pak je H řešitelná. Důkaz. Dokažme, že H (i) ≤ G(i) pro všechna i ≥ 0. Snadnou indukcí podle i: Případ i = 0 je zřejmý a z H (i) ≤ G(i) plyne [H (i) , H (i) ] ≤ [G(i) , G(i) ]. Řešitelnost grupy budeme v hlavolamech využívat tak, že se nám jeden těžký úkol rozpadne na několik menších problémů. Konkrétně místo řešení grupy budeme řešit její podgrupy a faktorgrupy. Problém. Řešení podgrupy Vstup: hlavolam (G, B), H ≤ G, h ∈ H ¯ kde b1 b2 . . . bn = h Výstup: b1 , b2 , . . . , bn ∈ B, Problém. Řešení faktorgrupy Vstup: hlavolam (G, B), N ⊳ G, h ∈ G ¯ kde (b1 b2 . . . bn )N = hN Výstup: b1 , b2 , . . . , bn ∈ B, Lemma 3.6. Pro vyřešení hlavolamu (G, B) stačí vyřešit grupu N ⊳ G a grupu G/N . Důkaz. Nechť je zadaný a ∈ G. Vyřešením grupy G/N najdeme prvky g1 , . . . , gn ∈ ¯ tak, že (g1 g2 . . . gn )N = aN . Uvažujme h = (g1 g2 . . . gn )−1 a ∈ N , vyřešeB ¯ tak, že h1 h2 . . . hm = h. Dostáváme ním grupy N najdeme h1 , h2 , . . . , hm ∈ B g1 g2 . . . gn · h1 h2 . . . hm = a, což je hledané řešení hlavolamu.

9

Nechť (G, B) je hlavolam a N ⊳ G. Pro vyřešení hlavolamu stačí vyřešit G/N s generátory bi N (bi ∈ B) a vyřešit grupu N . Najít generátory grupy N je složitější, protože musíme najít množinu postupů, které tuto grupu generují. Tyto postupy je těžké najít obecně, ale stačí je nalézt jen jednou pro daný hlavolam a používat je nezávisle na počátečním stavu. Tyto postupy si můžeme představit jako naučené algoritmy, které je třeba si pro řešení hlavolamu pamatovat. Definice 3.7. Řešením hlavolamu (G, B) podle subnormální řady G = G0 ⊲ G1 ⊲ · · · ⊲ Gn = 1 rozumíme vyřešení faktorgrup Gi /Gi+1 pro všechna i. To podle předchozího lematu stačí k vyřešení hlavolamu (G, B). Úlohu řešení hlavolamu můžeme formulovat takto. Máme zadaný řešitelný stav g ∈ G a množinu generátorů B ⊂ G, hBi = G a hledáme postup b1 b2 . . . bn = g, kde bi ∈ B, i = 1, 2, . . . , n. Obtížnost řešení můžeme měřit podle počtu postupů, které připadají v úvahu. Pro obecnou grupu jsme dokázali, že každý tah jde vygenerovat nejhůře na |G| tahů. Počet různých postupů je tedy |G| X

|B||G|+1 − 1 |B| = . |B| − 1 n=1 n

Tento odhad můžeme výrazně zmenšit, pokud víme, že jde o komutativní grupu. Tam spolu komutují generátory a tedy nezáleží na jejích pořadí v pod2 d2 dn sloupnosti. Všechny prvky grupy Pn pak můžeme vyjádřit postupy b1 b2 . . . bn , kde 0 ≤ di < deg(bi ) a zároveň j=1 dj ≤ |G|. Můžeme udělat dva horní odhady Q na počet takových postupů. Z vlastnosti 0 ≤ di < deg(bi ) dostáváme odhad Pni=1 di jako součin počtu možných mocnin jednotlivých generátorů. Z vlastnosti nj=1 dj ≤ |G| víme, že celkový počet prvků je nejvíce |G|. To si můžeme představit jako když chceme rozdělit |G| předmětů do n+1 přihrádek (jedna přihrádka za každý generátor a jedna za identitu, aby mohlo být generátorů
také méně než |G|). Tím se dostáváme na odhad kombinačním . číslem |G|+n |G| Těchto posloupností bude většinou relativně málo, ale při zvolení velkého počtu generátorů (například celé grupy), jich může být až stejně mnoho jako v obecné grupě. Příklad. Uvažujme jednoduchý hlavolam ve formě číselného zámku s třemi kotouči 3 čísel 0 až 9. Přiřadíme mu grupu Z10 a možné tahy jsou r1 = (1, 0, 0), r2 = (0, 1, 0), r3 = (0, 0, 1). Všechny tahy jsou řádu 10. Máme tedy zadané číslo a pomocí otáčení se chceme dostat do stavu samých nul. Obecnou úvahou získáme 31000 možných 3 postupů, avšak s využitím komutativnosti Z10 dostáváme jen 1000 postupů. Ani tato metoda ale není ideální, protože můžeme přeci skládat kotouče jeden po druhém a tím se dostaneme jen na 10 možných posloupností na každý kotouč, celkem tedy 30. Tomu se budeme věnovat dále. 10

Příklad. Uvažujme opět hlavolam s číselným zámkem. Budeme ho nyní řešit podle subnormální řady 3 2 Z10 ⊲ (1 × Z10 ) ⊲ (12 × Z10 ) ⊲ 13 . 3 2 ∼ Nejdříve vyřešíme faktor Z10 /(1 × Z10 ) = Z10 . V této grupě r1 odpovídá jedničce, r2 a r3 odpovídají nule. Víme, že deg(r1 ) = 10 a generuje celou grupu Z10 , tedy je 10 posloupností, které připadají v úvahu r1i , kde 0 ≤ i < 10. Znamená to vpodstatě, že točíme prvním kotoučem dokud se nedostaneme na nulu. Tím se 2 dostaneme do podgrupy Z10 a musíme najít její generátory. To není těžké, protože to jsou přímo r2 a r3 . 2 Obdobně vyřešíme faktorgrupu Z10 /(1 × Z10 ) a dostaneme se do Z10 s generátorem g3 . Pro tuto grupu je opět jen 10 možných postupů. Celkem jsme tedy potřebovali 30 postupů na složení hlavolamu. Tento počet jde ještě snížit na 21 použitím kompoziční řady 3 2 Z10 ⊲ (Z10 × Z5 ) ⊲ (Z10 × Z52 ) ⊲ Z53 ⊲ (1 × Z52 ) ⊲ (12 × Z5 ) ⊲ 13 .

Aby tato metoda fungovala musíme o stavu umět říct nejen jestli je hlavolam vyřešený, ale musíme být i schopni určit, jestli je v námi definované normální podgrupě. Zde je vidět, že hlavolam se lépe řeší podle subnormální řady, než řešit hlavolam jako celek. Rozložení velkého problému na více menších nám v této úloze výrazně pomáhá. Dále se budeme věnovat řešení řešitelných grup. Mějme zadaný hlavolam (G, B), kde G je řešitelná. Potom existuje subnormální řada, kde jsou všechny faktory abelovské. Řešení hlavolamu se pak redukuje na vyřešení několika menších grup, které jsou navíc komutativní, což je obecně jednodušší. Avšak většina hlavolamů nemá řešitelnou grupu, protože podle věty 3.4 nesmí obsahovat podgrupu A5 . Například obdoba Loydovy patnáctky v rozměru 3x2 (pět kamenů jedno prázdné pole) už nemá grupu řešitelnou. Pro příklad využití řešitelnosti grupy si můžeme vymyslet vlastní hlavolam. Příklad. Uvažujme hlavolam (G, B), kde G = S43 a B = (r, a, b, c), r = ((1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4)), a = ((2, 4), (2, 3, 4), (1, 2, 3, 4)), b = ((1, 2, 3, 4), (2, 4), (2, 3, 4)), c = ((1, 2, 3, 4), (2, 3, 4), (2, 4)). Grupa G je řešitelná, neboť direktní součin řešitelných grup je řešitelný. Hlavolam budeme řešit pomocí komutátorové řady S43 ⊲ A34 ⊲ Z26 ⊲ 1, ta má všechny faktory abelovské. Řešíme nejdříve faktor S43 /A34 ∼ = Z23 , kde tahy r, a, b, c odpovídají postupně (1, 1, 1), (1, 0, 1), (1, 1, 0), (0, 1, 1). Ty zřejmě generují Z23 a mají stupeň 2. Přinejhorším stačí vyzkoušet 16 možností a dostaneme se do podgrupy A34 . Dále řešíme faktor S43 /Z26 ∼ = Z33 . Najdeme nejdříve generátory této grupy, což můžou být například a2 , b2 , c2 , které odpovídají postupně (0, 1, 0), (0, 0, 1), (1, 0, 0). Ty zřejmě generují celou Z33 a mají stupeň 3, což nám dává 27 možností.

11

Nyní jsme v grupě Z26 a hledáme její generátory. To jsou například r−2 c−1 r2 c = (1, 0, 0, 0, 0, 0), r−3 c−1 r2 cr = (0, 1, 0, 0, 0, 0), r−2 a−1 r2 a = (0, 0, 1, 0, 0, 0), r−3 a−1 r2 ar = (0, 0, 0, 1, 0, 0), r−2 b−1 r2 b = (0, 0, 0, 0, 1, 0), r−3 b−1 r2 br = (0, 0, 0, 0, 0, 1). Všechny jsou stupně 2, tedy dostáváme 64 možností.

3.1

Generátory podgrupy

Nyní se věnujme hledání generátorů podgrupy respektive normální podgrupy. K tomu využijeme šikovné lemma, které se používá například i ve Schreier–Simsově algoritmu na hledání silně generující množiny. [6] Věta 3.8. (Schreierovo lemma) Nechť G je grupa, H ≤ G a B ⊂ G, kde hBi = G. Nechť R je pravá transverzála H v G, kde 1 ∈ R. Pro každý prvek g ∈ G definujeme g jako reprezentanta v R množiny Hg, tedy g ∈ Hg. Pak H je generována množinou C = {rb(rb)−1 |r ∈ R, b ∈ B}. Důkaz. Podle definice C ⊂ H. Stačí když dokážeme, že C¯ generuje H. Vyjádřeme C −1 = {rb(rb)−1 |r ∈ R, b ∈ B −1 }. Nechť máme zadané h ∈ H, to můžeme napsat ¯ Budeme definovat posloupnost h0 , h1 , . . . hn tak, jako h = b1 b2 . . . bn , kde bi ∈ B. aby hj = c1 c2 . . . cj rj+1 bj+1 bj+2 . . . bn , kde ci ∈ C¯ pro všechna i ≤ j, rj+1 ∈ R a hj = h. Definujme h0 = 1b1 b2 . . . bn . Dále budeme postupovat rekurzivně, pokud hj je definováno, pak definujme cj+1 = rj+1 bj+1 (rj+1 bj+1 )−1 a rj+2 = rj+1 bj+1 . Potom hj+1 = hj = h a je v požadovaném tvaru, protože hj = c1 c2 . . . cj (rj+1 bj+1 )bj+2 . . . bn = c1 c2 . . . cj (cj+1 rj+2 )bj+2 . . . bn = hj+1 . Tím dostaneme h = hn = c1 c2 . . . cn rn+1 . Protože h ∈ H a c1 c2 . . . cn ∈ hCi ≤ H musí platit rn+1 ∈ H ∩ R = {1}. Tedy h ∈ hCi. Problém. Hledání generátorů podgrupy. Vstup: hlavolam (G, B) a podgrupu H ≤ G. Výstup: množina postupů C ⊂ H tak, že hCi = H. Máme zadaný hlavolam (G, B) a normální podgrupu N ⊳G. Hledáme množinu postupů C, které generují N . Nechť R je transverzála N v G. Schreierovo lemma říká, že C = {rb(rb)−1 |r ∈ R, b ∈ B} generuje N a zároveň nám zaručuje, že ˙ |C| ≤ |G : H||B|. Množinu C pak ještě můžeme zbavit o přebytečné prvky: postupně můžeme z C vyřazovat prvky c ∈ C takové, které lze vyjádřit ve tvaru c = c1 c2 . . . cn , kde ci ∈ C − {c}. 12

Pro tuto metodu hledání generátorů však potřebujeme najít transverzálu R a navíc všechny její prvky vyjádřit posloupností tahů. To je problém ekvivalentní řešení faktorgrupy G/N . Pro každý h ∈ G/N umíme najít b1 b2 . . . bn N = h. Potom b1 b2 . . . bn ∈ G můžeme definovat jako prvek transverzály a zástupce h.

3.2

Algoritmus na řešení řešitelných grup

Ukažme se nyní algoritmus na to, jak vyřešit řešitelnou grupu jen pomocí řešení abelovských grup. Nechť (G, B) je hlavolam a G je řešitelná grupa stupně řešitelnosti n. Pak existuje komutantová subnormální řada G = G0 ⊲ G1 ⊲ · · · ⊲ Gn = 1. Použijeme indukci na Gi podle i. Nechť Gi je řešitelná grupa stupně řešitelnosti n − i a Bi ⊂ Gi množina tahů, které generují Gi . V prvním kroku definujeme G0 = G a B0 = B. V jednom indukčním kroku nejdříve vyřešíme abelovskou faktorgrupu Gi /Gi+1 . Pro každý prvek r této grupy tedy najdeme posloupnost b1 b2 . . . bm N = r, tedy prvek b1 b2 . . . bm je v rozkladové třídě odpovídající r. Transverzálu Ri definujme jako množinu těchto tahů přes všechny prvky faktorgrupy. Nyní pomocí Schreierova lemmatu jednoduše najdeme množinu tahů Bi+1 = {rb(rb)−1 |r ∈ Ri , b ∈ Bi }, které generují Gi+1 . Algoritmus skončí když i = n, neboli když Gn = 1. Tím jsme vyřešili celou řešitelnou grupu.

13

4. Hlavolam IQ 139 Opustíme nyní řešitelné grupy a budeme se zabývat konkrétním hlavolamem. IQ 139 je hlavolam tvaru puku, který má po obvodu 12 dílků a dva středové dílky. Lze otáčet všemi 12-ti dílky dokola a lze otočit celou levou nebo celou pravou polovinu hlavolamu. Všechny dílky mají navíc dvě možné orientace. 2

9

6 12

1

1

11

2

12

8

5

11

3

10

4

9 5

8 7

6

3

4 7

(b) Zamíchaný hlavolam IQ 139

(a) Složený hlavolam IQ 139

4.1

10

Grupa a řešení hlavolamu

Nyní se zaměříme na problém nalezení grupy toho hlavolamu. Obecně to budeme dělat tak, že najdeme nejprve neřešitelné stavy v U a následně dokážeme, že zbytek stavů už je řešitelný. Najdeme univerzum U = (T ⋉ V ) × W = (S12 ⋉ Z212 ) × Z22 a generátory B = r, R, L, kde r = ((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12), 012 , 02 ), R = ((1, 6)(2, 5)(3, 4), (16 , 06 ), (1, 0)), L = ((7, 12)(8, 11)(9, 10), (06 , 16 ), (0, 1)).

7

12

1

8

6

11

2

5

9

3

10

4

10

4

9

3

5

11 12

2

8

6

7

(c) Tah L

1

(d) Tah R

14

Věta 4.1. Grupa řešitelných stavů hlavolamu IQ 139 G je izomorfní s nějakou podgrupou T × W = S12 × Z22 . Důkaz. Dokážeme, že pro ∀t ∈ T, ∀w ∈ W, ∃!v ∈ V tak, že (t, v, w) je řešitelný stav. Mějme zadané t ∈ T , w ∈ W a stav (t, v, w), který lze zapsat jako konečná posloupnost generátorů r, R a L. Sledujme nyní libovolný prvek a ∈ M v této posloupnosti. Označme n jako celkový počet generátorů r a m jako počet R a L, které v posloupnosti prvek a zobrazují na jiný prvek. Paritou na T budeme ztotožňovat s paritou permutace a paritou na W definujeme tak, že (0 × 0) a (1 × 1) jsou sudé a ostatní liché. Generátor r mění paritu T , ale nemění paritu W , zatímco R i L mění paritu obou. Z toho vyplývá, že pokud jsou parity t a w různé, musí být n liché. Navíc víme, že každý generátor započítaný v m a n s prvkem a pohne o lichý počet pozic. Tedy pokud je parita a a p(a) různá, pak m + n je liché, jinak je sudé. Z toho jednoduše určíme paritu m. Otočení prvku a proběhne přesně m-krát a tedy je jednoznačně určená jeho orientace. Věta 4.2. Grupa řešitelných stavů hlavolamu IQ 139 G je izomorfní s T × W = S12 × Z22 2 Důkaz. Mějme zadané t ∈ T , w ∈ W . Definujme {gi }11 i=0 ∈ S12 × Z2 , kde gi = ri Rr−i . Omezíme se prozatím jen na grupu S12 . Dokážeme, že tato posloupnost generuje celou grupu S12 . Generovaná grupa je 3-tranzitivní (to dokážeme v další podkapitole), obsahuje trojcyklus g7 g0 g7 g0 = (1, 8, 6), a obsahuje lichou permutaci g0 , tedy podle lemmatu 2.12 je grupa symetrická. Všechny gi zachovávají shodnost parit v T a W . Pokud jsou tedy parity p a s různé, stačí nazačátku provést tah r, který obrátí paritu jen v T . Tímto postupem se umíme dostat do stavu t × w′ , kde w′ má stejnou paritu jako w. Pokud w 6= w′ , pak se tyto stavy liší jen orientací obou středových dílků a stačí provést postup r6 Lr−6 R = (id, (1, 1)).

Poznámka. Alternativní důkaz, kde není potřeba existence trojcyklu, ale potřebujeme 6-tranzitivitu. Tím je pak podle věty 2.10 symetrická. Nyní se zabývejme problémem samotného vyřešení hlavolamu IQ 139. Zatím jsme dokázali existenci posloupnosti tahů, která generuje každý prvek z S12 × Z22 , nyní budeme hledat konstrukční důkaz. Postup je jednoduchý, protože předchozí důkaz je už konstrukční. Tedy původní permutaci převedeme na složení transpozic, postupně po bereme po dvou transpozice a nahradíme je vhodnými trojcykly, a ty už umíme vygenerovat pomocí 3-tranzitivity a trojcyklu g7 g0 g7 g0 .

4.2

Algoritmus na řešení a nejmenší počet tahů

I když jsme dokázali, že pro každý stav umíme najít tahy tak, abychom hlavolam vyřešili, ale tento postup je pro člověka skoro nemožný na aplikaci. Je zbytečně dlouhý a je těžké na něj vůbec přijít. Proto se budeme zabývat postupy, které jsou kratší a pro člověka lépe zpracovatelné. Pro každý stav určitě existuje nejkratší posloupnost, které ho generuje. Nejdelší z těchto posloupností přes všechny stavy nazveme božské číslo hlavolamu.

15

U hlavolamu IQ 139 navíc nebudeme chtít počítat do délky posloupnosti všechny tahy, protože generátor r můžeme provést vpodstatě v nulovém čase. Stejně tak otočení celého hlavolamu, což můžeme zapsat jako postup RL. Obecně tento jev můžeme definovat tak, že každý generátor má navíc přiřazené číslo, které reprezentuje jeho váhu. Uvedeme zde jeden algoritmus na řešení, který zároveň dokazuje, že božské číslo hlavolamu IQ 139 je menší nebo rovno 57. Nejdříve stabilizujeme dílek 1: jen pomocí tahů r a RL můžeme dostat dílek 1 na své místo, a zároveň aby parita na středové grupě a byla stejná jako parita na permutační grupě. Toto nás nestojí žádný tah, jen si natočíme hlavolam tak, aby se nám s ním dobře pracovalo. Dále budeme používat postupy gi , i = 0, 1, . . . 11, které mají všechny váhu jedna. Postupně stabilizujeme prvky 2 až 6: Postupně dáváme dílky na svá místa a to bez použití tahů, které hýbou s už zafixovanými prvky. Stačí probrat všechny možnosti umístění prvku, který chceme stabilizovat. To znázorňují obrázky, kde čísla značí vzdálenost od původního místa a šedě jsou označeny zafixované prvky. 4

3

2 3

3

2

0

2

3

3

0

2

3

2

2

3

1

3

2 1

2

1

2

2

3

2

3

3

(f) Fixace třetího dílku

(e) Fixace druhého dílku

0

2

(g) Fixace čtvrtého dílku

6

3 1

4 1

4

2

3 0

3 2

2

3

5

0

(i) Fixace šestého dílku

(h) Fixace pátého dílku

Nyní budeme dále stabilizovat prvky v druhé polovině hlavolamu . K tomu budeme používat konjugovaný trojcyklus c = g7 g0 g7 g0 . Potřebujeme nejdřív zjistit, jestli je permutace sudá, když ne, provedeme tah g6 . Na zbytek budou stačit tahy (8, 6, 9) = g8 g10 · c · g10 g8 (8, 6, 10) = g8 · c · g8 (8, 6, 11) = g8 g9 · c · g9 g8 (11, 12, 1) = g10 g8 g1 g5 · c · g5 g1 g8 g10 . 16

Tyto trojcykly navíc můžeme konjugovat pomocí rotací r a nebo dělat jejich inverze. Na stabilizaci prvků 7, 8 a 9 stačí vždy jen jeden z prvních tří trojcyklů, které mají maximálně 8 tahů. Na správné umístění posledních tří použijeme čtvrtý trojcyklus konjugovaný pomocí tahu r. Celkem potřebných tahů je 3 + 3 + 4 + 4 + 6 + 1 + 8 + 8 + 8 + 12 = 57.

17

5. Hlavolamy typu puk Zobecněme nyní hlavolam IQ 139. Představme si hlavolam, kde místo 12 dílků dokola je jich n, kde n je sudé. Generátory budou podobné – rotace, otočení levé části a otočení pravé části. Takovému hlavolamu budeme říkat puk n. Obecně ho můžeme zapsat jako (Pn , B), kde Pn = (Tn ⋉ Vn ) × Wn ≤ Un = (Sn ⋉ Z2n ) × Z22 , Tn je permutační grupa, Vn je grupa orientaci a Wn je grupa středu. Dále B = {r, R, L}, kde r = ((1, 2, . . . , n), 0n , 02 ), n n n n R = ((1, )(2, + 1) . . . (⌊ ⌋, ⌊ ⌋ + 1), (1n/2 , 0n/2 ), (0, 1)), 2 2 4 4 n n n n n L = ((n, + 1)(n − 1, + 2) . . . (n − ⌊ ⌋ + 1, + ⌊ ⌋), (0n/2 , 1n/2 ), (1, 0)). 2 2 4 2 4 Hlavolam IQ 139 pak odpovídá hlavolamu puk 12. Budeme se nyní zabývat problémem hledání grupy těchto hlavolamů. Rozebereme si několik případů podle n. Stejně jako u puku 12 definujme gi = ri Rr−1 ∈ Pn pro 0 ≤ i < n.

5.1

Sudé puky

Puky rozdělujeme na sudé a liché, protože jsou to dvě třídy hlavolamů, které jsou od sebe výrazně odlišné. Sudé puky jsou takové kde n je ve tvaru 4k pro přirozené k. Věta 5.1. Tn je 3-tranzitivní pro n = 4k. Důkaz. Zde budeme generátory hlavolamu uvažovat jen jako permutace, tedy bereme jejich restrikci na grupu Tn . Pro n = 4 je tvrzení zřejmé, protože gi jsou vedlejší transpozice a grupa Tn je tím pádem symetrická. Nechť n > 4. Mějme zadané m1 , m2 , m3 ∈ N a m1 , m2 , m3 ≤ n. Hledáme p ∈ Tn tak, že p(m1 ) = 1, p(m2 ) = 2 a p(m3 ) = 3. Tah r je cyklus délky n, tedy existuje α < n tak, že rα (m1 ) = 1. Definujme m′2 = rα (m2 ). Bez újmy na obecnosti můžeme předpokládat, že ′ m2 > n2 (pokud je dílek m′2 v pravé části hlavolamu, můžeme ho dostat doleva pomocí tahu gm′2 +1 ). Dále postup n n g n2 −1 g n2 = (n, n − 2, n − 4, . . . , , n − 1, n − 3, . . . , + 1) 2 2 tvoří cyklus na prvcích v druhé polovině, tedy od n2 výš. Existuje tedy β < n tak, že n g1 (g n2 −1 g n2 )β (m′2 ) = g1 ( + 1) = 2. 2 Zároveň všechny tyto tahy jsou stabilizátory prvního prvku, takže jsme našli p′ ∈ Pn tak, že p′ (m1 ) = 1 a p′ (m2 ) = 2. Zcela obdobně najdeme permutaci q ∈ Tn tak, že qp′ (m3 ) = 3 a zároveň q fixuje prvky 1 a 2. 18

Poznámka. Touto metodou s použití matematické indukce můžeme dokázat až n -tranzitivnost Tn . 2 Věta 5.2. Tn = Sn pro n = 4k. Důkaz. Z minulé věty víme, že Tn je 3-tranzitivní, dále existuje trojcyklus gn/2+1 g0 gn/2+1 g0 = (1,

n n + 2, ) 2 2

a lichý tah r, tedy podle věty 2.12 je Tn symetrická. Věta 5.3. Pn ≤ Sn × Z22 pro n = 4k. Důkaz. Pro n = 8k + 4 je důkaz stejný jako v hlavolamu IQ 139. Pro n = 8k je důkaz trochu jednodušší, protože L i R zachovávají paritu Sn a tudíž celkový počet rotací má stejnou paritu jako je parita permutace v Sn . Zbytek důkazu probíhá stejně. Věta 5.4. Pn = Sn × Z22 pro n = 8k. Důkaz. Už víme, že tahy r, R, L generují celou grupu Tn = Sn , nyní stačí dokázat, že (id, (0, 1)) ∈ Pn , protože rn/2 Lln/2 R = (id, (1, 1)). Připomeňme, že n n n n R = ((1, )(2, − 1) . . . ( , + 1))(0, 1). 2 2 4 4 Zvolme libovolně permutaci π ∈ Tn , která se dá zapsat jako součin n8 disjunktních transpozic na prvcích větších než n2 . Protože Tn je symetrická, tak je určitě ( n2 )tranzitivní. Pak existuje p, q ∈ Pn tak, že n n n 3n p−1 Rp = ((1, )(2, − 1) . . . ( , + 1) · π))(0, 1), 2 2 8 8 3n n 3n n n n − 1) . . . ( , + 1) · π))(0, 1). q −1 Rq = (( + 1, )( + 2, 8 8 8 8 4 4 Pak dostáváme Rp−1 Rpq −1 Rq = (id, (0, 1)). Věta 5.5. Pn = Sn × Z22 pro n = 8k + 4. Důkaz. Důkaz probíhá stejně jako ve větě 4.2.

5.2

Liché puky

Nyní přejdeme na liché puky, tedy takové kde, n = 4k + 2 pro přirozené k. Věta 5.6. Sn ≥ Tn ∼ = Z2 ⋉f (Sn/2 × Sn/2 ) pro n = 8k + 6. Důkaz. (Sn/2 × Sn/2 ) vnímáme jako všechny permutace na lichých prvcích krát všechny permutace na sudých prvcích. V grupě Z2 vnímáme prvek 1 jako prohození všech lichých a sudých prvků (tedy například stav r). Aby byl semidirektní součin definován správně, musíme definovat f : Z2 → Aut(Sn/2 × Sn/2 ). To uděláme následovně f (0) : (x, y) 7→ (x, y), f (1) : (x, y) 7→ (y, x). 19

Generátory budou pak odpovídat n r = (1, ((1, 2, . . . , ), id)), 2 n+2 n+2 n+2 n+2 )(2, − 1)..., (1, − 1)(2, − 2)...), R = (0, ((1, 4 4 4 4 L = r−n/2 Rrn/2 . Nyní dokážeme, že generátory opravdu generují celou tuto grupu. Nejdříve se jednoduše pomocí tahu r dostaneme do stavu (0, (x, y)). Podle počtu transpozic zjistíme, že tahy R a r−1 Rr jsou liché permutace na jedné grupě a sudé na druhé grupě. Tedy s jejích pomocí se dostáváme do stavu (0, (x′ , y ′ )), kde x′ i y ′ jsou sudé permutace. Pro obě grupy existuje trojcyklus gn/2+1 g0 gn/2+1 g0 respespektive r−1 gn/2+1 g0 gn/2+1 g0 r, který je na druhé identita. Obě grupy jsou navíc 3-tranzitivní. To se dokazuje obdobě jako ve větě 5.1 až na to, že gn/2−1 gn/2 netvoří cyklus délky n2 + 1, ale jen délky n+2 , což však na důkaz stačí. Umíme tedy vytvořit libovolný trojcyklus na 4 jedné z grup a na druhé zůstane vše nezměněno. Tím tedy vygenerujeme celý součin An/2 × An/2 . Věta 5.7. Sn ≥ Tn ∼ = Z2 ⋉f (An/2 × An/2 ) pro n = 16k + 2. Důkaz. Důkaz je totožný s důkazem předchozí věty až na to, že každý generátor je sudý na obou grupách. Nemůžeme tedy na nich dostat žádnou lichou permutaci. Věta 5.8. Sn ≥ Tn ∼ = Z2 ⋉f (Z2 ⋉φ (An/2 × An/2 )) pro n = 16k + 10. Důkaz. Definujme φ(0) : (x, y) 7→ (x, y), φ(1) : (x, y) 7→ ((1, 2) · x, (1, 2) · y). Potom grupa (Z2 ⋉φ (An/2 × An/2 ) je izomorfní s podgrupou (Sn/2 × Sn/2 ), kde je parita obou permutací stejná. Tahem R převedeme do stavu, kdy jsou obě permutace sudé a zbytek důkazu provedeme stejně jako u věty 5.6. Věta 5.9. Z22 ≥ Wn ∼ = Z2 pro n = 4k + 2. Důkaz. Paritou na grupě Z22 rozumíme součet prvků modulo 2. Existuje postup rn/2 Lr−n/2 R = (id, 0n , (1, 1)) ∈ Pn , který generuje grupu sudých prvků Z22 , ta je izomorfní se Z2 . Pro n = 8k + 6 každý z generátorů, který mění paritu na Z22 , zároveň mění paritu na právě jedné z permutačních grup Sn/2 . Tedy pokud (t, v, w) ∈ Pn , tak z prvku t můžeme jednoznačně určit paritu prvku w. Tím se nám grupa Wn redukuje na Z2 . Pro n = 16k + 10 každý generátor, který mění paritu na Z22 , zároveň mění paritu na obou permutačních grupách. Opět Wn ∼ = Z2 . Pro n = 16k + 2 nechť (t, v, w) ∈ Pn . Paritou na Vn rozumíme součet prvků modulo 2. Každý tah, který mění paritu na Z22 , zároveň mění paritu na Vn , tedy pomocí prvku v opět jednoznačně určíme paritu w. 20

′ Věta 5.10. Un ≥ Pn ∼ = ((Z2 ⋉f (Sn/2 × Sn/2 )) ⋉f Z2n−2 ) × Z2 pro n = 8k + 6.

n/2

Důkaz. Označme si grupu Z2 jako grupu orientací lichých důlků hlavolamu. Dokážeme, že orientace jednoho lichého dílku lze jednoznačně určit pomocí permutace hlavolamu a ostatních orientací. Každý generátor, který obrátí paritu na n/2 Z2 , zároveň obrátí paritu permutace na lichých dílcích (pokud n = 16k + 14 tak obrací paritu na permutaci sudých dílků). Tedy z permutace umíme určit n/2 paritu na Z2 a tím pádem pokud známe prvních n2 − 1 prvků, tak umíme zjistit poslední prvek. Obdobně dokážeme pro sudé dílky. Zároveň tuto grupu umíme vygenerovat, protože existuje g n−2 g0 g n2 +1 g0 g n2 +1 g n−2 g n2 +1 g0 g n2 +1 g0 = (id, (1, 0n/2−2 , 1, 0n/2 ), 0) 4

4

a permutační grupa lichých dílků je 2-tranzitivní. Obdobně pro sudé dílky hlavolamu. f ′ můžeme formálně definovat jako f ′ (p) : (o1 , o2 , . . . , on/2−2 ) 7→ (op−1 (1) , pp−1 (2) , . . . , op−1 (n/2−2) ), kde on/2−1 definujme jako součet parit o1 , o3 , . . . , on/2−3 , pl , kde pl je restrikce p na permutační grupu na lichých dílcích hlavolamu, on/2 definujme jako součet parit o2 , o4 , . . . , on/2−2 , pr , kde pr je restrikce p na permutační grupu sudých dílků. ′ Věta 5.11. Un ≥ Pn ∼ = ((Z2 ⋉f Z2 ⋉φ (An/2 × An/2 )) ⋉f Z2n−1 ) × Z2 pro n = 16k + 14.

Důkaz. Nejdříve dokážeme, že orientaci posledního dílku umíme jednoznačně určit pomocí permutace a orientace ostatních dílků. Každý generátor, který mění paritu na Z2n , zároveň obrací paritu obou permutačních grup. Tedy z permutace můžeme určit paritu Z2n a tedy i orientaci posledního dílku. f ′ (p) : (o1 , o2 , . . . , on/2−1 ) 7→ (op−1 (1) , pp−1 (2) , . . . , op−1 (n/2−1) ), kde on/2 definujme jako součet parit o1 , o2 , . . . , on/2−1 a restrikce p na permutační grupu lichých dílků. Nyní chceme dokázat, že tahy generují celou tuto grupu. Z minulé věty víme, že existuje prvek, který jen obrátí orientace dvou dílků hlavolamu, které mají stejnou paritu. Nyní stačí najít prvek, který obrátí orientaci lichého počtu lichých i sudých dílků. Myšlenka: uděláme stav RL a na něm nastavíme permutaci na identitu s tím, že dílkům n+2 a 3n+2 zůstane orientace 1. Víme, že existuje libovolný trojcyklus 4 4 na lichých dílcích, který navíc zachovává paritu orientací na obou sudých i lichých dílcích hlavolamu, protože toto platí pro trojcyklus gn/2+1 g0 gn/2+1 g0 , který používáme s pomocí 3-tranzitivity na generování libovolného trojcyklu. Teď umíme udělat libovolnou sudou permutaci na na obou permutačních grupách a zároveň se zachová parita orientací na sudých i lichých prvcích. Stav RL má sudé obě permutace a zároveň obě parity orientací jsou liché. Věta 5.12. Un ≥ Pn ∼ = ((Z2 ⋉f Z2 ⋉φ (An/2 × An/2 )) ⋉ Z2n ) × Z2 pro n = 16k + 2. Důkaz. Stačí když najdeme prvek, který bude jen obracet orientaci jednoho dílku. Požijeme ideu minulého důkazu, kde pomocí trojcyklů vrátíme permutaci R do identity. Tím dostaneme prvek, kde permutace je identita a parita orientací dílků je lichá. 21

5.3

Hledání řešení

Tímto jsme našli grupy všech hlavolamů typu puk n a nyní se zaměříme na řešení těchto hlavolamů. Tedy pro každý řešitelný stav konstruktivně hledáme posloupnost tahů, která jej generuje. Při dokazování, že jsou stavy řešitelné jsme ale vždy postupovali konstruktivně, stejně jako u hlavolamu IQ 139. Takže všechny hlavolamy typu puk zároveň umíme vyřešit.

22

6. Neregulární hlavolamy Nyní se budeme zabývat hlavolamy, které nejsou regulární. Tedy jsou to takové hlavolamy (G, B, S) kde platí |Ge | > 1. Tedy existuje g ∈ G, g 6= 1, kde g(e) = e. Věta 6.1. Nechť (G, B, S) není regulární hlavolam. Pak |G| > |S|. Důkaz. Definujme funkci f : G → S tak, že f : g 7→ g(e). Tato funkce je jistě na, protože G je tranzitivní. Dále f (Ge ) = e a |Ge | > 1, tedy f není prostá. Tím dostáváme požadované |G| > |S|. Lemma 6.2. Nechť (G, B, S) není regulární hlavolam. Pak |Ge | = |Gs | pro všechna s ∈ S. Důkaz. Pro s ∈ S existuje p ∈ G tak, že p(e) = s. Pak pGe p−1 = Gs a tedy |Ge | = |Gs |. Věta 6.3. Řešení neregulárního hlavolamu (G, B, S) je lehčí než řešení regulárního hlavolamu (G, B). Důkaz. Nejdříve dokážeme, že pokud umíme vyřešit regulární hlavolam, pak je to i řešení neregulárního. Nechť máme zadaný řešitelný stav s ∈ S. V G najdeme g tak, že g(e) = s. Z řešení (G, B) najdeme b1 , b2 , . . . , bn ∈ B tak, že b1 b2 , . . . , bn = g, pak b1 b2 . . . bn (e) = g(e) = s je řešení neregulárního hlavolamu. Nyní ukažme, že v neregulárním hlavolamu pro každý stav s ∈ S vždy existuje řešení, které však neřeší regulární hlavolam. |Gs | > 1, tedy existuje g ∈ Gs tak, že g 6= 1. Pak existuje řešení b1 b2 . . . bn (e) = g(e) = s a zároveň b1 b2 . . . bn 6= id. Řešení obecného hlavolamu (G, B, S) můžeme formulovat tak, že pro dané g ∈ G hledáme b1 , b2 , . . . , bn ∈ B tak, že g −1 b1 b2 . . . bn ∈ Ge . V regulárním hlavolamu platí Ge = {1} a tedy je to přímo ekvivalentní b1 b2 . . . bn = g. V neregulárním hlavolamu pro dané g ∈ G najdeme s ∈ S tak, že g(e) = s. Potom platí b1 b2 . . . bn (e) = s ⇔ gg −1 b1 b2 . . . bn (e) = s ⇔ g −1 b1 b2 . . . bn g ∈ Ge . Příklad. Jako příklad neregulárního hlavolamu můžeme uvést zjednodušený hlavolam IQ 139, kde jednotlivé dílky nejsou očíslované, ale polovina je jich obarvená bíle a druhá je obarvená černě. Úkolem je pak hlavolam dostat do stavu, kdy jsou černé a bílé dílky střídají. Orientaci středu nebudeme brát v úvahu. Stavy si reprezentujeme jako posloupnost nul a jedniček, která je dlouhá 12. Stav e ∈ S je pak (1, 0, 1, 0, . . . , 1, 0). Z řešení IQ 139 víme, že G ∼ = S12 a řešitelné stavy jsou všechny ty posloupnosti, kde je šest jedniček a šest nul. V tomto hlavolamu Gs odpovídá všem permutacím v S12 , které jdou vyjádřit jako složení permutace na černých dílcích a permutace na lichých dílcích, tedy Gs ∼ = S62 .

6.1

Zjednodušování hlavolamů

Každý hlavolam si nějak můžeme zjednodušit podobně jako předchozí příklad. Například u Rubikovy kostky můžeme ignorovat orientaci některých nebo všech dílků. Nebo například můžeme ignorovat pozice a natočení hranových dílků, kde 23

se hlavolam zjednoduší až na Rubikovu kostku 2x2x2. Obecně si takovéto zjednodušení představit tak, že některé prvky hlavolamu přestaneme rozlišovat. U předchozího příkladu jsme přestali rozlišovat všechny liché a všechny sudé dílky a zároveň jsme přestali rozlišovat barvy středu. Tuto vlastnost pak v hlavolamu (G, B, S) můžeme promítnout jako disjunktní rozklad stavů z S, kde v každé množině budou stavy, které nerozlišujeme. Na S zvolme třídy ekvivalence T tak, že r ∼ s ⇔ ∀g ∈ G : g(r) ∼ g(s) a zároveň existují alespoň dva prvky, které jsou ekvivalentní. Označme E jako třídu ekvivalence, kde je prvek e. Pak G působí na množině T a (G, B, T ) je hlavolam, kde E je vyřešený stav. Zároveň však |T | < |S| a jde o lehčí hlavolam, protože vyřešením (G, B, S) vyřešíme i hlavolam (G, B, T ). Nevýhoda takovýchto zjednodušení je, že výsledný hlavolam není nikdy regulární. Tuto třídu ekvivalence standardně najdeme tak, že si nejdřív určíme E, což je množina stavů z S, které chceme v novém hlavolamu pokládat za vyřešené.

6.2

Obtížnost hlavolamů

Pro každý hlavolam bychom chtěli nějak určit, jak je obtížné najít jeho řešení. Ukazuje se, že to není lehký úkol a není jednoznačné měřítko, nebo znak, podle kterého bychom to mohli spolehlivě určit. Zabývejme otázkou jaká vlastnost dělá hlavolam těžkým. Uveďme některé vlastnosti, které zřejmé nejsou dobrým měřítkem obtížnosti. Velikost grupy: Uvažme hlavolam (Zn , {1}), který má grupu velikosti n, ale vyřešit ho je triviální. Počet generátorů: Stejně jako minule můžeme uvažovat (Zn , {1}) a (Zn , Zn ), kde jsou oba extrémy počtu generátorů, ale oba jsou lehké. Božské číslo: Stejný příklad hlavolamu (Zn , {1}), který má božské číslo n2 pro sudé n. Pokud se však budeme zabývat jen permutačními hlavolamy, pak můžeme nalézt docela dobrá měřítka obtížnosti pro člověka. Jde o nejmenší počet tahů na vygenerování permutace, která má skoro všechny body fixní, například trojcyklus nebo transpozice (pokud je v grupě). Pro člověka je totiž lépe představitelné opakované používání těchto tahů. Zároveň tato čísla nám napovídají, jak vyřešit hlavolam rychle. Například u IQ 139 je nejkratší trojcyklus na 4 tahy (g7 g0 g7 g0 ), zatímco transpozice na 11 tahů. Proto v uvedeném algoritmu řešíme IQ 138 pomocí těchto trojcyklů.

24

7. Božské číslo hlavolamu IQ 139 Je možné najít optimálních řešení pro každý stav hlavolamu IQ 139. K tomu účelu jsem si napsal program v jazyku C++. Jde o program, který na vstup dostane stav hlavolamu ve formě posloupnosti čísel jedna až dvanáct, která reprezentuje permutaci hlavolamu. Výstup je pak posloupnost tahů gi , i = 0, 1, . . . , 11, který daný stav vyřeší. Protože hlavolam je vždy stejný a mění se jen vstupní stav, můžeme se některé věci předpočítat dopředu. Rozdělme tedy program na generování a hledání. Generování stačí spustit jen jednou. Nejprve si ještě zjednodušíme práci úvahou o zafixování prvku. Stejně jako v lidské řešení si nejdřív hlavolam nastavíme tak, aby první dílek byl na svém místě a parita středu byla shodná s paritou permutace. Nyní budeme tento prvek fixovat na místě, tedy ostatní dílky budeme vnímat jen jako relativní pozice k tomuto prvku. To můžeme udělat tak, že odstraníme všechny generátory, které tímto prvkem hýbou. Tím se nám také zmenší velikost grupy a tedy rychlost výpočtu. Tato grupa odpovídá grupě stabilizátorů prvního prvku a je to tedy S11 .

7.1

Popis algoritmu pro generování

Obecně jde o algoritmus, který dostane zadanou grupu hlavolamu G a její generátory B a výstup bude soubor, kde každému bytu odpovídá jeden stav G a v něm je hodnota nejmenšího počtu tahů na složení. Konkrétní implementaci hlavolamu IQ 139 a jeho generátorů jsem provedl přímo ve zdrojovém kódu. Algoritmus implemetujeme jako hledání do šířky v orientovaném grafu stavů, kde orientované hrany odpovídají zobrazení stavu (vrcholu) podle jednotlivých generátorů. Začneme ve stavu id, který má nejmenší počet tahů nula a začneme na hloubce h = 0. V každé iteraci projdeme všechny stavy s nejmenším počtem tahů h a na tyto stavy aplikujeme postupně všechny generátory. Pro každý takto získaný stav nastavíme hodnotu h + 1, pokud už není nižší. Nakonec zvedneme hloubku h o jedna. Takto pokračujeme dokud nejsou všechny stavy ohodnocené. To můžeme snadno určit tak, že nenajdeme žádný stav v nějaké hloubce h. Číslo h − 1 pak odpovídá božskému číslu hlavolamu. Tento algoritmus běží v čase O(sgk), kde s je počet všech stavů, g je počet generátorů, k je božské číslo. Předpokládáme-li, že operace skládání je v konstantním čase. Jeho paměťová náročnost je O(s), což je největší překážka pro generování těžších hlavolamů. Pro IQ 139 nám stačí 11! bytů, což je přibližně 38MB, zatímco pro stejný algoritmus na Rubikově kostce dává paměťovou náročnost okolo čtyřiceti bilionů gigabytů.

25

7.2

Popis algoritmu pro hledání

Tento algoritmus dostane zadanou grupu G, množinu generátorů B, vygenerovaný soubor z předchozího algoritmu a počáteční stav s. Vrátit má posloupnost tahů, který tento stav vyřeší. Začneme na stavu s a zjistíme jeho hloubku h. V jedné iteraci zkusíme aktuální stav posunout o všechny možné generátory a vybereme jeden stav, který má menší hloubku h − 1. Jeho existenci nám zaručuje metoda konstrukce. Vypíšeme zvolený generátor b, přesuneme se do stavu b(s) a nastavíme aktuální hloubku na h − 1. Algoritmus skončí, když se dostaneme do stavu id, neboli když je hloubka nula. Časová náročnost nezávisí na počtu stavů, což dělá algoritmus velmi rychlý a proběhne v čase O(gk). Například pro Rubikovu kostku máme g = 18 a k = 20, a to je zanedbatelné vůči počtu stavů s, který má dvacet cifer. [5] Paměťová náročnost je velikost vstupu plus konstanta.

7.3

Výsledky

Počty stavů na jednotlivých hladinách něco vypovídají a struktuře hlavolamu. Z těchto hodnot například můžeme vyčíst maximální počet tahů, na které jde hlavolam složit – jeho božské číslo je 15.

7.4

Modifikace na ostatní hlavolamy

Pokud bychom tento program chtěli využít na řešení jiných hlavolamů je potřeba implementovat grupu hlavolamu, tedy nějaký stavový prostor a mít správně zadefinované operace grupy. Dále musíme umět převádět stav na číslo a zpátky pro ukládání a hledání v souboru. Tato čísla by navíc měla jít za sebou, aby soubor nezabíral víc místa, než je nutné. Musíme také dávat pozor na to, že algoritmus je velice náročný na paměť a grupa velikosti 12! už zabírá přibližně 450MB.

26

Doslov V této práci jsme se zabývali jen základním poznatkům z této široké teorie, mnoho stále zůstává neobjeveno. Další práce, navazující na tuto, by mohli blíže zkoumat zjednodušené neregulární hlavolamy a jejich vztah k hlavolamům původním, nebo například zjistit, jak je na permutačních hlavolamech aplikovatelný SchreierSimsův algoritmus na hledání silně generující množiny [6]. Je také možnost navázat na výzkum hlavolamů odvozených od IQ 139 a například zjistit jejich božská čísla. Otevřenou otázkou také zůstává, co vlastně dělá hlavolam těžkým. Už z úvodu také víme, že je tato oblast matematiky úzce spjata s informatikou. Je jasné, že výpočetní technologie může být silnou důkazovou metodou, ale matematická teorie zase ulehčuje práci při výpočtech. Na některé problémy je potřeba spojit síly z různých oborů, jak ukazuje příběh hledání božského čísla Rubikovy kostky.

27

Seznam použité literatury [1] Dixon, John D a Brian Mortimer. Permutation groups. New York: Springer, c1996, xii, 346 p. ISBN 03-879-4599-7. [2] Drápal, Aleš. Teorie grup: základní aspekty. 1. vydání. Praha: Karolinum, 2000, 207 s. ISBN 80-246-0162-1. [3] Escofier, Jean-Pierre a Brian Mortimer. Galois theory. New York: Springer, 2001, xiv, 280 p. ISBN 03-879-8765-7. [4] Joyner, David. Adventures in group theory: Rubik’s cube, Merlin’s machine, and other mathematical toys. 2nd edition. Baltimore: Johns Hopkins University Press, 2008, xv, 310 p. ISBN 08-018-9013-6. [5] Rokicki, Tomas, Herbert Kociemba, Morley Davidson a John Dethridge. God’s Number is 20. [online]. [cit. srpen 2012]. Dostupné z: http://www.cube20.org/. [6] Seress, Ákos. Permutation group algorithms. New York: Cambridge University Press, 2003, ix, 264 p. ISBN 05-216-6103-X. [7] Štoudek, Martin. Řešitelné grupy. Brno, 2006. http://is.muni.cz/th/106610/prif_b/bcprace_106610.pdf. práce. Masarykova Univerzita, Přírodovědecká fakulta.

Dostupné z: Bakalářská

[8] Tůma, Jiří. Matematické hlavolamy a základy teorie grup. l. vydání. Praha : Mladá fronta, 1988, 246 s. Bakalářská práce. Masarykova Univerzita, Přírodovědecká fakulta.

28