Rubikin kuutio ja permutaatioryhmät

Rubikin kuutio ja permutaatioryhmät

Jyrki Lahtonen, Turun yliopisto, matematiikan laitos

Tässä dokumentissa esittelen jonkin verran permutaatioryhmiksi kutsuttujen matemaattisten objektien teoriaa. Koska tavoitteena on soveltaa teoriaa Rubikin kuution tutkimiseen (ratkaisualgoritmi, tilojen lukumäärän laskeminen), en pyri läheskään kattavaan esitykseen tästä laajasta alueesta. Esitys on varsin tiivis, mutta (etenkin päivitysten jälkeen) toivottavasti sellainen, jota matemaattisesti lahjakas lukiolainen pystyy helposti seuraamaan. Kaikki todistukset ovat helposti löydettävissä Turun yliopiston kahden ensimmäisen vuoden matematiikan kurssien Algebran peruskurssi ja Algebra luentomonisteista. Osan perusteluista olen ottanut mukaan päätekstiin ja osan kerännyt linkkien taakse.

Tarkoitukseni ei ole esittää tai etsiä mahdollisimman nopeaa Rubikin kuution ratkaisumenetelmää. Esitän ainoastaan erään algebrallisen tavan lähestyä tätä pulmaa. Esitetty menetelmä on matematiikalle tyypillinen "Divide and conquer"-algoritmi, joka on valittu nimen omaan algebrallisen luonteensa vuoksi.

Kiitokseni Taneli Huuskoselle ja Valtteri Niemelle. Heidän kanssaan käymäni keskustelut ovat kristalloineet tässä esitettäviä ajatuksia.

Sisällysluettelo

Permutaatioista

Olkoon X jokin äärellinen joukko. Bijektiivistä funktiota f, jolle X on sekä lähtö- että maalijoukko sanotaan joukon X permutaatioksi. Vaaditaan siis, että jokainen joukon X alkio esiintyy tarkalleen yhden alkion kuvana. Funktioita kuvataan usein diagrammeina, joissa nuolet liittävät lähtöjoukon alkiot kuviinsa. Koska permutaation tapauksessa lähtö- ja maalijoukot yhtyvät, on luonnollisempaa piirtää joukko X vain kerran, jolloin jokaisesta alkiosta lähtee ja saapuu tarkalleen yksi nuoli. Ohessa kuva 6 alkion joukon permutaatiosta.

Kuvan oikeanpuoleisesta osasta huomataan, että permutaatiota kuvaavat nuolet muodostavat sulkeutuvia ketjuja. Tällaisia ketjuja kutsutaan sykleiksi. Jos syklissä on n kappaletta nuolia (tai alkioita), sanotaan sitä lyhyesti n-sykliksi.

Ylläolevan tapaiset diagrammit vievät paljon tilaa. Kompaktimpaan esitykseen pääsemiseksi nimetään (numeroidaan) joukon X alkiot luvuilla 1,2, jne. Tällöin funktio f voidaan kuvata lyhyesti vektorina, jossa luetellaan kuvat f(1), f(2), jne. Algebrassa käytetään yleensä vektorimerkinnän asemasta syklimerkintää, jossa sulkuihin kirjoitetaan peräkkäin sykliin kuuluvat alkiot nuolten kulkusuunnan määräämässä järjestyksessä. Permutaatiota vastaa tällöin sulkulauseke, jossa sulkujen lukumäärä on sama kuin ko. permutaation syklien lukumäärä. Huomaa, että tällainen sykliesitys ei ole tarkkaan ottaen yksikäsitteinen, sillä syklien aloituskohdat voidaan valita vapaasti. Esimerkiksi 3-syklit (123) ja (231) molemmat tarkoittavat permutaatiota, jossa ykkönen kuvautuu kakkoseksi, joka puolestaan kuvautuu kolmoseksi, joka lopulta kuvautuu takaisin ykköseksi. Alla on esitetty äskeisen 6 alkion joukon permutaatio vektori- ja syklimerkintää käyttäen. Yleensä tehdään sopimus, ettei 1-syklejä merkitä lainkaan näkyviin. Poikkeuksen tälle muodostaa pelkästään 1-sykleistä koostuva ns. identiteettipermutaatio, jolle jätetään näkyviin yksi 1-sykli, esimerkiksi (1).

Kun tarkastellaan permutaation vektoriesitystä, huomataan että siinä jotkin lukuparit ovat "väärässä järjestyksessä" eli isompi luku esiintyy vektorissa ensin. Esimerkkipermutaatiossamme tällaisia käännettyjä pareja on kolme kappaletta. Käännettyjen parien lukumäärä sinänsä ei ole kovin mielenkiintoinen käsite, sillä se riippuu alkioiden numeroimisjärjestyksestä. Numerothan esiintyvät tarkastelussa vain joukon X alkioiden "nimilappuina". (Esimerkkinä voit todeta, että jos yo. kuvassa vaihdetaan alkioiden 1 ja 5 nimilaput keskenään, niin käännettyjen parien määrä nousee kolmesta kolmeentoista.) Tärkeää on, että käännettyjen parien pariteetti (parillinen vai pariton) on numerointijärjestyksestä riippumaton. Tämä seikka todistetaan mm. Turun yliopiston Algebran peruskurssilla. Permutaatiota sanotaankin parilliseksi tai parittomaksi riippuen siitä, onko sen käännettyjen parien lukumäärä parillinen vai pariton luku. Yllä mainitun tuloksen nojalla permutaation pariteetti on hyvin määritelty käsite, eli ei riipu käytetystä alkioiden numerointitavasta. Lukija voi harjoitustehtävänä todeta, että n-sykli (tai pikemminkin permutaatio, jossa on yksi n-sykli ja jossa loput alkiot pysyvät paikallaan, eli kuuluvat 1-sykliin) on parillinen, jos n on pariton ja päinvastoin.

