Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

3. Mozdulatok egymás után

3. Mozdulatok egymás után

Most próbáljunk meg kártyakeverő gépet építeni. A gép konkrét mozdulatokat tud elvégezni, mondjuk el tudja emelni a csomagot, vagy meg tudja cserélni a legfelső két lapot. Ha ezeket a mozdulatokat sokszor véletlenszerűen alkalmazza egymás után, megkeveredik-e jól a kártyacsomag?

Persze tisztáznunk kellene, mit is takar a „jól” megkevert kártyacsomag fogalma, és mit a „véletlenszerűen” alkalmazott mozdulatok, mindez ismét a valószínűségszámításhoz tartozik. De az biztos, hogy ha az adott mozdulatokkal nem kapható meg a kártyacsomag lapjainak tetszőleges sorrendje, akkor a gép nem lesz megfelelő.

3.1. Kérdés. Az említett két mozdulattal (felső két lap cseréje, emelés) meg lehet-e kapni a kártyacsomag lapjainak összes lehetséges sorrendjét, ha ügyesen keverünk?

Hasonló problémával kerülünk szembe bizonyos játékok (például a Rubik-kocka) vizsgálatakor is, amikor az a kérdés, hogy a megengedett mozdulatokkal előállítható-e a játék egy kívánt állapota. Ezt a kérdéskört az 5. Fejezetben vizsgáljuk majd.

3.2. Kérdés. Rendet lehet-e csinálni egy könyvespolcon úgy, hogy mindig csak két könyvet cserélünk meg?

Hát persze. Ha a legbaloldali helyen nem az a könyv van, ami odavaló, akkor odacseréljük azt, ami odavaló. Ezután a balról második helyre is odacseréljük azt, ami odavaló. Az eljárást folytatva minden könyv a helyére kerül (és a szükséges lépések száma a legrosszabb esetben is eggyel kevesebb, mint a könyvek száma).

3.3. Kérdés. Rendezhetők-e a könyvek, ha csak szomszédos (helyen lévő) könyvek cseréjét engedjük meg?

Nyilván igen: a legbaloldali helyre való könyvet a helyére tehetjük úgy is, hogy mindig a bal szomszédjával cseréljük addig, amíg a helyére nem kerül. Ezután folytatjuk a balról második helyre való könyvvel, és így tovább.

Most már be tudjuk látni azt is, hogy emeléssel és a legfelső két lap cseréjével minden kártyacsomag rendezhető. Az emelés azt jelenti, hogy a csomag tetejéről leveszünk egy kisebb csomagot, és azt változatlan sorrendben alulra tesszük. (Ezt úgy is felfoghatjuk, hogy csak a legfelső lapot tesszük legalulra, de ezt sokszor végezzük.) Tegyük fel, hogy a csomagban n lap van. A k -adik és a k + 1 -edik lap cseréjét elvégezhetjük úgy, hogy elemeljük a csomagot a k - 1 -edik lapnál (tehát az első k - 1 lapot alulra tesszük), majd megcseréljük a felső két lapot, végül elemeljük a csomagot az n - k + 1 -edik lapnál (azaz visszatesszük az alsó k - 1 lapot a tetejére). A szomszédos lapok cseréje tehát elvégezhető, és így a csomag rendezhető.

3.4. Feladat. Legyenek k és t egynél nagyobb, relatív prím egészek. Az 1 , 2 , , n számok 12 n sorrendjéből kiindulva tetszőleges két olyan elemet felcserélhetünk, amelyek különbsége k vagy t . Bizonyítsuk be, hogy ilyen lépések egymásutánjával akkor és csak akkor juthatunk el minden lehetséges sorrendhez, ha k + t - 1 ? n .

Általában most is az olyan állításokat nehezebb bizonyítani, hogy a megadott mozdulatokkal bizonyos sorrend nem állítható elő.

3.5. Kérdés. Tegyük fel, hogy a kártyacsomagunk csak négy lapból áll, és az emelésen kívül az első és a harmadik lapot szabad megcserélni. Megkaphatjuk-e a lapok összes lehetséges sorrendjét?

