11  Grupos livres e o cubo mágico

11.1 O cubo mágico

O cubo mágico, como outros brinquedos de lógica, pode ser analisado usando o sistema GAP. Neste projeto vamos analizar o grupo associado com o cubo mágico e vamos criar um algoritmo baseado na teoria dos grupos livres para a solução do cubo.

11.2 Exploração interativa

O cubo tem 48 peças cujas posições estão ilustradas no seguinte diagrama.

                     +--------------+
                     |              |
                     |  1    2    3 |
                     |              |
                     |  4  CIMA   5 |
                     |              |
                     |  6    7    8 |
                     |              |
      +--------------+--------------+--------------+--------------+
      |              |              |              |              |
      |  9   10   11 | 17   18   19 | 25   26   27 | 33   34   35 |
      |              |              |              |              |
      | 12  ESQ   13 | 20 FRENTE 21 | 28 DIREIT 29 | 36  TRAS  37 |
      |              |              |              |              |
      | 14   15   16 | 22   23   24 | 30   31   32 | 38   39   40 |
      |              |              |              |              |
      +--------------+--------------+--------------+--------------+
                     |              |
                     | 41   42   43 |
                     |              |
                     | 44  BAIX  45 |
                     |              |
                     | 46   47   48 |
                     |              |
                     +--------------+

Todo movimento pode ser visto como uma permutação dessas peças. Por exemplo girar o topo induz a permutação seguinte.

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

Nós definimos similarmente as outras permutações que correspondem a girar os outros lados. O grupo de permutações que corresponde ao cubo é o subgrupo de \(S_{48}\) gerado por essas permutações.

gap> e := (1,40,41,17)(4,37,44,20)(6,35,46,22)(9,14,16,11)(10,12,15,13);
gap> f := (6,16,43,25)(7,13,42,28)(8,11,41,30)(17,22,24,19)(18,20,23,21);
gap> d := (3,19,43,38)(5,21,45,36)(8,24,48,33)(25,30,32,27)(26,28,31,29);
gap> t := (1,27,48,14)(2,29,47,12)(3,32,46,9)(33,38,40,35)(34,36,39,37);
gap> b := (14,38,30,22)(15,39,31,23)(16,40,32,24)(41,46,48,43)(42,44,47,45);
gap> G := Group( c, e, f, d, t, b );
<permutation group with 6 generators>

Calculemos a ordem de \(G\). A ordem de \(G\) coincide com o número de configurações do cubo.

gap> Size( G );                     
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 ]
gap> Collected( last );
[ [ 2, 27 ], [ 3, 14 ], [ 5, 3 ], [ 7, 2 ], [ 11, 1 ] ]

Vamos ver como transformar uma configuração a um elemento de \(G\). Considere por exemplo a seguinte configuração.

                     +--------------+
                     |              |
                     |  16   4   46 |
                     |              |
                     |  13 CIMA  31 |
                     |              |
                     |  38   39   8 |
                     |              |
      +--------------+--------------+--------------+--------------+
      |              |              |              |              |
      |  22  20   32 | 48   47   19 | 25   45   14 | 40   10   41 |
      |              |              |              |              |
      | 29  ESQ   42 | 23 FRENTE  5 | 26 DIREIT 12 | 37   TRAS 36 |
      |              |              |              |              |
      | 27   15   43 | 24   21   11 | 6     7    9 | 35   34   33 |
      |              |              |              |              |
      +--------------+--------------+--------------+--------------+
                     |              |
                     | 30   28   17 |
                     |              |
                     | 44  BAIX  18 |
                     |              |
                     | 3     2   1  |
                     |              |
                     +--------------+

Note que, a peça 16 aparece no lugar de 1, 4 no lugar de 2, 46 no lugar de 3, etc. Nós precisamos construir a permutação que leva \[ 1\mapsto 16,\quad 2\mapsto 4,\quad 3\mapsto 46,\ldots \] Esta permutação pode ser construída usando as seguintes instruções.

gap> s := [16,4,46,13,31,38,39,8,22,20,32,29,42,27,15,43,48,47,19,23,5,24,21,11,25,45,14,26,12,6,7,9,40,10,41,37,36,35,34,33,30,28,17,44,18,3,2,1];
gap> x := PermList( s );            
(1,16,43,17,48)(2,4,13,42,28,26,45,18,47)(3,46)(5,31,7,39,34,10,20,23,21)(6,
38,35,41,30)(9,22,24,11,32)(12,29)(14,27)(33,40)(36,37)
gap> x in G;
true

11.3 Tarefa 1

Seja \(X\) um grupo. Lembre que uma série \[ X_0>X_1>X_2>\cdots>X_m=1 \] de subgrupos é dita série de composição se \(X_{i+1}\) é um subgrupo normal em \(X_i\) e \(X_i/X_{i+1}\) é um grupo simples para todo \(i\) (ou seja, \(X_i/X_{i+1}\) não possui subgrupo normal próprio e não trivial). A série de composição em um grupo, pode não ser única, mas sabemos pelo Teorema de Jordan-Holder que o comprimento das séries e os tipos de isomorfismo dos fatores (os fatores de composição) são unicamente determinados por \(X\). Estes fatores podem ser vistos como os blocos elementares do grupo similarmente aos fatores primos dos números naturais.

No seguinte exemplo simples vamos determinar os fatores de composição do grupo dihedral \(D_{10}\) (as simetrias do pentágono).