Permutaatioryhmistä

Yleistä

Tunnetusti bijektion käänteiskuvaus on niin ikään bijektio. Samoin kahdesta joukon X bijektiosta voidaan muodostaa kolmas annettujen bijektioiden kuvaustulona eli kompositiona. Käytetään joukon X kaikkien permutaatioiden joukosta merkintää S(X). Olkoon G joukon S(X) epätyhjä osajoukko. Joukolla G voi olla sellainen ominaisuus, että sen alkioiden kompositiot kuuluvat myös joukkoon G. Tällöin sanotaan, että G on permutaatioryhmä. Jos G on permutaatioryhmä, niin sen alkioiden käänteiskuvaukset myös kuuluvat joukkoon G. Todistus.

Nähdään, että esimerkiksi koko S(X) on permutaatioryhmä. Jos X on lukujen 1,2,3,...,n muodostama joukko, käytetään lyhennysmerkintää Sn. Koska n alkiota voidaan kirjoittaa n! eri järjestyksessä, tämän ryhmän alkioiden määrä on n!. Permutaatioiden kertolasku on näin tavallista funktioiden yhdistämistä. Koska yleensä funktioiden kompositiomerkinnässä (esimerkiksi f o g) viimeksi kirjoitettua funktiota sovelletaan ensin, on muistettava, että permutaatioidenkin tuloa on luettava "oikealta vasemmalle". Siis esimerkiksi ryhmässä S4

Jälkimmäistä esimerkkiä voidaan yleistää toteamalla, että syklin käänteispermutaatio (=käänteisfunktio) saadaan yksinkertaisesti kirjoittamalla syklissä esiintyvät alkiot käänteisessä järjestyksessä. Nuolikuviosta tämä on erityisen ilmeistä.

Voidaan ajatella parilliset permutaatiot plusmerkkisiksi ja parittomat miinusmerkkisiksi. Tällöin voidaan helpohkosti (TY, Algebran peruskurssi) todistaa seuraava luonnollisen tunteinen tulos.

Tulosääntö

Näiden tulosten ja aiemman syklien pariteettia koskevan havaintomme perusteella saadaankin usein kätevä sääntö syklimerkinnällä esitetyn permutaation merkille: permutaatio on parillinen tarkalleen silloin, kun sen sykliesityksessä on parillinen määrä parillisen pituisia syklejä. Näin esimerkiksi kahden 4-syklin tulo on parillinen kun taas 2-syklin, 3-syklin, 4-syklin, 5-syklin ja 6-syklin tulo on pariton.

Tulosäännöstä nähdään heti, että joukon X parilliset permutaatiot muodostavat permutaatioryhmän Alt(X), niin sanotun alternoivan ryhmän. Jos X on joukko 1,2,...,n, käytetään merkintää An. Lukijalle harjoitustehtäväksi jätetään sen osoittaminen, että kaikista permutaatioista tasan puolet on parillisia ja toinen puoli parittomia. Ryhmässä An on siis n!/2 alkiota.

Yllä jo näimme, miten parillinen permutaatio (12)(34) voitiin esittää 3-syklien tulona. Voidaan osoittaa, että itse asiassa jokainen parillinen permutaatio voidaan esittää 3-syklien tulona. Todistus.

Yksi keskeinen permutaatioryhmiä koskeva keskeinen seikka on, että ryhmä Alt(X) on ns. yksinkertainen ryhmä, jos joukossa X on ainakin 5 alkiota. Rubikin kuutiota ratkottaessa ei tällä muutoin tärkeällä tuloksella ole merkitystä. Tästä kuitenkin viime kädessä johtuu, ettei viidettä ja sitä korkeampaa astetta oleville yhtälöille voida johtaa algebrallista ratkaisukaavaa. Lisätietoja näistä aiheista saat osallistumalla algebran kurssille.

Konjugointi

Jos s ja t ovat joukon X permutaatioita, niin permutaation s t s-1 sanotaan muodostetun konjugoimalla permutaatiota t permutaatiolla s. Meidän kannaltamme tärkeää on havaita, että konjugointi säilyttää syklirakenteen, toisin sanoen permutaatiossa t ja sen konjugaateissa esiintyvät yhtä pitkät syklit: konjugoitu permutaatio s t s-1 operoi alkioihin kuten alkuperäinenkin permutaatio t, mutta konjugoiva permutaatio s on ensin vaihtanut alkioiden "nimilappuja/numerointia". Oheinen kuva valaisee tätä seikkaa 3-syklin tapauksessa. Kuvassa s ja sen käänteiskuvaus on kuvattu normaalina nuolikuviona, jossa lähtö ja maalijoukko on erotettu. Konjugoitava 3-sykli t sen sijaan on kuvattu syklinä joukon X vasemmalta lukien toisessa kopiossa. 1-syklit on jätetty merkitsemättä. Kuvan harmaat nuolet esittävät "mielivaltaisten" 3-syklin ulkopuolisten alkioiden kuvautumista.