Látszólag most is végtelen sok mozdulatsorozatot kellene áttekinteni, könnyen meggondolhatjuk azonban, hogy erre nincsen szükség, mert a csomag lapjainak csak véges sokféle (összesen 4 ! = 24 ) sorrendje lehetséges. Az egyszerűség kedvéért számozzuk meg a lapokat, induljunk ki az 1234 sorrendből, és nézzük meg, hogy milyen sorrendet kapunk, ha elvégzünk egy mozdulatot. Emelésekkel 2341, 3412, 4123 jön ki. Ha az első és harmadik lapot cseréljük, akkor az eredmény rendre 3214, 4321, 1432, 2143. Eddig nyolc lehetséges sorrend jött ki. De tovább már nem kell csinálni a dolgot, mert könnyű végigszámolni, hogy sem emeléssel, sem az első és a harmadik lap cseréjével már nem kapunk új sorrendet. Tehát az adott mozdulatokkal csak nyolc sorrend valósítható meg, nem az összes.

A mostani gondolatmenet ugyan mutatja, hogy az általános probléma esetén is mindig csak véges sok lehetőséget kell végignéznünk, de ez az eljárás nem is szép, és nem is hatékony. Lássunk először egy szebb megoldást ugyanerre a feladatra. Ezúttal a kártyacsomag lapjainak sorrendjeihez fogunk geometriai transzformációkat rendelni.

Rakjuk a négy kártyalapot körben rá egy négyzet négy csúcsára. Az első és a harmadik lap tehát az egyik átló két végpontjára kerül. Ha ezeket megcseréljük, miközben a másik két lap a helyén marad, akkor a négyzetet a másik átlójára tükröztük. Az emelések nyilván a négyzet forgatásainak felelnek meg. Ha tehát ezeket a mozdulatokat többször elvégezzük, akkor is mindig a négyzet egy egybevágósági transzformációját kapjuk (átló átlóba, oldal oldalba megy). Tehát olyan sorrendet, mint például 2134, soha nem kaphatunk, hiszen ennél az 13 átlóból a 23 oldal keletkezne.

A számítógép-építési problémában klónnak neveztük azoknak a függvényeknek a halmazát, amelyek a megadott függvények egymásba helyettesítgetésével előálltak. Érdemes észrevenni, hogy most ennek egy speciális esetéről van szó. Ha a jelek halmazának a kártyacsomag lapjait vesszük, akkor minden keverési mozdulat átrendezi a lapok sorrendjét, tehát egy egyváltozós függvénynek tekinthető (ami ráadásul még kölcsönösen egyértelmű is). Például a négyelemű kártyacsomagban az első és a harmadik lap cseréje az az f függvény, amelyre f ( 1 ) = 3 , f ( 3 ) = 1 , és f ( 2 ) = 2 , f ( 4 ) = 4 . Hasznosabb az ilyen f függvényekkel dolgozni, mint helyette a lapok 3214 sorrendjével, mert a keverési mozdulatok egymásutánja e függvények egymásba helyettesítésének felel meg. Egy-egy ilyen függvényt, tehát egy halmazt önmagára képző kölcsönösen egyértelmű leképezést a halmaz egy permutációjának nevezzük. Ezek egymásba helyettesítését pedig egyszerűen szorzásnak hívjuk.

3.6. Feladat. Igazoljuk, hogy véges halmazon minden permutáció inverze megkapható úgy, hogy a permutációt önmagával szorozgatjuk (azaz hatványozzuk).

Ha meg van adva egy halmazon néhány (esetleg végtelen sok) permutáció, akkor azoknak a permutációknak a halmazát, amelyek ezekből szorzás és inverzképzés segítségével (véges sok lépésben) előállíthatók, az általuk generált permutációcsoportnak szokás nevezni. Az előbbi példában szereplő nyolc permutáció tehát permutációcsoportot alkot. Az eddigiekből az is látszik, hogy egy véges halmazon értelmezett permutációk akkor és csak akkor alkotnak permutációcsoportot, ha bármely kettőt összeszorozva ismét az adott permutációk valamelyikét kapjuk.

Leggyakrabban úgy kapunk permutációcsoportot, hogy egy alakzat összes szimmetriáit tekintjük. Például egy szabályos háromszögét (mint a szóproblémáról szóló fejezetben), vagy egy négyzetét, mint az imént. A következő fejezetben egy módszert mutatunk arra, hogyan lehet egy alakzat szimmetriáit megszámolni.

Ahhoz, hogy permutációkkal számolni tudjunk, hasznos lesz bizonyos speciális permutációkra külön jelölést bevezetni. Ha az i és j jeleket kell kicserélni, akkor erre az ( i , j ) jelölést alkalmazzuk. Ennél a permutációnál tehát a többi jel fixen marad (azaz önmagába megy). Ennek a jelölésnek az általánosításaként jelölje ( a , b , c , , u , v ) azt a permutációt, aminél az a képe b , a b képe c , és így tovább, az u képe v , végül a v képe a (és a többi jel most is a helyén marad). Vagyis a zárójelben szereplő jelek körbepermutálódnak, és így az ilyen permutációt ciklusnak nevezzük. Tipikus ciklus például, ha a kártyacsomagban a felső lapot legalulra tesszük. A ciklusok jelentőségét a következő állítás világítja meg.