gap> G := DihedralGroup( 10 );
<pc group of size 10 with 2 generators>
gap> C := CompositionSeries( G );
[ Group([ f1, f2 ]), Group([ f2 ]), Group([  ]) ]
gap> List( [1..2], i->C[i]/C[i+1] );
[ Group([ f1, <identity> of ... ]), Group([ f2 ]) ]
gap> List( [1..2], i->StructureDescription(C[i]/C[i+1]) );
[ "C2", "C5" ]

Temos que a série de composição de \(D_{10}\) tem comprimento \(2\) e os dois fatores são cíclicos de ordem \(2\) e \(5\).

Agora responda às seguintes perguntas sobre o grupo \(G\) do cubo mágico.

  1. Qual é o comprimento da série de composição do grupo \(G\)?
  2. Quantos fatores são abelianos e quantos são não abelianos.
  3. Os fatores abelianos, sendo grupos simples, são cíclicos; determine as suas ordens.

11.4 Tarefa 2

Vamos estudar a estrutura permutacional do grupo \(G\).

  1. Determine as órbitas de \(G\) agindo no conjunto das 48 peças.
  2. Dê uma intepretação destas órbitas.
  3. Lembre que um subconjunto \(\Delta\) das peças chama-se bloco se \(\Delta g=\Delta\) ou \(\Delta g\cap \Delta=\emptyset\) vale para todo \(g\in G\). Determine os blocos contidos nas órbitas de \(G\).
  4. Dê interpretação destes blocos.

Use as funções Orbits (manual) e Blocks (manual).

11.5 Tarefa 3

Finalmente nós vamos resolver o cubo usando um homomorfismo do grupo livre em \(G\). Seja \(\mathcal F\) o grupo livre gerado pelos geradores \(C\), \(E\), \(F\), \(D\), \(T\), \(B\). Note que \(\mathcal F\) é gerado por \(6\) elementos e cada gerador de \(\mathcal F\) corresponde a um gerador de \(G\). A propriedade universal do grupo livre implica que o mapa \[ C\mapsto c,\ E\mapsto e, F\mapsto f,\ D\mapsto d,\ T\mapsto t,\ B\mapsto b \] pode ser estendido a um único homomorfismo \(\varphi:\mathcal F\to G\). Se \(g\in G\) e \(w\in\mathcal F\) é uma pré-imagem de \(g\), então \(w\) mostra como escrever \(g\) em uma palavra nos geradores de \(G\). Ou seja, \(w\) mostra como obter a configuração que corresponde ao elemento \(g\) como uma sequência dos \(6\) movimentos básicos.

Ilustramos esta ideia com um exemplo simpes usando o grupo \(D_{10}\).

gap> a := (1,2,3,4,5); b := (2,5)(3,4);
(1,2,3,4,5)
(2,5)(3,4)
gap> G := Group( a, b );
Group([ (1,2,3,4,5), (2,5)(3,4) ])
gap> Fr := FreeGroup( "A", "B" );
<free group on the generators [ A, B ]>
gap> hom := GroupHomomorphismByImages( Fr, G, GeneratorsOfGroup( Fr ), GeneratorsOfGroup( G ));
[ A, B ] -> [ (1,2,3,4,5), (2,5)(3,4) ]
gap> x := Random( G );
(1,4)(2,3)
gap> PreImagesRepresentative( hom, x );
A^-1*B^-1*A^-3

O resultado diz que a permutação \(x=(1,4)(2,3)\) pode ser obtida como a composição \(a^{-1}b^{-1}a^{-3}\). De fato

gap> a^-1*b^-1*a^-3 = x;
true
  1. Construa o grupo \(\mathcal F\) em cima em GAP usando FreeGroup (manual).
  2. Construa o homomorfismo \(\varphi\) em cima usando GroupHomomorphismByImages (manual).
  3. Considere a configuração do cubo na Seção 11.2. Construa a sequência dos movimentos que resulta nesta configuração.
  4. Considere uma configuração aleatória do cubo escolhendo um elemento aleatório de \(G\) (usando Random( G )). Construa a sequência dos movimentos que resulta nesta configuração aleatória.
  5. Usando um dos cubos disponibilizados por Igor, obtenha a configuração da Seção 11.2.

11.6 Tarefa 4

  1. Verifique que \(G\) pode ser gerado por 2 elementos.
  2. Ache um subconjunto minimal \(S\) do conjunto \(\{c,e,f,d,t,b\}\) de geradores tal que \(\left<S\right>=G\).
  3. Construa a configuração da Seção 11.2 usando apenas os movimentos do conjunto \(S\) no item anterior.
  4. Seja \(C\) o conjunto de 8 peças de canto (as peças que possuem 3 cores). O grupo \(G\) age sobre o conjunto \(C\). Mostre que \(G\) induz \(S_{8}\) sobre o conjunto dessas peças. Similarmente, seja \(L\) o conjunto das 12 peças laterias (as peças que possuem 2 cores). Mostre que \(G\) induz \(S_{12}\) sobre \(L\). (Isso explica os grupos \(A_8\) e \(A_{12}\) entre os fatores de composição de \(G\)). Use Action( G, conj, act )(manual).

No item 1., pegue, usando Random( G ), dois elementos aleatórios em \(G\) e verifique se o grupo gerado por eles coincide com \(G\).