Kommutaattorit

Sanomme, että permutaatiot s ja t kommutoivat, jos niiden kuvaustulo ei riipu tekijöiden järjestyksestä, eli st = ts. Aiemmin näimme, että 3-syklit (123) ja (124) eivät kommutoi, koska (123)(124)=(13)(24) ja (124)(123)=(14)(23). Tyypillinen tilanne (ei kuitenkaan ainoa), jolloin s ja t kommutoivat, on sellainen, missä s ja t liikuttavat eri alkioita. Tällöin joukko X voidaan jakaa kahtia osiin A ja B siten, että s pitää kaikki osan B alkiot paikallaan ja t pitää kaikki osan A alkiot paikallaan. Esimerkiksi ryhmässä S5 permutaatiot s=(123) ja t=(45) kommutoivat:

(123)(45)=(2,3,1,5,4)=(45)(123).
Tässä osa A on joukko {1,2,3} ja osa B joukko {4,5}.

Jos permutaatiot s ja t eivät kommutoi, niin epäkommutatiivisuuden määrää voidaan "mitata" laskemalla niiden kommutaattori [s,t]=sts-1t-1. Helposti nimittäin nähdään, että [s,t] on identiteetti kuvaus, tarkalleen silloin kun s ja t kommutoivat.

Millaisia kommutaattoreita tarvitsemme? Muutetaan äskeistä kommutoivaa tilannetta minimaalisesti siten, että t pitää osan A alkiot paikallaan ainoastaan yhtä (sanokaamme x) lukuun ottamatta. Oletetaan lisäksi, että s ei pidä alkiota x paikallaan. Tilanne on siis oheisen kuvan mukainen. Kuvan harmaa katkoviiva erottaa osat A ja B toisistaan.

Osoittautuu, että tällöin kommutaattori [s,t] on 3-sykli (x s(x) t(x)). Seuraavassa taulukossa on laskettu, miten kommutaattori kuvaa näitä kolmea alkiota - kullakin vaakarivillä on rivin ensimmäisenä mainitun alkion kuvautuminen kommuttaattorin neljässä vaiheessa:

t-1 s-1 t s
x t-1(x) t-1(x) x s(x)
s(x) s(x) x t(x) t(x)
t(x) x s-1(x) s-1(x) x

Tämä tulee jatkossa olemaan tärkeä tapa tuottaa 3-syklejä.

Rubikin kuutio

Yleistä

Rubikin kuutio on 80-luvun alussa markkinoille tullut unkarilaisen insinöörin Ernö Rubikin kehittämä kohtuullisen vaativa pulmapeli. Siinä on kuutio jaettu joka suuntaan kolmeen eri kerrokseen, joita kutakin voidaan kiertää muista riippumattomasti. Näin kuution kaikki kuusi sivua jakautuvat yhdeksäksi ruuduksi, jotka alkutilanteessa ovat kaikki samanvärisiä. Alla on kuva tällaisesta sekoittamattomasta kuutiosta. Kuvan vasemmassa osassa on esitetty kolme etualalla olevaa kuution sivua ja oikealla kolme taustalla olevaa sivua ikään kuin etualan sivut olisi poistettu. Tässä kuutiossa vastakkaisten sivuparien värit ovat siis punainen ja musta, valkoinen ja keltainen, sininen ja vihreä. Myynnissä olleissa kuutioissa esiintyi muitakin väriyhdistelmiä. Itse värit eivät ratkaisualgoritmin kannalta tietenkään ole olennaisia - ainoastaan eriväristen sivujen suhde toisiinsa (mitkä värit ovat vastakkaisilla sivuilla, mitkä kolme yhtyvät jossakin kuution kärjessä jossakin tietyssä järjestyksessä jne).
Alkutilanne:

Kuution erisuuntaisia kerroksia kiertämällä tuon yksivärisen alkutilanteen saa sekoitettua varsin nopeasti tunnistamattomaksi värien sekamelskaksi. Pulmapelin ideana on palauttaa sekoitettu kuutio yllä kuvattuun alkutilaan. Koska kuution osat voivat olla toisiinsa nähden yli 43 triljoonassa eri asennossa, on selvää, että satunnaisella kuution kääntelyllä onnistumismahdollisuudet ovat häviävän pienet.

