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

5. A bűvös kocka és a GAP program

5. A bűvös kocka és a GAP program

A bűvös kockának nagy irodalma van. Itt csak az a célunk, hogy bemutassuk a csoportelméletben széles körben használt GAP programot, és ehhez a bűvös kocka kiváló példát szolgáltat, annyira, hogy a program korábbi változatának tutorial-jában pontosan ez a példa szerepelt.

A GAP programot csoportok vizsgálatára fejlesztették ki, az emberiség csoportelméleti tudásának sok fontos részét tartalmazza. Hasznosnak bizonyult az algebra más ágaiban is. De ettől nem kell megijedni, mi magunk is eljátszhatunk vele. Nemcsak permutációkkal való szorzásra alkalmas, sok elemi dolgot is ki tud számolni (számelméleti kérdéseket, mint például a prímfaktorizáció, polinomokat is tud kezelni, stb.). A program szabad szoftver, a forráskódja is ingyenesen elérhető, és működik a legtöbb szokásos platformon (például Linux, Microsoft Windows alatt és a Macintosh-on is). Letölthető a következő címről:

Bemelegítésként végezzük el a 3. Fejezetben tárgyalt két permutációszorzást.

gap//>// (1,3,4,2)*(2,4,3); (1,2) gap//>// (2,4,3)*(1,3,4,2); (1,3)

Hogyan lehet a bűvös kocka mozgásait permutációkkal megfogni? A kocka 27 kisebb kockából áll. Ezek közül az olyanok, amelyek lapok közepén helyezkednek el (és csak egy színes oldaluk van), minden tekerésnél a helyükön maradnak, ezekkel tehát nem kell foglalkozni. Annak a 12 kis kockának, amelyek az éleken helyezkednek el, két színes lapjuk van, a nyolc csúcskockának pedig három. Számozzuk meg ezeket a színes lapokat az 1. ábra szerint:

1 2 3 4 00 5 6 7 8 9 10 11 12 00 13 14 15 16 17 18 19 20 00 21 22 23 24 25 26 27 28 00 29 30 31 32 33 34 35 36 00 37 38 39 40 41 42 43 44 00 45 46 47 48 \[ {\setlength{\arraycolsep}{5pt}\begin{array}{|*4{rrr|}} \cline{4-6} \multicolumn{1}{c}{} //&// //&////&// 1 //&// 2 //&// 3 \\ \multicolumn{1}{c}{} //&// //&////&// 4 //&// //&// 5 \\ \multicolumn{1}{c}{} //&// //&////&// 6 //&// 7 //&// 8 \\ \hline 9 //&// 10 //&// 11 //&// 17 //&// 18 //&// 19 //&// 25 //&// 26 //&// 27 //&// 33 //&// 34 //&// 35\\ 12 //&// //&// 13 //&// 20 //&// //&// 21 //&// 28 //&// //&// 29 //&// 36 //&// //&// 37\\ 14 //&// 15 //&// 16 //&// 22 //&// 23 //&// 24 //&// 30 //&// 31 //&// 32 //&// 38 //&// 39 //&// 40\\ \hline \multicolumn{1}{c}{} //&// //&////&// 41 //&// 42 //&// 43 \\ \multicolumn{1}{c}{} //&// //&////&// 44 //&// //&// 45 \\ \multicolumn{1}{c}{} //&// //&////&// 46 //&// 47 //&// 48 \\ \cline{4-6} \end{array}} \]

1. ábra.

Milyen permutációnak felel meg, ha az ábrán legfelül lévő lapon tekerünk egyet az óramutató járásának megfelelő irányba? Az ezen a lapon levő számok elmozdulnak az ( 1 , 3 , 8 , 6 ) és a ( 2 , 5 , 7 , 4 ) permutáció szerint. De nemcsak ez történik! Az élkockák mozgása miatt még végrehajtódik ( 10 , 34 , 26 , 18 ) is, a sarokkockák mozgása miatt pedig még másik két négyesciklus (hiszen a sarokkockáknak három számozott lapjuk van). A végeredmény a következő:


            gap//>// F:=(1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19);
  

Hasonlóképpen tápláljuk be a többi forgatásnak megfelelő permutációt is, ezek könnyen láthatóan a következők:


            B:=(9,11,16,14)(10,13,15,12)(1,17,41,40)(4,20,44,37)(6,22,46,35)
            K:=(17,19,24,22)(18,21,23,20)(6,25,43,16)(7,28,42,13)(8,30,41,11)
            J:=(25,27,32,30)(26,29,31,28)(3,38,43,19)(5,36,45,21)(8,33,48,24)
            T:=(33,35,40,38)(34,37,39,36)(3,9,46,32)(2,12,47,29)(1,14,48,27)
            A:=(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40).
          

Most készítsük el az ezek által generált csoportot, számítsuk ki ennek az elemszámát, és az elemszám prímtényezős felbontását:


           gap//>// cube := Group(F, A, B, J, K, T);
           gap//>// Size (cube);
           43252003274489856000
           gap//>// Factors (last);
           [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
            2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3,
            3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 7, 7, 11]

Vagyis a kockának 43252003274489856000 = 2 27 3 14 5 3 7 2 11 állapota lehet! Mutassuk most meg, hogy az alapállapotból nem juthatunk el abba az állapotba, amikor egy élkocka megfordul a saját helyén, és minden más a helyén marad. Ilyen mozgatás lenne például a (7,18) csere. Ugyanakkor két szomszédos élkockát egyszerre már meg lehet fordítani:


           gap//>// (7,18) in cube;
           false
           gap//>// (7,18)(5,26) in cube;
           true
          

Hasonlóan igazolható az is, hogy egy sarokkockát a saját helyén nem lehet elforgatni (csak ha például egy másik sarokkocka is elfordul a saját helyén).

5.1. Feladat. Adjunk arra a tényre, hogy egy élkocka nem fordítható meg a helyén, egy „elegáns” (tehát nem számolós és programot nem használó, matematikai) bizonyítást.

Ha egy élkockát nem is tudunk megfordítani, azért vannak olyan mozgássorozatok, amik csak nagyon kevés kis kockát mozgatnak, és ezek jól felhasználhatók a kocka minél gyorsabb rendezéséhez. A GAP segítségével ilyen sorozatokat is kereshetünk, mint az alábbi példák mutatják. Az f - 1 az f permutáció inverzét jelöli, például F - 1 azt, hogy a felső oldalt visszafelé kell forgatni. Az f 2 pedig azt jelenti, hogy f -et kétszer kell alkalmazni. Az alábbi sorozatok közül az első elforgat két sarokkockát a saját helyén, a második a fent keresett transzformáció, ami két élkockát fordít meg, a harmadik pedig élkockákat cserél.


           gap//>// (K∗B^-1∗A^2∗B∗K^-1∗F^2)^2;
           (1,9,35)(8,19,25)
           gap//>// J^-1∗F^2∗J^2∗F∗J^-1∗F^-1∗J^-1∗F^2∗B∗K∗J∗K^-1∗B^-1;
           (5,26)(7,18)
           gap//>// K∗J∗F∗J^-1∗F^-1∗K^-1∗K^-1∗B^-1∗F^-1∗B∗F∗K;
           (2,4)(5,18)(7,26)(10,34)