3.7. Feladat. Igazoljuk, hogy egy véges halmazon minden permutáció felbontható olyan ciklusok szorzatára, amelyeknek páronként nincs közös eleme.

Példaként számítsuk ki, hogy az f = ( 1 , 3 , 4 , 2 ) és a g = ( 2 , 4 , 3 ) ciklusok szorzata hová viszi a 2 jelet. Kétféle sorrendben is végezhetjük a szorzást. Ha először f -et, majd g -t alkalmazzuk (ennek jele f g = ( 1 , 3 , 4 , 2 ) ( 2 , 4 , 3 ) ), akkor a 2 képe f -nél 1 lesz, az 1 pedig g -nél helyben marad, hiszen az 1 nem szerepel a ( 2 , 4 , 3 ) -ban. Tehát f g a 2-t 1-be viszi. Ugyanígy kiszámolható, hogy f g az 1-et 2-be viszi, a 3 és 4 elemeket pedig helyben hagyja. Tehát f g az ( 1 , 2 ) ciklus. Ugyanakkor g f -nél a 2 képe 2 lesz (a g elviszi 4-be, az f visszahozza). Tehát azt tapasztaltuk, hogy f g ? g f , azaz szorzásnál a sorrendre is vigyázni kell. Könnyű gyakorló feladatnak érdemes kiszámolni, hogy g f = ( 1 , 3 ) .

A fejezet elején azt láttuk be, hogy a kételemű ciklusok által generált permutációcsoport az összes permutációból áll.

3.8. Kérdés. Jól megkeveredik-e a csomag, ha a keverőgép a háromelemű ciklusokat képes elvégezni?

A válasz az, hogy nem. Ezt is úgy fogjuk belátni, hogy megadunk valamit (mint az iménti négyzetet), amelynek az összes hármasciklus szimmetriája, de nem minden permutáció szimmetriája. Ez a „valami” a következő kifejezés lesz:

F ( x 1 , , x n ) = ( x 1 - x 2 ) · ( x 1 - x 3 ) · · ( x 1 - x n ) · · ( x 2 - x 3 ) · · ( x 2 - x n ) · · ( x n - 1 - x n ) .

Vagyis össze kell szorozni az összes x i - x j különbséget, ahol i //<// j .

Ha f permutáció az { 1 , 2 , , n } halmazon, akkor helyettesítsük F -be az x 1 , , x n változókat az f által megadott sorrendben, azaz számítsuk ki az F ( x f ( 1 ) , , x f ( n ) ) kifejezést. Ez nyilván csak előjelben különbözik F ( x 1 , , x n ) -től, ezt az előjelet az f előjelének fogjuk nevezni.

3.9. Tétel. Az f g előjele az f és g előjeleinek a szorzata. Kettesciklus előjele - , hármasciklusé + , általában egy k hosszú ciklus előjele pontosan akkor + , ha a ciklus páratlan hosszú.

Ez könnyű tétel, melyet az Olvasó is megpróbálhat belátni. Most már látszik, hogy hármasciklusokkal nem jó kártyakeverő gépet építeni, mert akármennyit keverünk is, mindig + előjelű (úgynevezett páros) permutációt kapunk. A páros permutációk tehát permutációcsoportot alkotnak. Ez olyan fontos, hogy neve is van. Az 1 , 2 , , n halmaz összes permutációinak csoportja az S n szimmetrikus csoport, ezek közül a páros permutációk csoportja az A n alternáló csoport.

3.10. Feladat. Határozzuk meg a páros permutációk számát.

Mi a helyzet egy olyan géppel, ami a kettesciklusokat képes alkalmazni? Azt már láttuk, hogy ezekből minden permutáció megkapható. De most már azt is látjuk, hogy ez mégsem egy igazán jó keverőgép. Ha ugyanis egy mozdulatot végzünk, akkor biztosan - előjelű (azaz páratlan) permutációt kapunk. Ha kettőt, akkor páros permutációt kapunk, mert két páratlan permutáció szorzata páros. Ha három mozdulatot végzünk, akkor megint páratlan lesz az eredmény. Ha tehát valaki figyeli a kezünket, és megszámolja, hogy hány keverő mozdulatot teszünk, akkor nemtriviális információt kap a lapok sorrendjéről. Ez a probléma mindig fellép, ha az összes keverő mozdulatunk páratlan permutáció.