Kuvassamme kuutio on asennossa, jossa edessä on valkoinen sivu, ylhäällä punainen ja oikealla sininen. Mitään olellista ei tapahdu, jos käännämme koko kuution sellaiseen asentoon, jossa edessä on punainen sivu, ylhäällä keltainen (alkuperäinen takasivu) ja oikealla sininen. Matemaattiselle kielenkäytölle tyypillisen tapaan kutsumme kahta tällaista kuution tilaa, jotka saadaan toisistaan koko kuutiota kääntämällä ekvivalenteiksi . Tällöin siis kuution osien keskinäinen asento ei muutu, ainoastaan katselemme kuutiota eri suunnasta. Jos emme pidä kuution ekvivalentteja tiloja eri tiloina, voimme olettaa, että sivujen keskellä olevat ruudut pysyvät koko ajan paikallaan ja tavallaan näin määräävät koko sivun värin (pyrkimyksenähän on yksivärinen sivu). Jos olet joskus purkanut Rubikin kuution osiinsa, vakuuttunet helposti siitä, etteivät nämä keskiruudut itse asiassa koskaan liiku! Tarkoituksenmukaisuussyistä alla kuvattujen siirtosarjojen aikana joskus keskiruutujenkin värit vaihtuvat, mutta tähän olen turvautunut ainoastaan siksi, että kulloinkin "oleelliset" tapahtumat olisivat etualalla.

Perussiirtoja

Kuution erisuuntaisia kerroksia voidaan kutakin kääntää neljänneskierros kahteen eri suuntaan. Jatkoa varten olen nimennyt tietyt tällaiset siirrot kuvaavilla nimillä: etumyota, etuvasta, oikeaalas, oikeaylos, keskialas, keskiylos, vasenalas, vasenylos, kansiplus, kansimiinus, valiplus, valimiinus, pohjaplus, pohjamiinus. Ohessa kuvia näistä siirroista:

Käytän jatkossa siirtosarjoista merkintää, jossa lainausmerkkien sisällä on pilkuilla erotettuna yllä mainittuja perussiirtoja. Tässä yhteydessä (päinvastion kuin permutaatioista puhuttaessa) on luonnollista lukea siirtosarjaa vasemmalta oikealle.

Yllä kuvattu ekvivalenssi tarkoittaa nyt esimerkiksi sitä, että alkutilanteeseen voimme yhden siirron siirtosarjan "keskiylos" asemesta tehdä siirtosarjan "vasenalas,oikeaalas" - näiden siirtosarjojen vaikutus kuution osien keskinäisiin suhteisiin on sama. Käännä mielessäsi siirtosarjan "keskiylos" jälkeen koko kuutiota neljänneskierros siten, että yläsivu tulee etusivuksi - kuutio näyttää tarkalleen samalta kuin siirtosarjan "vasenalas,oikeaalas" jälkeen. Näin voimme teoriassa luopua sivujen keskiruutuja liikuttavista perussiirroista. Usein saadaan kuitenkin selkeämpi kuva siirtosarjasta, jos siihen ei tarvitse sisällyttää koko kuution kääntämistä = katselukulman vaihtoa.

Rubikin kuution permutaatioryhmät

Kuutiossa on useita erityyppisiä osia: 54 ruutua (9 kullakin sivulla), 6 sivun keskiruutua (1 kullakin sivulla), 8 kärkipalaa (pala, josta on näkyvissä 3 eriväristä ruutua) ja 12 särmäpalaa (pala, josta on näkyvissä 2 eriväristä ruutua). Perussiirrot permutoivat nyt sitten kutakin tyyppiä olevia osia (ruutuja, kärkiä ja särmiä). Selvästikään särmä- ja kärkipalat eivät koskaan voi sekoittua keskenään, eli kärkipala ei koskaan siirry särmäpalan paikalle tai päinvastoin. Rajoituksetta voimme olettaa tekevämme kuutioon vain keskiruudut paikallaan pitäviä perussiirtoja etumyota, etuvasta, takamyota, takavasta, oikeaalas, oikeaylos, vasenalas, vasenylos, kansiplus, kansimiinus, pohjaplus ja pohjamiinus - muut perussiirrothan saatiin näitä kombinoimalla ja katselukulmaa vaihtamalla.

Sanomme kunkin sivun keskiruudun värin määräävän kyseisen sivun värin. Edelleen sanomme kärki- tai särmäpalan olevan oikeassa paikassa, jos se on ruutujensa väristen sivujen leikkauksessa. Edelleen sanomme kärki- tai särmäpalan olevan oikeassa paikassa ja oikeassa asennossa, jos se on oikeassa paikassa, ja jos sen jokainen ruutu on oikeanvärisellä sivulla. Oheisessa kuvassa kuutio on tilassa, jossa kaikki kärki- ja särmäpalat ovat oikeilla paikoillaan, mutta etusivun kaksi kärkipalaa ja yläkerroksen kaksi särmäpalaa ovat väärissä asennoissa. Myöhemmin näemme, että tähän tilanteeseen itse asiassa päästään alkutilanteesta tietyllä siirtosarjalla.

