Problema

<--->

1. Partir de uma configuração qualquer do cubo e chegar à configuração inicial (em que todas as faces têm a mesma cor) ou vice-versa.
2. O problema anterior terá solução partindo de facto de uma configuração qualquer? (Se desmontarmos o cubo podemos montá-lo sem nenhum cuidado especial e esperar que o problema tenha sempre solução?)

Notação de Singmaster

A cada face é atribuída uma letra que a identifica. U - Up F - Front R - Right D - Down B - Back L - Left

Movimentos do cubo

A rotação R:

Representando por K^-1 a rotação da face K de 90º no sentido contrário ao dos ponteiros do relógio, poderemos representar um "rearranjo" do cubo por meio de uma palavra no alfabeto

(Notando que K^-1=K³, podemos observar que a consideração do alfabeto {U, F, R, D, B, L} basta.)

É imediato reconhecer que as rotações não são mais que permutações do conjunto dos "cubinhos" que constituem o cubo e que executar rotações sucessivamente corresponde a compor essas permutações. Assim, não é surpreendente que RU^-1 e U^-1R não correspondam ao mesmo rearranjo do cubo, já que a composição de funções não é, em geral, comutativa.

RU-1:

R -->

U-1 -->

U-1R:

U-1 -->

R -->

(Note-se que estamos a compor as funções à direita.)

Terminologia e resultados básicos

Um pouco sobre permutações

Uma permutação é uma aplicação bijectiva de um conjunto em si próprio.

Exemplo

A permutação pode escrever-se como produto de ciclos (disjuntos) (1, 3, 6)(2, 8)(4, 7, 5) ou ainda como produto de transposições (1, 3)(1, 6)(2, 8)(4, 7)(4, 5).

É fácil ver que:

1. um ciclo de comprimento par se pode escrever como produto de um número ímpar de transposições;
   
2. um ciclo de comprimento ímpar se pode escrever como produto de um número par de transposições;
   [prova: (a₁, a₂, ... ,a_n)=(a₁, a₂)(a₁, a₃) ... (a₁, a_n)]
3. ciclos disjuntos comutam;
4. um ciclo de comprimento k tem ordem k (em particular, a permutação que esse ciclo representa composta consigo própria k vezes dá a permutação identidade).

Teorema. Nenhuma permutação se pode escrever como um produto de um número par e de um número ímpar de transposições.

Este resultado permite-nos definir permutação par e permutação ímpar.

Um pouco sobre grupos

Um grupo é um conjunto não vazio munido de uma operação binária associativa para a qual existe um elemento neutro e é tal que todo o elemento tem inverso.

Exemplo. O conjunto das permutações de um conjunto com n elementos munido da composição de funções é um grupo. Denota-se por S_n. O elemento neutro é a função identidade.

Mais alguns resultados simples:

1. a paridade é um homomorfismo do grupo das permutações de um conjunto finito em Z₂;
2. o conjunto das permutações pares de um conjunto com n elementos forma um grupo: o grupo alterno A_n, o qual tem índice 2 em S_n;
3. Os tri-ciclos (ciclos de comprimento 3) geram o grupo alterno (i.e., todo o elemento do grupo alterno se pode escrever como produto de tri-ciclos).
   [prova: (a, b)(a, c) = (a, b, c); (a, b)(c, d)= (a, c, d)(a, c, b)]

Um pouco sobre grafos

Para falar do cubo mágico é muitas vezes conveniente usar terminologia da teoria de grafos.

Vértices: são os cubinhos com 3 faces visíveis; Arestas: são os cubinhos com 2 faces visíveis;

Uma árvore é um grafo no qual dois quaisquer vértices podem ser ligados por exactamente um caminho.

O grupo de Rubik com o GAP

Ideal Toy Company stated on the package of
the original Rubik cube that there were more than
three billion possible states the cube could attain.
It's analogous to Mac Donald's proudly announcing
that they've sold more than 120 hamburgers.
(J. A. Paulos, Innumeracy)

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

Chamamos grupo de Rubik ao grupo < R, U, F, B, L, D > que pode ser fornecido ao GAP escrevendo, dentro de uma sessão GAP