Meglepő felfedezés, aminek a bizonyításához mély csoportelméleti eszközök (és például geometriai transzformációk, sőt komplex számok is) kellenek, hogy lényegében az az egyetlen megszorítás, amit most felfedeztünk. Ha a gépünk használhat páros és páratlan mozdulatokat is, és a megengedett permutációk generálják az összes permutációt, akkor a csomag jól meg fog keveredni. Ez a tétel magyarázza meg azt a köznapi tapasztalatot, hogy ha valaki nem csal nagyon, akkor lényegében mindegy, hogy milyen mozdulatokkal kever, a csomag jól megkeveredik.

3.11. Tétel. Tegyük fel, hogy a kártyacsomagnak n ? 5 lapja van, és válasszunk ki néhány keverő mozdulatot. Mindegyikhez meg van adva egy pozitív valószínűség (melyek összege 1). A keverő mozdulatokat a megadott valószínűségekkel alkalmazzuk, egymástól függetlenül. Ha ezek a permutációk generálják az egész szimmetrikus csoportot (azaz szorozgatással minden permutációt megkaphatunk belőlük), és van közöttük páros is, akkor a kártyacsomag jól megkeveredik, azaz elég nagy k esetén a k -adik keverő mozdulat után a csomag lapjainak bármelyik sorrendje közelítőleg egyforma (azaz 1 / n ! ) valószínűséggel fog előfordulni.

Az igazi probléma persze annak eldöntése, hogy az adott permutációk mikor generálják az összes permutációt (illetve hogy milyen permutációcsoportot generálnak). Ez igen nehéz kérdés, mert általában nem áll rendelkezésünkre olyan egyszerű alakzat, aminek a szimmetriáiról volna szó. Ízelítőül álljon itt egy olyan probléma, ami hosszú évtizedekig megoldatlan volt.

Legyen p prímszám, és tekintsük az a x + b függvényeket, ahol a = 1 , 2 , , p - 1 , és b = 0 , 1 , 2 , , p - 1 . Ezeket a { 0 , 1 , , p - 1 } halmazon is értelmezhetjük, és ha az eredményt maradékosan elosztjuk p -vel, akkor az is ebben a halmazban lesz. Azonnal látszik, hogy permutációkat kaptunk, amik csoportot alkotnak. A nevezetes probléma az volt, hogy igaz-e a következő: ha ezekhez a permutációkhoz még bármilyen másik permutációt hozzáveszünk, akkor ezek már az összes permutációt generálják.

Az igenlő választ úgy sikerült bebizonyítani, hogy a csoportokat mint önálló dolgokat vizsgálták, a szerkezetüket igyekeztek felderíteni. Például azt, hogy hogyan lehet őket kisebb csoportokból felépíteni. Azokat a csoportokat, amelyekkel ez (bizonyos módon) nem tehető meg, egyszerű csoportnak nevezzük.

Legkönnyebben úgy kaphatunk példát egyszerű csoportra, hogy egy prím hosszú ciklus összes hatványát tekintjük. Kicsit nehezebb belátni, hogy az A n alternáló csoport egyszerű, ha n ? 5 (ez az oka annak, hogy a legalább ötödfokú egyenletre nincsen gyökképlet, erről a 6. Fejezetben lesz szó). További példákat szolgáltatnak a geometriából származó (például az egybevágósági transzformációk segítségével kapható) egyszerű csoportok.

A csoportelmélet egyik legfontosabb problémája volt, hogy megtalálja és kielemezze a véges egyszerű csoportokat. A listát 1982 táján sikerült teljessé tenni, ezt az eredményt nevezzük a véges egyszerű csoportok klasszifikációjának. Annak bizonyítása, hogy a lista teljes, több mint tízezer oldal. Összesen 18 végtelen sorozat van (ezek egyike az alternáló csoportok A 5 , A 6 , sorozata), és még további26 csoport, ami egyik sorozatba sem illik bele, és ezért spóradikus egyszerű csoportnak nevezzük őket. Ezek legnagyobbika a Monster névre hallgat, és méltán:

808 017 424 794 512 875 886 459 904 961 710 757 005 754 368 000 000 000 ,

azaz 8 . 08 · 10 53 eleme van. Ez sokkal több, mint ahány atomból a Föld áll, tehát például reménytelen számítógépben tárolni az elemeit.

A klasszifikációt sok helyen lehet alkalmazni, a csoportelméleten kívüli (például kombinatorikai) problémák tárgyalására is. Az egyik spóradikus egyszerű csoportot egy űrszonda is magával vitte, kommunikációs célból.