Jos perussiirtojen avulla saadaan aikaan kuution osien permutaatiot s ja t, niin suorittamalla vastaavat siirtosarjat peräkkäin (ensin t, sitten s) saadaan permutaatio st. Näin ollen mahdollisten siirtosarjojen antamat permutaatiot muodostavat permutaatioryhmän, jota kutsumme Rubikin ryhmäksi G(Rubik). Rubikin ryhmä muodostuu tässä kuution 54 ruudun joistakin permutaatioista, joten G(Rubik) on näin ajateltavissa ryhmän S54 osajoukoksi. Edelleen siirtosarjaa vastaavan permutaation s käänteispermutaatio s-1 saadaan "käännetystä siirtosarjasta" eli peruuttamalla tehdyt perussiirrot käännetyssä järjestyksessä. Esimerkiksi, jos permutaatio s saadaan siirtosarjalla "etumyota,oikeaalas,kansiplus", niin siirtosarja "kansimiinus,oikeaylos,etuvasta" antaa permutaation s-1. Koska kyse on viime kädessä funktioiden yhdistämisestä, tämä vastaa koulumatematiikasta tuttua yhdistetyn funktio käänteisfunktion lauseketta

(f g)-1= (g-1)(f-1),
jossa tapahtuu vastaava yhdistettävien funktioiden järjestyksen kääntyminen.

Usein on hyödyllistä tarkastella vain sitä, miten Rubikin ryhmän permutaatiot liikuttavat kokonaisia paloja ja unohtaa näiden palojen asennot (ts. ei välitetä siitä, miten yksittäiset ruudut liikkuvat). Tällöin saamme ryhmän G(paikat), jonka voidaan ajatella olevan ryhmän S(kärjet ja särmät)=S20 osajoukko (20 paikkaa = 8 kärkeä + 12 särmää). Tällöin kuitenkin olemme hukanneet informaatiota - emme tiedä enää mitään palojen asennosta. Palojen asentoja voimme myös kuvata permutaatioryhmällä G(asennot), joka muodostuu sellaisista Rubikin ryhmän permutaatioista, jotka jättävät kaikki kärki- ja särmäpalat oikeille paikoilleen, mutta mahdollisesti vääriin asentoihin.

Ryhmä G(asennot) on selvästi Rubikin ryhmän osajoukko. Voimme todistaa, että G(asennot) on Rubikin ryhmän normaali aliryhmä. Ryhmien G(Rubik) ja G(paikat) suhde sen sijaan on hieman mutkikkaampi. Matematiikassa tähän samojen permutaatioiden eri tarkastelutapoihin liittyvä informaation menetys vastaa tekijäryhmän käsitettä. Itse asiassa meidän kolmea permutaatioryhmäämme sitoo toisiinsa relaatio

G(Rubik)/G(asennot)=G(paikat).
Tämä suhde sisältää lähinnä sen yksinkertaisen asian, että kuution tila määräytyy täysin, kun tunnetaan särmä- ja kärkipalojen paikat ja asennot. Rubikin kuution kannalta tällä suhteella on se merkitys, että kuution tilojen lukumäärä saadaan ryhmän G(paikat) permutaatioiden lukumäärän ja ryhmän G(asennot) permutaatioiden lukumäärän tulona.

Ratkaisualgoritmi

Karkea algoritmi

Tarkastellaan ensin yleisiä suuntaviivoja, eli sitä minkälaisia vaiheita ryhmäteoreettisessa algoritmissamme voisi olla. Lähtötilannehan on jokin Rubikin ryhmän permutaatio. Esiteltävän algoritmin ideana on jatkuvasti tehdä siirtosarjoja, joiden jälkeen kuution tilaa kuvaava permutaatio kuuluu aina pienempään ja pienempään Rubikin ryhmän aliryhmään.

Algebrallisesti (vaan ei visuaalisesti) on luontevaa yrittää ensin huolehtia siitä, että palat ovat oikeilla paikoillaan (mutta eivät välttämättä oikeissa asennoissa), eli ensin haluamme palauttaa annetun Rubikin ryhmän permutaation aliryhmän G(asennot) permutaatioksi. Toinen mahdollisuus (algoritmin etenemisen visuaalisen hahmottamisen kannalta jopa parempi) olisi keskittyä ensin esimerkiksi kärkipaloihin ja sitten särmäpaloihin.

Jaamme algoritmin karkeasti viiteen eri vaiheeseen:

Jos haluamme ensin viedä kärkipalat oikeille paikoilleen ja oikeihin asentoihinsa, ja vasta sitten keskittyä särmäpaloihin, niin vaihdamme vain vaiheiden 3 ja 4 järjestyksen. Alla esitetty tapa suoriutua näistä vaiheista on sellainen, etteivät nämä vaiheet häiritse toisiaan (esimerkiksi särmäpalojen siirtäminen oikeille paikoilleen alla kuvatulla tavalla ei johda kärkipalojen kääntymiseen pois oikeista asennoista).

Näistä ensimmäinen vaihe on helppo toteuttaa. Näemme nimittäin heti, että ryhmässä G(paikat) on ainoastaan parillisia permutaatioita. Tämä johtuu siitä, että perussiirrot vastaavat ryhmässä kahden 4-syklin tuloa (yksi 4-sykli permutoi kärkipaloja ja toinen särmäpaloja). Näin ollen kuution jokaisessa mahdollisessa tilassa kärkipalojen paikkoihin ja särmäpalojen paikkoihin on joko molempiin kohdistunut parillinen permutaatio tai molempiin pariton permutaatio sen mukaan, onko perussiirtoja tehty alkutilanteesta lähtien parillinen vai pariton määrä. Jos siis kärkipaloihin ja särmäpaloihin on kohdistunut pariton permutaatio, tekemällä minkä tahansa sivujen keskiruudut paikallaan pitävän perussiirron pääsemme haluttuun tilanteeseen.