cubo := Group( R, U, F, B, L, D);

Dentro dessa sessão pode depois saber-se qual a ordem do grupo, bem como a decomposição do resultado em factores primos. Basta escrever

n := Size(cubo); PrintFactorsInt(n); Print("\n");

Trata-se de um número bastante maior que 3 biliões (3*10¹²).

Orientação

Consideremos uma subárvore maximal do cubo (que estamos a ver como um grafo). A cada uma das arestas da árvore associamos uma face que a contenha. Existe exactamente uma maneira de ir de um vértice a outro usando um caminho na árvore.

Escolhemos um cubinho correspondente a um dos vértices e depois uma das faces desse cubinho, a qual marcamos com um símbolo '+'. Rodando a face associada a uma aresta da árvore que contenha esse cubinho, o símbolo '+' é transmitido também a outro vértice. Repetindo o processo, colocamos um símbolo '+' em cada um dos vértices do cubo. A escolha da árvore, das faces associadas às arestas da árvore e da face onde colocamos o primeiro símbolo '+' dá-nos uma posição standard para cada um dos vértices do cubo. Poderemos, por exemplo, dizer que um dos vértices foi rodado de 120º no sentido dos ponteiros do relógio relativamente à posição standard.

0 - se o vértice se encontrar na posição standard (também dizemos neste caso que o vértice se encontra orientado);

1 - se o vértice estiver rodado de 120º relativamente à posição standard;

2 - se o vértice estiver rodado de 240º relativamente à posição standard.

A cada rotação K associamos um vector v(K) de Z₃⁸ que nos dá o efeito de K na orientação dos vértices. (Para descrever v usamos uma certa numeração dos vértices.)

K v(K) U (0,1,0,0,0,2,0,0) F (2,0,0,1,0,0,0,0) R (0,2,0,0,0,1,0,0) D (1,0,0,2,2,0,0,1) B (0,0,0,0,0,1,0,2) L (0,0,1,0,0,0,1,1)

É claro que v pode ser estendida a um homomorfismo do grupo de Rubik em Z₃⁸.
Sendo v(K) = (v₁,v₂,v₃,v₄,v₅,v₆,v₇,v₈), tem-se

Orientação das arestas.

Pode fazer-se algo inteiramente análogo ao que se fez para os vértices.

Consideremos agora um grafo cujos vértices são as arestas do cubo e em que dois vértices estão ligados por uma aresta se pudermos ir de um a outro por meio de uma rotação. Escolhemos uma subárvore maximal deste grafo. (Aqui não há a necessidade de escolher uma face do cubo para cada aresta considerada, já que cada uma destas arestas está inteiramente contida numa das faces do cubo.) Numeramos também os vértices.

Podemos usar um processo análogo ao usado no caso dos vértices para colocar o símbolo '+' em exactamente uma das faces de cada aresta do cubo, obtendo assim uma posição standard para cada uma das arestas.

Podemos também definir um homomorfismo a(K) do grupo de Rubik em Z₂¹² que nos dá o efeito de K na orientação das arestas. Mostra-se que (com a notação apropriada) se tem também uma congruência da forma

Definimos assim uma aplicação

que a um elemento M do grupo de Rubik (i.e., uma configuração M do cubo) associa (v(M),p(M),a(M),q(M)). Esta aplicação é claramente injectiva. Não é sobrejectiva: basta notar que os a_i satisfazem uma condição não trivial. (Assim, o problema 2 tem uma resposta negativa: se desmontarmos o cubo devemos ter cuidado ao montá-lo.)

