A kommutátor
Bevezető
A kommutátor egy nagyon hasznos dolog. Matematikával foglalkozó egyének biztosan találkoztak már vele.
A matematikában a kommutátorok a ciklikus csoportokban, gyűrűkben és úgy általában az assziciatív / kommutatív algebrai struktúrákban játszanak fontos szerepet. Mi ennek a gyakorlati hasznát fogjuk kihasználni.J (Aki eddig nem sejtette volna, a kocka és társai nemcsak jó játékok, de a ciklikus csoportok ideális szemléltetőeszközei is.)
A kommutátor tulajdonképpen egy speciális algoritmus. Nézzük az alábbit:
P és Q egy-egy algoritmus, és ' jelöli az adott algoritmus inverzét. Vagyis PP' nem csinál semmit, QQ' sem, és PQQ'P' se jó semmire. (Az inverzek "semlegesítik' az előttük álló algoritmust. Pl. A kockán FRDR' inverze RD'R'F')
Nos, az PQP'Q' algoritmust nevezik kommutátornak. (Egyéb jelölés: [g, h] = ghg-1h-1) Persze végtelen sok kommutátor létezik, többségük haszontalan, azonban ha felfogjuk a lényegét, hogy hogyan is működik, azzal sok hasznos algoritmust tudunk magunknak létrehozni. A kommutátor-algoritmus legnagyobb előnye, hogy gyakorlatilag bármilyen permutációs játékra (és ciklikus csoportelméleti problémára) lehet alkalmazni: 3x3x3 és társai, piraminx, megaminx, 4 dimenziós, 5 dimenziós, skewb, stb.
A kommutátorokat a klasszikus 3x3x3ason fogom bemutatni. (Illetve leghátul van két 4x4x4es példa is.)
A matematikai alapok
A ciklikus permutációs lépéseket gyakorta így jelölik, pl. (123). Ez a következőt jelenti: az 1-essel jelölt dolog ugrik a 2-essel jelölt dolog helyére, a 2-es a 3-as helyére, a 3-as vissza az 1-es helyére. azaz, pl. ha körbe lerajzoljuk őket:
| 1 |
3 |
| 3 2 |
2 1 |
| Ez az eredeti. |
(123) után ez lesz. |
Természetesen (123) ugyanaz, mint (231) vagy (312). A felsorolást épp ezért a legkisebbel szokták kezdeni.
A kockán ez így néz ki:
Tartsuk úgy a kockát, hogy a fehér oldal fönt legyen, a narancs elöl. Legyen a FehérNarancs él az 1-es, FehérZöld él a 2-es, és NarancsZöld él a 3-as. Csináljuk meg az alábbi algoritmust:
RBLF U F'L'B'R' U'
Láthatjuk, hogy az 1-es él a 2-es helyére ment, a 2-es a 3-as helyére, a 3-as az 1-es helyére, tehát a fenti algoritmus = (123)
Vegyünk még hozzá egy másik permutációt, mondjuk (345), azaz mit is csinál az (123)(345)?
Először is az 1-es megy a 2-es helyére, leírjuk, hogy 1. A 2-es megy a 3-as helyére, tehát 12. A 3-as menne az 1-es helyére… De a második körben azt látjuk, hogy a 3-as a 4-es helyére megy! Tehát: 124. A 4es megy az 5-ös helyére: 1245, az 5ös pedig a 3as helyére: 12453, és végül visszajutottunk az 1-eshez.
Vagyis: (123)(345) = (12453)
Ha nem értjük, nézzük meg két részletben, körbe lerajzolva őket:
Ez az eredeti. (123) után ez történik:
Most pedig egy (345). Fontos: Ez az eredeti ábrán a jobb alsó, a bal alsó és és a bal középső számokat ugráltatja, és itt is ezt csinálja, azaz:
A vastagon jelölt számok fognak ugrani. Ez lesz belőle:
Tehát, az eredeti ábrából kiindulva mi hova ment? 1->2, 2->4, 4->5, 5->3, 3->1, vagyis (12453).
Természetesen, ha a két (vagy több) permutációnak semmi közük egymáshoz, akkor nem kell variálni:
(123)(456) = (123456)
Néhány egyéb példa:
(12)(23) = (132)
(123)(325)(613) = (156)
(12345)(54321) = (1) = id. Ez utóbbi nem csinál semmit, hiszen a két permutáció egymás inverzei. Id. az identitásképzés, ami „önmagát" ( a kiindulási alappal megegyezőt) jelent.
Ha P és Q algoritmusnak a végeredmény szempontjából nincs közös elemük, akkor a kommutátor hasztalan.
Vagyis PQP'Q' = QPP'Q' = QQ' = id.
P és Q független, tehát a sorrendjük felcserélhető (azaz kommutatívak). P' visszacsinálja P-et, Q' visszacsinálja Q-t.
(Matematikailag bebizonyítható, hogy PQP'Q' akkor és csak akkor = id., ha P és Q kommutatív.)
Nézzünk egy hasznosabb kommutátort. Legyen
P = (123456789)
Q = (9 10 11 12 13 14 15 16 17)
Ekkor: PQP'Q' = (123456789) (9 10 11 12 13 14 15 16 17) (987654321) (17 16 15 14 13 12 11 10 9)
P és Q majdnem függetlenek. Egyetlen közös elemük a 9-es. Vagyis P' majdnem visszacsinálja P-et, Q' pedig majdnem visszacsinálja Q-t.
A végeredmény (számolással vagy rajzzal leellenőrizhető) ez:
PQP'Q' = (9 17 8)
Pontosan ez a kommutátor előnye: mindkét algoritmus sokat változtat, de a végeredmény rövid, csak egy kis módosítás az eredetin. Ehhez az kell, hogy a két algoritmus kevés közös elemet változtasson.
Élfordító kommutátor
Lássunk egy kommutátort a kockán. Ha eddig nem volt világos, miről is van szó, most (remélhetőleg) az lesz:
Fogjuk a kockát, és fordítsunk meg egy élt a felső rétegen úgy, hogy azon a rétegen semmi más ne változzon. Pl.
R'ER2E2R' megcseréli a jobb fölső élt. (Jó lehet még a MD'M'DMD2M' is az elülső felső él megcserélésére, én most az előbbit nézem.)
Ha megcsináljuk az algoritmus inverzét: RE2R2E'R, akkor értelemszerűen visszakapjuk az eredeti, kirakott kockát.
Mit is csinált az algoritmus? A felső rétegen csak ennyi történt: a jobb felső élt megfordította. Az alsó két rétegen meg kutyult valamit.
Ha tehát az algoritmus inverzét csináljuk meg az megint megfordítja a jobb felső élt, az alsó részt pedig visszaállítja.
De! Tegyünk az algoritmus után egy apró módosítást: U2.
Most csináljuk vissza az első algoritmust! Mit fog csinálni? Azt, amit korábban megbeszéltünk: megfordítja a jobb felső élt, és visszacsinálja az alsó két réteget. Mivel az alsó két rétegbe nem avatkoztunk bele, így az maradéktalanul visszaáll. Ezt kapjuk:
Csináljuk vissza a módosítást is: U2.
Vagyis kaptunk egy kommutátort két él felcserélésére. A teljes algoritmus:
P = R'ER2E2R' Q = U2, azaz:
PQP'Q' = R'ER2E2R' - U2 - RE2R2E'R - U2
U2 helyett használhatunk U-t ill. U'-t, ekkor persze más él fog megfordulni, és nem az eredetivel szemközti.
Alapvetően ez a kommutátorok taktikája: kitalálunk egy egyszerű algoritmust, módosítunk benne egy picikét, az első inverzével visszaállítjuk a többséget, majd a módosítást is visszacsináljuk.
Ha a két él eléggé távol van egymástól, tegyünk „beállító" forgatásokat. Pl.
Ilyenkor vagy D'L2 után a fent említett algoritmus, majd L2D, vagy F2, csak akkor majd nem U2-vel, hanem U'-val tesszük a rossz élt a másik helyére. (azaz F2 - R'ER2E2R' - U' - RE2R2E'R - U - F2)
Sarokfordító kommutátor
Nézzük az alábbi példát:
A kommutátoros taktika: az egyik élt (legyen a jobb felső) ki kéne venni, és rendes állapotában vissza kéne tenni. U'-val „kicseréljük" a két élt, majd az első algo inverzével az alsó két réteg is visszajön, és ez a sarok is visszafordul. Végül U-val a módosítást is helyreállítjuk.
Tehát:
R'D'R kiveszi a jobb felső sarkot, DR'D'R pedig normálisan vissza teszi.
Ha most csinálnánk meg az inverzét, minden visszaállna. Vagyis az inverz az alsó két réteget helyrehozza, a felső oldalt békén hagyja a jobb felső elülső sarok kivételével, amit elforgat (az óramutatóval ellentétes irányban).
Mielőtt tehát megcsináljuk az inverz algoritmust, csinálunk egy U'-t, hogy a másik rossz sarok legyen a jobb felső elülső helyen.
Ezután az inverz algoritmus visszaállítja az alsó két réteget (hiszen itt semmi nem változott), és a felső rétegen azt az egy sarkot visszafordítja a megfelelő irányba.
Tehát most R'DRD' és R'DR után:
Végül U-val a módosítást is korrigáljuk.
A teljes algoritmus:
R'D'RDR'D'R - U' - R'DRD'R'DR - U
(Ahol P = R'D'RDR'D'R, Q = U')
Itt is, mint egyébként mindenhol, használhatunk beállító mozdulatokat, csak ne felejtsük el a végén visszaállítani őket.
A sarokpermutáló kommutátor
Hogyan is lehet 3 sarkot tetszőlegesen helyezni egy lépésben, úgy hogy semmi más ne változzon? Nos, a ravaszabbak már sejtik a választ…
Nézzük az egyik legegyszerűbb példát:
Először meg kell állapítanunk az egymásnak megfelelő matricákat, vagyis hogy mi minek a megfelelője, és melyik melyiknek a helyére megy. Ez az orientáció szempontjából lényeges, nehogy valamelyik sarok rosszul kerül a helyére.
Tekintsük a FehérKékNarancs sarkot: legyen mondjuk a kiválasztott színe a kék. Hova megy majd ez a sarok? Oda, ahol most a ZöldSárgaNarancs sarok van. Tehát meg kéne mondanunk ennek a saroknak a kiválasztott matricáját. Mivel az előző sarok-é a kék volt, megnézzük, itt mi van a kék helyén: a narancs. Ennek a saroknak tehát ez a kiválasztott színe. Ez a sarok pedig majd oda megy, ahol most a NarancsFehérZöld sarok van. Az előző sarok színe a narancs volt. Mi van itt a narancs helyen? Itt is narancs van.
Háromféleképpen indulhatunk el, hogy mit tekintünk kiválasztott színnek. Az egymásnak megfelelő színeket az alábbi ábrák mutatják, az első felel meg a fent leírtnak:
Mint a későbbiekben látni fogjuk, a legjobban akkor járunk, ha két szín fönt van egy oldalon, a harmadik lent, de nem legalul, hanem oldalt, mint a második ábrán. Tehát ezt választjuk.
Visszatérve tehát a problémához: az alsó sarokot (FehérNarancsZöld) kell felvinnünk a helyén álló sarok helyére (FehérKékNarancs), úgy hogy a lenti sarok kiválasztott színe a fent sarok kiválasztott színének helyére kerüljön. Két lehetőségünk is van: DFD'F', vagy R'D'R. Legyen az utóbbi, a rövidsége miatt. Fontos, hogy a felső oldalon semmi más nem változhat.
A sarok tehát a helyén van.
Ha most csinálnánk meg az inverz algoritmust (visszavisz a kiindulási pontra): a jobb felső sarok visszamegy alulra (a kiválasztott matrica a másik matrica helyére), és az alja visszaáll.
Ehelyett cseréljük ki a betett sarkot a másik felső oldalon lévő sarokkal, a felső réteget kihasználva: U'.
Most hajtsuk végre az inverzet, R'DR: a jobb sarok lemegy alulra (a helyére, zöld matricája lesz oldalt), és az alsó réteg többi része is visszaáll.
U-val a módosítást is végrehajtjuk, és kész. A teljes algoritmus:
R'D'R - U' - R'DR - U
Egy másik példa:
Határozzuk meg az előbbi módon az egymásnak megfelelő matricákat. Három változat közül választhatunk:
Nos, melyik felel meg a feltételnek? Két matrica fent, azonos oldalon, egy az alsó rétegen, de nem legalul, hanem oldalt. A helyes válasz a harmadik: ne zavarjon, hogy a kocka el van döntve: most a „felső oldal" a jobb oldalon van.
Azaz, z' után:
Az alsót bevisszük a helyére, ügyelve, hogy a felső oldalon más ne változzon: BD2B', majd a betett sarkot kicseréljük a másik rosszal: U2.
Visszacsináljuk az első algot, és végül a módosítást is. Kész.
A teljes algo:
z' BD2B' - U2 - BD2B' - U2 z
Még egy példa:
Kiválasztott matricákkal:
Hát, egyik sem nevezhető ideálisnak. De! Ha jól megnézzük az elsőt, egy B után jó lesz! Azaz:
Ugyanaz a nóta: az alsót betesszük a helyére (jelen esetben jobb hátra fel, úgy hogy a zöld matricája legyen fönt):
RD2R'
Majd U'-val ugyanide tesszük a másik rossz sarkot:
Visszacsináljuk a sarokbeillesztő algot: RD2R', majd a módosítást: U, végül a beállítást: B'
A teljes algoritmus tehát:
B - RD2R' - U' - RD2R' - U - B'
Egy utolsó idevágó példa:
Nehéz ügy. A második majdnem jó. Nem baj, nézzük a másodikat: úgy is be lehet tenni a sarkot egyből, hogy az alsó színe felülre kerüljön. Ám ehhez alatta kell lennie:
D2-vel beállítjuk, hogy a lenti sarok a helye alatt legyen. Majd R2DR2D'R2-vel beraktuk a sarkot. U2-vel kicseréljük a másik rossz sarokkal, majd a sarokcserés algot visszacsináljuk: R2DR2D'R2. Majd U2-t, végül D2-t is visszacsináljuk.
A teljes algo:
D2 - R2DR2D'R2 - U2 - R2DR2D'R2 - U2 - D2
Van viszont rövidebb változat is. Az elején a saroknak a helye alatt kell lennie. Ne D2-t, hanem U2-t forgassuk (a helyét visszük a sarok fölé).
Ekkor a sarokcserélő algo L2DL2D'L2. U2-vel fenti rossz sarkot visszük az adott helyre, majd vissza csináljuk az sarokcserélő algot: L2DL2D'L2. Ezután U2-vel visszacsináljuk a módosítást, majd U2-vel a beállítást. Tehát:
U2 - L2DL2D'L2 - U2 - L2DL2D'L2 - U2 - U2, vagyis:
U2 - L2DL2D'L2 - U2 - L2DL2D'L2
A fenti példák gondolkodásmódjaival képesek vagyunk arra, hogy bármely három sarkot a helyére vigyük a kockán, ideális esetben 8, általában 10, de maximum 12 fordítással!
Egyéb hasznos kommutátorok
Nézzünk néhány további, speciális esetet:
Itt a közepeket és a lenti éleket kéne elforgatni. Az alapötlet:
Ha a négy élt fel tudnánk hozni a középső rétegre, akkor e réteg elforgatásával mind a közepek, mind az élek arrébb vándorolnak eggyel, és csak ezek, tehát a többi elem visszaállna, amikor visszacsináljuk az első algot.
Tehát hozzuk fel az éleket, pl.:
FRB felhoz három élt, F'LF berakja a negyediket. Most minden elforgatandó rész a középső rétegen van, tehát odébb visszük őket: E'. Visszaállítunk mindent: F'L'FB'R'F'.
Tehát:
FRBF'LF - E' - F'L'FB'R'F'
(Megjegyzés: ez nem valódi kommutátor, hiszen E-t nem kellett visszacsinálni. A PQP' alakú algoritmusokat, mint ez, valójában konjugátornak hívják.)
A sarkok ötletét élekre is átültethetjük:
Szintén keressük meg az egymásnak megfelelő matricákat. Itt csak két lehetőségünk van:
Az első nagyon jó lesz. Tegyük be a lenti élt a helyére, jól, más elem ne változzon:
R'E'R
U2-vel cseréljük ki a másik éllel, majd az jön első algo inverze: R'ER, végül a módosítás inverze: U2.
Azaz:
R'E'R - U2 - R'ER - U2
Na ez kicsit érdekes lesz: egy jól ismert PLL algoritmust oldunk meg kommutátorral.
Az alapötlet: nem sarkokat, és nem is éleket mozgatunk, hanem él-sarok párokat! Ezt ugyanúgy tesszük majd, mint a sarkok esetén, csak most az élt is vele mozgatjuk.
Mivel azonban három elemet tudunk általában permutálni, nem kettőt, így tegyünk egy U-t a legelején.
Most a felső réteg egy középből és négy sarok-él párból áll, ebből egy már a helyén van.
Azonban mindhárom fönt van. Az egyiket oldalsó helyzetbe kéne vinni (vagyis hogy ne a felső rétegen legyen). Csak egyet tudunk nyugodtan odébb mozgatni: a legelsőt: F'
Az utolsó ábra lesz a nyerő. Nosza, tegyük be az alsót a helyére: B'd2B. Most tegyük a másik fölső sarok-él párt ide: U. Csináljuk meg az inverzeket: B'd2B, majd U', végül a módosítást alakítsuk vissza: F
A teljes algoritmus:
[U] F' - B'd2B - U - B'd2B - U' - F
(Megjegyzés: a legelső U azért kellett, hogy kommutátoros megoldásunk legyen, tehát ezt nem kell visszacsinálni. Lecserélhetjük y-ra is, ekkor viszont a végén kell egy U.)
Alternatív megoldás sarokforgatásra:
Alapötlet: levisszük a két sarkot, és ott cseréljük ki őket.
Tehát: F'R-rel levisszük őket. A felső rétegből csak ez a két elem van lent, így nyugodtan kicserélhetjük őket: D2, majd vissza tesszük őket: R'F.
Most U2-vel kicseréljük őket, majd az első algot vissza, végül megint U2.
A teljes algo:
F'RD2R'F - U2 - F'RD2R'F - U2
A következő történt: amikor alul kicseréltük a két sarkot, azokon még forgattunk is egyet. Először narancs ill. kék matricát láttunk fent, de a helycsere után ez is megváltozott. U2-vel fönt kicseréltük őket, a fönti matricák maradtak. Az első algo inverze önmaga, tehát nemcsak visszahozza a sarkokat az eredeti helyükre (meg a többi elemet is), de még egyet forgat rajtuk. Tehát, bár a két sarok kétszer cserélt helyet, és így ugyanoda kerültek vissza, közben kettőt fordultak is.
Hasonló érdekesség az élekre:
Az alapötlet: két egymás melletti élt kicserélünk úgy, hogy jól kerüljenek vissza. Amikor fent a másik két élt a helyükre visszük, és megcsináljuk az inverzet, akkor ezeken az éleken is megtörténik a csere.
Tehát:
F'R után a középső rétegen nyugodtan megcserélhetjük a FehérZöld és FehérNarancs élt, hiszen a felső rétegből csak ez a két elem van itt. Ráadásul a fehér színük pont az ellentétes oldalon lesz, ergo visszatételkor az lesz fönt.
Vagyis:
F'RE2R'F
Most U2-vel kicseréltük az éleket. Így az algo inverzekor ezek fognak visszaállni, elvégre az algo az elülső fönti, és a jobb fönti élt cseréli meg, és most U2 révén a másik két él van itt. Végül az inverz után U2-t is helyrehozzuk.
Egyben így fest: F'RE2R'F - U2 - F'RE2R'F - U2
Egy másik jól ismert PLL:
Az alapötlet: hasonló az előzőhöz, csak itt nem szeretnénk forgatni. Ha két egymás melletti sarkot (pl. a két hátsót) megcserélünk, akkor U2 után az algo inverzekor a másik két sarok visszacserélődne.
Sokféleképpen megcserélhetjük a két hátsót (fontos, hogy a fehér színük fönt maradjon), a legrövidebb viszont az, ha alul, D2-vel oldjuk meg. Úgy kell levinnünk őket, hogy átlósan legyenek, és D2 után a fehér színük ugyanott maradjon. Pl.:
RU'L
Most a fenti rétegből csak a két kérdéses sarok van lent, így mehet a D2. Tegyük vissza őket: L'UR'. U2-vel jöhet a másik két sarok, majd az inverz mindent visszaállít. Végül U2-t is visszahozzuk.
A teljes algo: RU'L D2 L'UR' - U2 - RU'L D2 L'UR' - U2
Egy 4x4x4es élrendező kommutátor:
A szokásos taktika 3 elem cseréjére.
A második lesz a jó. Az alsót betesszük a helyére: R'dR, csere fönt: U2, inverz1: R'd'R, inverz2: U2, vagyis: R'dR - U2 - R'd'R - U2
Végül, egy 4x4x4es középcserélő kommutátor:
Valójában három elemet mozgatunk majd, mégpedig ezeket:
Az alsót betesszük a felső fehér kis középelem helyére: b'db. Most U-val a fenti narancs közepet tesszük erre a helyre. Az inverzkor visszaáll minden: b'd'b. Végül U'-vel a módosítást is visszaállítjuk. Azaz:
b'db - U - b'd'b - U'
Ennyi… kellő logikával bármilyen permutációs játékra átültedheted a kommutátorokat.
Az angol nyelvű forrás, többé kevésbé ugyanez található rajta:
http://www.math.leidenuniv.nl/~jnoort/index.php?location=commutators
(a holland Joël van Noort honlapja)
Egyéb hasznos matematikai dolgok Jaap oldalán:
http://www.geocities.com/jaapsch/puzzles/theory.htm
Jó szórakozást!
Renslay, 2006 július.