Tärkeitä siirtosarjoja

Algoritmimme muut vaiheet perustuvat kukin yhden vakiosiirtosarjan ja sen konjugaattien käyttöön. Alkuosan teorian nojalla mikä tahansa parillinen permutaatio voidaan tuottaa 3-syklien avulla, joten on luonnollista etsiä paikkojen 3-syklejä. Nämä on alla tuotettu sopivina kommutaattoreina ryhmäteoreettissä osiossa esitellyllä tavalla. Hyvin samanhenkisten kommutaattorien avulla löydämme helposti siirtosarjat, jotka kääntävät kahta vierekkäistä särmäpalaa paikoillaan tai kahta vierekkäistä kärkipalaa - toista myötäpäivään toista vastapäivään. Myöhemmin osoitamme, että näiden siirtosarjojen avulla saamme tuotettua kaikki ryhmän G(asennot) permutaatiot. Näin tuleekin algoritmimme valmiiksi.

Kärkipalojen 3-sykli

Havaitaan, että esitetty siirtosarja on itse asiassa aiemman esimerkin mukainen kommutaattori. Joukon A roolin ottaa tässä kuution ylin kolmannes ja kaksi alempaa kolmannesta muodostavat joukon B. Kuvan siirtosarjan viimeinen siirto "kansimiinus" ottaa vastaa permutaatiota s, ja sitä edeltävien 3 siirron sarja "oikeaalas,pohjamiinus,oikeaylos" permutaatiota t. Nyt s-1 on siirtosarja "kansiplus" ja t-1 on siirtosarja "oikeaalas,pohjaplus,oikeaylos". Huomaamme, että siirtosarja t jättää kuution ylimmän kolmanneksen koskemattomaksi oikean etuyläkärjen palaa lukuun ottamatta. Oletuksemme ovat siis voimassa, ja tiedämme siirtosarjaa [s,t] tekemättäkin sen antavan 3-syklin. Heuristinen perustelu tälle saadaan esimerkiksi seuraavasta löyhähköstä ajatuskulusta: Aluksi sekoitamme kuutiota siten, että ylimmästä kolmanneksesta vain yksi kärkipala vaihtuu ja muut palat pysyvät oikeilla paikoilla oikeissa asennoissa. Kuution 2 alinta kerrosta voivat tässä sekoittua hyvinkin perusteellisesta. Sitten kierrämme kuution yläkertaa neljänneskierroksen, jolloin vaihtunut kärkipala siirtyy yläkerran toiseen kärkeen ja sen tilalle tulee yläkertaan "kuuluva" kärkipala. Seuraavaksi peruutamme aluksi tekemämme sekoitussiirrot (käänteisessä järjestyksessä, jotta peruutus tapahtuisi oikein!), jolloin kuution alimman kahden kerroksen sekoittuminen palautuu alkutilaan muilta osin, mutta yläkerrasta tähän siirto sarjaan osallistuu nyt "väärä" pala, ja näin ollen kahdessa alimmassa kerroksessa on nyt 1 virheellinen kärkipala - muut osat ovat alkutilanteen mukaisessa järjestyksessä. Lopuksi peruutamme myös ylimmän kerroksen kierron ja saamme 3-syklin, johon osallistuvat yläkerrasta aluksi korvattu kärkipala x, sen paikalle alun siirtosarjassa tullut alakerran kärki t(x) sekä sen paikalle yläkerran kierrossa tullut kärki s(x).

Kaikenkaikkiaan tämä siirtosarja on

[s,t]="oikeaalas,pohjaplus,oikeaylos,kansiplus,oikeaalas,pohjamiinus,oikeaylos,kansimiinus"
Huomaa, että koska siirtosarjaa (päinvastoin kuin permutaatiota) luetaan vasemmalta oikealle, tehdään tuossa ensin t-1 (3 siirtoa) sitten s-1 (1 siirto) sitten t (3 siirtoa) ja lopuksi s (1 siirto).

Särmäpalojen 3-sykli

Tämä siirtosarja on niin ikään nähtävä kommutaattorina [s,t], missä kuten edellisessä siirtosarjassa s="kansimiinus" ja t="etumyota,valimiinus,etuvasta". Siirtosarja t (kuten myös t-1) jättää kuution ylimmän kolmanneksen koskemattomaksi yhtä särmäpalaa lukuun ottamatta, joten yleisen tuloksemme nojalla saamme 3-syklin siirtosarjalla
[s,t]="etumyota,valiplus,etuvasta,kansiplus,etumyota,valimiinus,etuvasta,kansimiinus"

Kahden kärkipalan kierrot

Tämäkin siirtosarja on konstruoitu kommutaattorina. Ensimmäiset kuusi siirtoa antavat permutaation t-1, joka jättää kuution ylimmän kolmanneksen koskemattomaksi lukuun ottamatta etusivun oikeanpuoleista yläkärkeä, joka on kiertynyt paikallaan 120 astettta, kaksi alinta kerrosta menivät tietenkin sekaisin. Sitten on tehty yläkerran kierto s-1. Kun seuraavaksi peruutetaan aluksi tehty siirtosarja (vastaten permutaatiota t), niin kaksi alinta kerrosta palautuvat alkutilaan ja oikeassa etuylänurkassa nyt oleva kärkipala kiertyy paikallaan 120 astetta vastakkaiseen suuntaan. Kun lopuksi kumotaan yläkerran kierto, on haluttu siirtosarja [s,t] valmis.