(Não se trata de um homomorfismo. Mostra-se, no entanto, que é um homomorfismo em

Seja M=K₁ ...K_n um movimento do cubo, ou seja, um elemento do grupo de Rubik em que os K_i são rotações. Como a paridade é um homomorfismo do grupo de Rubik em Z₂, tem-se paridade(p(M))=paridade(p(K₁))...paridade(p(K_n))=paridade(q(K₁))...paridade(q(K_n))=paridade(q(M)).

A menos de alguns detalhes, acabamos de demonstrar o seguinte

Teorema. Se um elemento (v,p,a,q) de

1. p e q têm a mesma paridade;
2. v₁+v₂+v₃+v₄+v₅+v₆+v₇+v₈ = 0 (mod 3). (Isto implica que numa configuração válida não pode haver exactamente 1 vértice não orientado.)
3. a₁+a₂+a₃+a₄+a₅+a₆+a₇+a₈+a₉+a₁₀+a₁₁+a₁₂ = 0 (mod 2). (Isto implica que numa configuração válida não pode haver exactamente 1 aresta não orientada e se houver exactamente duas arestas não orientadas, então uma está rodada de 120º e a outra de 240º relativamente às respectivas posições standard.)

Um algoritmo

Este resultado tem como consequência imediata que a ordem do grupo de Rubik é 3⁸/3 x 2¹²/2 x (8! x 12!)/2.

Uma demonstração construtiva do resultado dá-nos um algoritmo para resolver o cubo mágico (já que, partindo de uma configuração qualquer, nos permite construir as rotações necessárias para chegar a ela). Suponhamos então que temos uma configuração (v,p,a,q) do cubo satisfazendo as condições 1. 2. e 3. Pretendemos mostrar que se trata de uma configuração legal, ou seja, que se pode partir da configuração inicial e chegar a esta usando apenas rotações (ou, o que é o mesmo, partir desta e chegar, usando rotações, à configuração inicial).

Podemos supor que p e q são permutações pares, pois se fossem ambas ímpares executávamos uma rotação e passávamos a ter permutações pares.

Vamos fazer o cubo do modo seguinte:

1. colocamos as arestas nos lugares certos;
2. orientamos as arestas sem as trocar de posição;
3. colocamos os vértices nos lugares correctos sem mexer nas arestas;
4. orientamos os vértices sem mexer nas arestas e sem trocar os vértices de posição.

Um movimento a memorizar

C = [F, R^-1] = FR^-1F^-1R

F -->

R-1 -->

F-1 -->

R -->

Colocação das arestas

C = [F, R^-1] = FR^-1F^-1R

O comutador C é um tri-ciclo nas arestas:

Temos então que com C e seus conjugados se obtêm todos os tri-ciclos das arestas.

Como estamos a supor que p é uma permutação par e sabemos que os tri-ciclos geram todas as permutações pares, podemos, a partir de p, obter a identidade, o que significa colocar todas as arestas nos lugares certos.

Orientação das arestas

C[F^-1,U] = CF^-1UFU^-1

C -->

F-1 -->

U -->

F -->

U-1 -->

A permutação anterior inverte a orientação em duas arestas e deixa as restantes arestas fixas. Usando conjugação, a inversão da orientação pode ser feita para duas arestas quaisquer. Assim, uma vez colocadas todas as arestas nas posições correctas, podemos usar este tipo de movimento para as orientar. Aqui usamos a hipótese 3.

Colocação dos vértices

[C,D] = CDC^-1D^-1

C -->

D -->

C-1 -->

D-1 -->

A permutação anterior é um tri-ciclo nos vértices que deixa as arestas fixas. Usando conjugação, obtemos todos os tri-ciclos nos vértices. Usando agora a hipótese de p ser uma permutação par e o facto de os tri-ciclos gerarem todas as permutações pares, temos que este tipo de movimentos nos permite colocar os vértices nas posições correctas sem mexer nas arestas.

Orientação dos vértices

[C²,D] = C²DC^-2D^-1

C^2 -->

D -->

C-2 -->

D-1 -->

A permutação anterior faz rodar 2 vértices: um roda 120º e o outro 240º. Tudo o resto fica fixo. Usando conjugação, isto pode ser feito para dois vértices quaisquer. Agora usamos a hipótese 2 para concluir que podemos orientar todos os vértices.

Possíveis generalizações

Podem considerar-se cubos n x n x n. (O cubo mágico é o caso 3 X 3 x 3; o da figura seguinte é 4 x 4 x 4.) Este problema tem diferenças significativas relativamente ao problema do cubo [2].

Alguns apontadores