Kahden särmäpalan kääntö

Tämäkin siirtosarja on kommutaattori. Se eroaa kärkipalojen kierron antavasta siirtosarjasta ainoastaan siirtosarjan t osalta. Tällä kertaa t-1 on seitsemän siirron sarja, joka jättää yläkerran entiselleen oikeanpuoleista särmäpalaa lukuun ottamatta ja kääntää tuon särmäpalan paikallaan. Kuten aiemmin, kuution yläkerran kierron s ja siirtosarjan t kommuttaatori [s,t] on haluttu siirtosarja.

Algoritmin vaiheet 2 - 5

Vaihe 2 - kärkipalat paikoilleen

Vaiheen 1 jälkeen tiedämme, että kärkipalojen paikkoihin on kohdistunut parillinen permutaatio. Tämä permutaatio saadaan 3-syklejä kombinoimalla. Yksi systemaattinen tapa valita seuraavaksi tehtävä 3-sykli on seuraava: Olkoon A jokin väärässä paikassa oleva kärkipala. Tällöin palan A oikealla paikalla on kärkipala B, joka ei tietenkään myöskään ole oikealla paikallaan. Jos A ja B olisivat ainoat väärillä paikoilla olevat kärkipalat, niin kärkipaloihin olisi kohdistunut 2-sykli (AB), mikä on pariton permutaatio. Näin ollen on olemassa kärkipala C (eri kuin A ja B), joka on väärässä paikassa. Jos teemme 3-syklin (ABC), niin sen seurauksena kärkipala A siirtyy oikealle paikalleen, eikä yhtään oikealla paikalla olevaa kärkipalaa siirry väärälle paikalle. Näin ollen oikealla paikalla olevien kärkipalojen lukumäärä kasvaa 3-syklin (ABC) seurauksena. Toistamalla prosessia riittävän monta kertaa, saame lopulta kaikki kärjet oikeille paikoilleen.

Mutta mutta? Pystymmekö välttämättä toteuttamaan minkä tahansa kärkipalojen 3-syklin. Aiemmin kuvattu esimerkki toimii siinä tapauksessa, että 3-sykliin osallistuvat kärkipalat ovat kaikki samalla sivulla (helposti näet, että tällöin kuutiota kääntelemällä saat halutut 3 kärkipalaa etusivun kuvattuihin kärkiin). Muut kärkien 3-syklit saadaan kuitenkin kuvattua 3-sykliä konjugoimalla: Jos esimerkiksi haluamme tehdä 3-syklin, johon osallistuvat etusivun vasen yläkärki, etusivun oikea alakärki ja takasivun oikea yläkärki, niin ennen kuvattua siirtosarjaa [s,t] teemmekin siirtosarjan g="pohjamiinus,oikeaalas", jolloin siirrossa "pohjamiinus" etusivun oikea alakärki siirtyy etusivun vasemmaksi alakärjeksi, ja siirrossa "oikeaalas" takasivun oikea yläkärki siirtyy etusivun oikeaksi yläkärjeksi. 3-syklin [s,t] jälkeen sitten lopuksi peruutamme tehdyt siirrot sarjalla g-1. Kaiken kaikkiaan tämä 3-sykli saadaan siis permutaationa g-1 [s,t] g.

Lisäksi on mahdollista, että 3-sykli pyörii "väärään suuntaan", eli teemmekin syklin (ACB) syklin (ABC) sijasta. Tästä tosin selviämme helposti, sillä (ABC)=(ACB)-1, eli käännämme vain siirtosarjan aiemmin kuvatulla tavalla. Jos olet vahingossa tehnyt väärään suuntaan pyörivän 3-syklin, niin älä masennu. Toistamalla sama siirtosarja saat oikeaan suuntaan pyörivän 3-syklin, sillä (ABC)(ABC)=(ACB).

Vaihe 3 - särmäpalat paikoilleen

Tästä vaiheesta selvitään nyt samoin kuin vaiheesta 2. Tekemällä aiemmin kuvatun särmäpalojen 3-syklin sopivia konjugaatteja riittävä määrä, särmäpalat menevät lopulta oikeille paikoilleen.

Vaihe 4 - kärkipalat oikeihin asentoihinsa

Tässä vaiheessa voimme olettaa, että kaikki kärkipalat jo ovat oikeilla paikoillaan. Ne saadaan oikeihin asentoihin kombinoimalla kuvattua siirtosarjaa ja sen sopivia konjugaatteja. Tässä ei välttämättä tarvitse turvautua konjugaatteihin, jos on halukas toistamaan ko. siirtosarjaa "tarpeettomasti". Yksi systemaattinen tapa on edetä kärki kerrallaan järjestyksessä "oikea etuylä, oikea takaylä, vasen takaylä, vasen etuylä, vasen etuala, oikea etuala, oikea taka-ala, vasen taka-ala". Tässä jonossa mitkä tahansa kaksi peräkkäistä kärkeä ovat samalla särmällä, joten katsomalla kuutiota sellaisesta suunnasta, jossa kyseinen särmä tulee etusivun yläreunaksi, voimme käyttää tarvittaessa kuvattua siirtosarjaa (tai sen käänteistä sarjaa) siihen, että jonossa aiemmin esiintyvä kärki kääntyy oikeaan asentoonsa. Tällöin emme välitä siitä, mitä jonossa seuraavana olevalle "apukärjelle" tapahtuu.

Mutta mutta? Miten käy jonon viimeisen kärjen? Sillehän emme enää voi tarjoa toista "apukärkeä" kaveriksi. Osoittautuu, että se ei ole tarpeen! Jonon kaksi viimeistä kärkeä nimittäin kääntyvät yhtä aikaa oikeihin asentoihinsa. Nimittäin tilanteessa, jossa kaikki kärkipalat ovat oikeilla paikoillaan voimme määrätä "kokonaiskiertymän" laskemalla yhteen kunkin kärkipalan kiertymät:

Voimme todistaa, että kokonaiskiertymä on aina 360 asteen monikerta. Kuvattu kahden vierekkäisen kärjen kierron antava siirtosarja sitten säilyttää tämän tilanteen, sillä siinähän toista kärkipalaa kierretään vastapäivään ja toista myötäpäivään. Näin ollen on mahdotonta saavuttaa tilannetta, jossa vain yksi kärkipala olisi väärässä asennossa! Tällainen permutaatio (joka on "saavutettavissa" purkamalla kuutio osiinsa ja kokoamalla se uudestaan eri tavoin) ei kuulu Rubikin ryhmään.

Vaihe 5 - särmäpalat oikeihin asentoihinsa

Kuvattu siirtosarja esittää, miten kaksi vierekkäistä särmäpalaa voidaan kääntää. On selvää, että tätä siirtosarjaa konjugoimalla saamme käännettyä mitkä tahansa kaksi särmäpalaa. Jos voisimme olla varmoja, että kääntyneitä särmäpaloja on aina parillinen määrä, niin tämä riittääkin - käännämme särmäpalat pareittain. Itse asiassa näin onkin. Sen näkemiseksi tarkastelkaamme sitä, miten Rubikin ryhmä operoi 24 särmäpalasivun (12 särmäpalaa, 2 sivua kullakin) joukossa. Näemme, että perussiirrot vastaavat tässä aina kahden 4-syklin tuloa. Tämä on parillinen permutaatio, joten 24 särmäpalasivuun kohdistuu tulosäännön nojalla aina parillinen permutaatio. Jos olisi mahdollista kääntää yksi (tai mikä tahansa pariton määrä) särmäpala paikallaan, syntyisi särmäpalasivujen joukkoon pariton permutaatio (nimittäin 2-sykli). Osoitimme juuri, että Rubikin ryhmässä ei tällaisia permutaatioita ole.

Yhteenveto, kombinaatioiden lukumäärä

Olemme nähneet vaiheissa 4 ja 5, että ryhmässä G(asennot) on alkioita 21137. Kullakin 12 särmäpalallahan on 2 mahdollista asentoa, mutta viimeisen asento määräytyy muiden asennoista siten, että väärinpäin olevia on parillinen määrä. Edelleen kullakin 8 kärkipalalla on 3 mahdollista asentoa, mutta viimeisen asento määräytyy siitä, että kokonaiskiertymä on 360 asteen kokonaislukumonikerta.

Vastaavasti näimme, että ryhmällä G(paikat) on aliryhmä H, joka muodostuu niistä permutaatioista, jotka operoivat sekä kärkipaloihin että särmäpaloihin parillisella permutaatiolla. Itse asiassa aliryhmässä H on tasan puolet ryhmän G(paikat) alkioista, sillä G(paikat) on erillisten osajoukkojensa H ja "oikeaalas"H unioni. Todistus. Vaiheissa 2 ja 3 näimme, että ryhmässä H ovat kaikki kärkipalojen parillisten permutaatioiden ja särmäpalojen parillisten permutaatioiden kombinaatiot. Näin ollen ryhmän G(paikat) alkioiden lukumäärä on 2 (8!/2) (12!/2). Ryhmäteoriaa tuntevat huomaavat varmaankin, että H on itse asiassa isomorfinen ryhmien A8 ja A12 suoran tulon kanssa.

Kaiken kaikkiaan siis Rubikin ryhmän alkioiden lukumääräksi saadaan

210378! 12! = 43 252 003 274 489 856 000,
joten ei ihme, että kuution satunnaisella kääntelyllä ei pulmapeli ratkea.

Rubikin ryhmän kompositiotekijöinä esiintyvät 2 alkion syklinen ryhmä (12 kertaa), 3 alkion syklinen ryhmä (7 kertaa) sekä alternoivat ryhmät A8 ja A12 (kumpikin kerran). Ryhmäteorian alkeita tuntevat huomaavat nyt heti, että Rubikin ryhmä ei ole ryhmäteorian mielessä ratkeava. Onneksi pulmapeli kuitenkin on ratkeava, kuten juuri näimme.