Universidade Estadual Paulista �Júlio de Mesquita Filho� Instituto de Geociências e Ciências Exatas Campus de Rio Claro Cubo Mágico: Propriedades e Resoluções envolvendo Álgebra e Teoria de Grupos Luis Gustavo Hau� Martins Grimm Dissertação apresentada ao Programa de Pós- Graduação � Mestrado Pro�ssional em Mate- mática em Rede Nacional � PROFMAT como requisito parcial para a obtenção do grau de Mestre Orientadora Profa. Dra. Carina Alves 2016 111 X111x Grimm, Luis Gustavo Hau� Martins Cubo Mágico: Propriedades e Resoluções envolvendo Álgebra e Teoria de Grupos/ Luis Gustavo Hau� Martins Grimm- Rio Claro: [s.n.], 2016. 81 f.: �g., tab. Dissertação (mestrado) - Universidade Estadual Paulista, Insti- tuto de Geociências e Ciências Exatas. Orientadora: Carina Alves 1. Cubo de Rubik. 2. Teoria de grupos. 3. Grupos de per- mutação. 4. Comutadores e conjugados. 5. Proposta didática. I. Título Ficha Catalográ�ca elaborada pela STATI - Biblioteca da UNESP Campus de Rio Claro/SP TERMO DE APROVAÇÃO Luis Gustavo Hau� Martins Grimm Cubo Mágico: Propriedades e Resoluções envolvendo Álgebra e Teoria de Grupos Dissertação aprovada como requisito parcial para a obtenção do grau de Mestre no Curso de Pós-Graduação Mestrado Pro�ssional em Matemática Universitária do Instituto de Geociências e Ciências Exatas da Universidade Estadual Paulista �Júlio de Mesquita Filho�, pela seguinte banca examina- dora: Profa. Dra. Carina Alves Orientadora Prof. Dr. Cristiane Alexandra Lázaro UNESP - Faculdade de Ciências - Bauru Prof. Dr. Agnaldo José Ferrari UNESP - Faculdade de Ciências - Bauru Rio Claro, 30 de agosto de 2016. À minha família Agradecimentos À minha esposa pelo apoio, incentivo, companhia nos estudos e pelo auxílio com o LATEX. À professora Carina Alves pela competência e paciência durante a orientação deste trabalho. A todos os professores do Mestrado Pro�ssional em Matemática em Rede Nacional da UNESP de Rio Claro pela contribuição nesse processo de formação continuada de pro�ssionais que atuam na educação básica. Aos funcionários da secretaria de pós-graduação da UNESP de Rio Claro pela aten- ção e empenho em ajudar prontamente. À Sociedade Brasileira de Matemática (SBM) por implementar o PROFMAT no Brasil, ao Departamento de Matemática da UNESP de Rio Claro pela apoio acadêmico e à Capes pelo apoio �nanceiro. Se você for curioso, encontrará quebra-cabeças em torno de você. Se você estiver determinado, irá resolvê-los. Ernö Rubik Resumo O cubo mágico é um dos quebra-cabeças mais famosos do mundo, e em geral atrai a atenção de muita gente, em especial a dos matemáticos. O desa�o, as formas, simetrias e movimentos induzem a ideia de estarmos diante de um objeto matemático. E podemos ir além. As ações e movimentos no cubo mágico são elementos que atendem a todas as condições da estrutura de um grupo, assim como também se relacionam com um grupo de permutações. À luz da Teoria de Grupos e dos Grupos de Permutações, iremos analisar algumas sequências de movimentos como os comutadores e conjugados. Existem vários algoritmos que resolvem o cubo mágico e que são fáceis de serem obtidos, por exemplo, na internet. O objetivo desta dissertação, além de trazer uma proposta de resolução, é o de proporcionar um caminho para além da simples memorização de um algoritmo, no sentido de compreendê-lo. Consequentemente, a justi�cativa para a possibilidade de se resolver um cubo mágico é de ordem matemática e não empírica. Palavras-chave: Cubo de Rubik, Teoria de grupos, Grupos de permutação, Comuta- dores e conjugados, Proposta didática. Abstract The Rubik's Cube is one of the most famous puzzle of the world, and generally at- tracts the attention of many people, especially mathematicians. The challenge, shapes, symmetries and movements induce the idea of being in front of a mathematical object. And we can go further. The actions and movements in the magic cube are elements that meet all the conditions of the structure of a group, as well as relate to a group of permutations. In light of the Group Theory and Permutations groups we will examine some sequences of movements such as commutators and conjugates. There are several algorithms that solve the magic cube and which are easy to obtain, for example, at the Internet. The aim of this dissertation, beyond to show a resolution, is to provide a path beyond simple memorization of an algorithm in order to understand it. Consequently, the justi�cation for the possibility of solving a Rubik's Cube is math and not empirical. Keywords: Rubik's cube, Group theory, Permutation group, Commutators and con- jugates, Didatic proposal. Lista de Figuras 2.1 Visão explodida de um cubo mágico 3× 3× 3. . . . . . . . . . . . . . . 21 2.2 Mecanismo interno de um cubo mágico 3× 3× 3. . . . . . . . . . . . . 22 2.3 Tipos e formatos derivados do cubo de Rubik. . . . . . . . . . . . . . . 23 2.4 Faces do cubo 3× 3× 3 e sua plani�cação. . . . . . . . . . . . . . . . . 23 2.5 Nomenclatura dos cubinhos. . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6 Eixos de rotação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.7 Exemplos de posição e orientação. . . . . . . . . . . . . . . . . . . . . . 25 2.8 Códigos das rotações das faces. . . . . . . . . . . . . . . . . . . . . . . 26 3.1 Quadrado representativo do grupo GQ. . . . . . . . . . . . . . . . . . . 30 3.2 Composição Rr ◦R1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Composição R1 ◦Rr. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4 Macros FR e RF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5 Macro F 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.1 Cubinhos afetados pela macro S. . . . . . . . . . . . . . . . . . . . . . 56 4.2 Cubinhos afetados pelo movimento F . . . . . . . . . . . . . . . . . . . 57 4.3 Efeito gerado pelas macros S e T . . . . . . . . . . . . . . . . . . . . . . 59 4.4 Permutação de 3 cubinhos de canto com alteração de suas orientações. 60 4.5 Permutação de 3 cubinhos de canto sem alteração de suas orientações. . 61 4.6 Rotação dos cubinhos de canto. . . . . . . . . . . . . . . . . . . . . . . 62 5.1 Sequência de montagem de cada uma das 4 etapas. . . . . . . . . . . . 68 6.1 Objetivo da Etapa 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.2 Objetivo da Etapa 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.3 Possibilidades da Etapa 2 � cubinhos na camada debaixo. . . . . . . . . 75 6.4 Possibilidades da Etapa 2 � cubinhos na camada superior. . . . . . . . 75 6.5 Objetivo da Etapa 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.6 Possibilidades da Etapa 3. . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.7 Possibilidades e objetivo da Etapa 4. . . . . . . . . . . . . . . . . . . . 77 6.8 Possibilidades e objetivo da Etapa 5. . . . . . . . . . . . . . . . . . . . 77 6.9 Possibilidades da Etapa 6. . . . . . . . . . . . . . . . . . . . . . . . . . 78 Lista de Tabelas 2.1 Nomes e códigos das faces . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.1 Grupos do algoritmo de Thistlethwaite . . . . . . . . . . . . . . . . . . 66 5.2 Etapas do método de Fridrich . . . . . . . . . . . . . . . . . . . . . . . 68 5.3 Etapas, objetivos e as macros necessárias. . . . . . . . . . . . . . . . . 71 Sumário 1 Introdução 19 2 O Cubo Mágico 21 2.1 Elementos de um cubo mágico e seu mecanismo . . . . . . . . . . . . . 21 2.2 Formatos e variações do cubo de Rubik . . . . . . . . . . . . . . . . . . 22 2.3 Movimentos das faces . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 Macro ou sequências de movimentos . . . . . . . . . . . . . . . . . . . . 26 3 Álgebra no Cubo Mágico 29 3.1 Teoria Básica de Grupos . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Grupos aditivos e multiplicativos de classes de restos . . . . . . . . . . 31 3.3 Classes Laterais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4 Grupo de Rubik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.5 Subgrupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5.1 Subgrupo gerado por um subconjunto . . . . . . . . . . . . . . . 38 3.6 Subgrupos Normais e Grupos Quocientes . . . . . . . . . . . . . . . . . 39 3.7 Homomor�smos de Grupos . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.8 Permutações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.8.1 Produto de Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.8.2 Repetição de ciclos e ordem . . . . . . . . . . . . . . . . . . . . 49 3.9 Assinatura de uma Permutação . . . . . . . . . . . . . . . . . . . . . . 50 3.9.1 Paridade de Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . 52 4 Aplicações da Teoria de Grupos e Grupos de Permutação no Cubo Mágico 55 4.1 Calculando a ordem de uma macro . . . . . . . . . . . . . . . . . . . . 55 4.2 Paridade dos movimentos das faces . . . . . . . . . . . . . . . . . . . . 56 4.3 Calculando o número de posições do cubo mágico . . . . . . . . . . . . 58 4.4 Comutadores e conjugados . . . . . . . . . . . . . . . . . . . . . . . . . 58 5 Resolvendo o Cubo Mágico 63 5.1 Resolvendo o Cubo Mágico com o menor número de movimentos . . . . 64 5.1.1 Método realizado por computador . . . . . . . . . . . . . . . . . 64 5.1.2 Método realizável por humanos . . . . . . . . . . . . . . . . . . 66 5.2 Resolvendo o Cubo Mágico no menor tempo . . . . . . . . . . . . . . . 67 5.3 Resolvendo o Cubo Mágico com a menor memorização . . . . . . . . . 68 5.3.1 1a Etapa: formar uma cruz na face inicial . . . . . . . . . . . . 69 5.3.2 2a Etapa: formar uma cruz nas faces adjacentes . . . . . . . . . 69 5.3.3 3a Etapa: formar uma cruz na face oposta à inicial . . . . . . . 69 5.3.4 4a Etapa: posicionar os cubinhos de canto . . . . . . . . . . . . 70 5.3.5 5a Etapa: orientar os cubinhos de canto . . . . . . . . . . . . . . 70 5.3.6 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6 Aplicação Escolar 73 6.1 Apresentação e funcionamento do cubo mágico . . . . . . . . . . . . . . 73 6.2 Códigos de cada movimento . . . . . . . . . . . . . . . . . . . . . . . . 73 6.3 Resolução do Cubo Mágico pelo método de camadas . . . . . . . . . . 74 6.3.1 Etapa 1: Formar uma cruz branca . . . . . . . . . . . . . . . . . 74 6.3.2 Etapa 2: Posicionar os cantos brancos . . . . . . . . . . . . . . 74 6.3.3 Etapa 3: Resolver a camada do meio . . . . . . . . . . . . . . . 76 6.3.4 Etapa 4: Formar uma cruz amarela . . . . . . . . . . . . . . . . 77 6.3.5 Etapa 5: Resolver a camada superior . . . . . . . . . . . . . . . 77 6.3.6 Etapa 6: Orientar os cubinhos de canto da camada superior . . 78 6.3.7 Etapa 7: Posicionar os cubinhos de aresta da camada superior . 78 Referências 81 1 Introdução Durante décadas o desa�o da resolução do cubo mágico, também chamado de cubo de Rubik, em homenagem ao seu inventor, intrigou muita gente. Ernö Rubik nasceu em 13 de julho de 1944 em Budapeste, Hungria e na década de 70 dava aulas de arqui- tetura na School for Commercial Artists. Em 1974 teve a ideia de construir um cubo capaz de rotacionar suas faces para que então pudesse ilustrar melhor para seus alunos o conceito tridimensional. O primeiro exemplar era de madeira e cada uma das seis faces do cubo era pintada de uma cor diferente. Cada face é dividida em 9 cubinhos menores totalizando 26 cubos visíveis e um virtual que se existisse estaria localizado no interior do cubo. Este 27o cubinho virtual é justamente o mecanismo que prende as 6 faces. No mesmo ano da criação, o cubo de Rubik ganhou o prêmio alemão de jogo do ano. Ernö Rubik não tinha exatamente a intenção de criar um quebra�cabeça cuja solução consiste em deixar cada uma das faces somente com uma cor. O pró- prio criador do cubo demorou cerca de um mês para remontá-lo à sua con�guração inicial. Em 1980 o cubo começou a ser produzido de forma industrial e estima�se que desde então já tenham sido vendidos mais de 350 milhões de unidades em todo o mundo. Inicialmente, no Capítulo 2, iremos trazer noções sobre seu mecanismo de funci- onamento e quais movimentos são permitidos efetuar. Esta primeira apresentação é necessária para entendermos o que é e como funciona um cubo mágico. E, além disso, os movimentos das faces, bem como dos cubinhos, são o objetivo alvo deste trabalho, pois são estes os elementos que iremos estudar mais adiante. No Capítulo 3 iremos abordar alguns conceitos básicos sobre a Teoria de Grupos e Grupos de Permutações. A partir deles identi�caremos o cubo mágico como um objeto matemático, assim como as ações e os movimentos no cubo serão identi�cados como operações que atendem às de�nições que serão vistas. No Capítulo 4 iremos aplicar os conceitos abordados, no intuito de entendermos alguns movimentos, estados e algoritmos que resolvem o cubo mágico. Além disso, calcularemos o número total de con�gurações que o cubo mágico pode assumir, jun- tamente com a justi�cativa de que algumas con�gurações são impossíveis de serem 19 20 Introdução atingidas. Finalmente, nos dois últimos capítulos poderemos nos aprofundar nos algoritmos de resolução. No Capítulo 5 iremos apresentar e detalhar três formas diferentes de re- solução: com menos movimentos, em menor tempo e com menor memorização. Neste último iremos apresentar um método de resolução baseado nos conceitos que foram abordados nos capítulos anteriores. Tal método exige um certo conhecimento e fa- miliaridade com o cubo mágico. Já no Capítulo 6 mostraremos outro método que é recomendado a iniciantes. Por este motivo, nos basearemos neste método para sugerir uma proposta didática. Neste capítulo será detalhado todas os estados e sequências necessários à resolução do cubo mágico, sem nos preocuparmos com qualquer demons- tração, e sim apenas como um método memorizável. 2 O Cubo Mágico O entendimento e familiaridade com o cubo mágico dependem de conhecermos certos conceitos que o cercam, como sua estrutura, código dos elementos (cubinhos, faces e movimentos) e até mesmo sua manipulação. Veremos que o modo como o seguramos é crucial para chegarmos à sua resolução. Ao longo deste capítulo faremos a descrição de todos os conceitos necessários para iniciarmos nosso estudo sobre o cubo de Rubik. 2.1 Elementos de um cubo mágico e seu mecanismo Primeiramente vamos descrever e classi�car todos os 26 cubinhos que compõem o cubo mágico. Nem todas as faces dos cubinhos são visíveis, dependendo de sua posição no cubo eles apresentam 1, 2 ou 3 faces visíveis. Podemos quanti�car e classi�car os cubinhos de 3 maneiras: • 6 cubinhos chamados de centrais por estarem no centro das faces do cubo, onde só uma face é visível; • 12 cubinhos chamados de aresta, ou de meio, e que compõem a aresta do cubo, onde duas faces são visíveis; • 8 cubinhos chamados de canto, ou de quina, e que são os vértices do cubo, onde três de suas faces são visíveis. Figura 2.1: Visão explodida de um cubo mágico 3× 3× 3. 21 22 O Cubo Mágico A �gura 2.1 mostra um cubo mágico 3× 3× 3 de modo a visualizarmos sua mon- tagem. Os cubinhos centrais são os que determinam qual será a cor da face do cubo e o único movimento que eles realizam é o de rotação em torno do eixo que os prende ao mecanismo central. Dizemos que estes cubinhos são �xos. A Figura 2.2 ilustra o mecanismo interno onde podemos observar que o cubinho central é �xo e seu único movimento permitido é o de rotação em torno do eixo que o prende. Figura 2.2: Mecanismo interno de um cubo mágico 3× 3× 3. 2.2 Formatos e variações do cubo de Rubik Existem dezenas de tipos, formatos e tamanhos de cubo mágico. O próprio Rubik quando idealizou o cubo pensou em um cubo 2× 2× 2, entretanto a ideia de construir a con�guração, que se tornou a mais famosa, surgiu do fato de que ele queria manter os centros �xos. O conceito do quebra cabeça se expandiu e muitos deixaram de ter o formato cúbico, sendo utilizadas outras formas geométricas como um tetraedro ou então um dodecaedro. Existem também aqueles com formas irregulares. A Figura 2.3 traz, dentre as dezenas, 60 tipos e formatos derivados do cubo de Rubik. O formato mais comum é o cubo 3× 3× 3 de 5,7 cm de aresta e de faces pintadas nas cores branca, amarela, azul, verde, vermelho e laranja. A Figura 2.4 ilustra esta con�guração. A compreensão dos movimentos e até da solução do cubo mágico dependem do modo como realizamos as rotações das faces. Mas para isso precisamos estabelecer uma referência que geralmente é a face que �ca voltada para frente de quem manipula o cubo. O nome das faces é dado em função de sua posição quando olhamos para o cubo de frente. O padrão mais comum é baseado nos termos em inglês, de forma abreviada, estabelecendo um código. A Tabela 2.1 mostra o nome das faces, em ambos os idiomas e com seus respectivos códigos. Formatos e variações do cubo de Rubik 23 Figura 2.3: Tipos e formatos derivados do cubo de Rubik. Figura 2.4: Faces do cubo 3× 3× 3 e sua plani�cação. Tabela 2.1: Nomes e códigos das faces Português Inglês Código Frente Front F Trás Back B Direita Right R Esquerda Left L Cima Up U Baixo Down D Para facilitar a visualização dos movimentos dos cubinhos vamos estabelecer uma nomenclatura para cada um deles utilizando a mesma referência citada na seção ante- rior, isto é, a face da frente. A nomenclatura é baseada na intersecção das faces em que o cubinho se encontra. Por exemplo, o cubinho de aresta que estiver na interseção da face da frente (F ) com a face de cima (U) será chamado de FU e o cubinho de canto que estiver na intersecção da face de trás (B), com a face da direita (R) e com a face de cima (U) será chamado de BRU . A �gura abaixo ilustra a nomenclatura de todos 24 O Cubo Mágico os cubinhos do cubo mágico. Figura 2.5: Nomenclatura dos cubinhos. Observação 2.1. Não há distinção entre as ordens com que a notação é escrita, ou seja, FRD = FDR = RFD = RDF = FRD = FDR. 2.3 Movimentos das faces O mecanismo interno permite que cada face tenha a liberdade de rotação de 0◦ a 360◦ em torno do eixo que �xa o cubinho central ao mecanismo interno, tanto no sentido horário quanto anti-horário tomando como referência sempre a face que �ca à frente de quem manipula o cubo. Figura 2.6: Eixos de rotação. O movimento será completo (vide Figura 2.6) quando a face for rotacionada de 90◦, em qualquer um dos dois sentidos. É fácil observar que se aplicarmos, em uma Movimentos das faces 25 determinada face, quatro vezes repetida o movimento completo o cubo não é alterado, ou seja, é uma operação neutra. Nos métodos mais tradicionais de resolução do cubo utilizam-se códigos para iden- ti�car cada movimento de rotação das faces. Estes códigos seguem a mesma lógica da nomenclatura das faces, isto é, a primeira letra maiúscula do nome do lado, em inglês. Para distinguir a rotação no sentido horário ou anti-horário, geralmente são utilizados dois símbolos: uma apóstrofe sobrescrita na letra ou a letra seguida de um i minúsculo. Por exemplo, se quisermos realizar um movimento da face direita uma vez no sentido anti-horário escrevemos1 R ′ ou Ri. Cada cubinho do cubo mágico possui uma posição e uma orientação. • De�nimos como posição, o local correto em que o cubinho deve se encontrar em relação aos cubinhos de centro. • De�nimos como orientação a con�guração correta que as cores de um determi- nado cubinho deve se encontrar em relação aos cubinhos de centro. Figura 2.7: Exemplos de posição e orientação. Um cubinho de aresta pode estar na sua posição correta, porém com sua orientação invertida. O mesmo pode ocorrer com um cubinho de quina. Note por estas duas 1O código mais comum utilizado é a letra com a apóstrofe sobrescrita. 26 O Cubo Mágico razões um cubinho de aresta possui 12 posições diferentes para assumir, 1 correta e 11 erradas, assim como suas cores podem assumir 2 orientações diferentes, 1 correta e 1 errada. Analogamente um cubinho de quina possui 8 posições diferentes para assumir, 1 correta e 7 erradas, assim como suas cores podem assumir 3 orientações diferentes, 1 correta e 2 erradas. Vejamos alguns exemplos tanto de posição e orientação corretos e incorretos na �gura 2.7. 2.4 Macro ou sequências de movimentos Figura 2.8: Códigos das rotações das faces. Uma sequência de movimentos é descrita pela sequência de códigos das rotações que se deseja efetuar, escrita da esquerda para a direita na mesma ordem em que as operações devem ser realizadas e tomando como referência a face que está à frente de quem o manuseia. A esta sequência daremos o nome de macro. Quando uma sequência ou uma macro for aplicada no cubo uma importante regra deve ser seguida: uma vez iniciada a sequência a face frontal de referência não pode ser alterada até que ela seja concluída. Qualquer rotação do próprio cubo em qualquer direção e sentido irá inter- ferir na sequência. Por esta razão, quando uma sequência de movimentos é efetuada, as únicas rotações que devem ser aplicadas serão somente nas faces respectivas ao có- digo. A Figura 2.8 ilustra os códigos mais utilizados nos algoritmos de solução do cubo. Agora vamos supor que queremos efetuar quatro movimentos seguidos na seguinte ordem: uma rotação da face superior no sentido horário, uma rotação da face direita no sentido horário, uma rotação da face superior no sentido anti-horário e uma rotação da face direita no sentido anti-horário. O código para esta macro S será: S = URU ′ R ′ . Macro ou sequências de movimentos 27 Caso se queira aplicar um mesmo movimento X mais de uma vez, utiliza-se a se- guinte notação: S = XX = X2, T = XXX = X3, etc. Por exemplo, para se efetuar duas rotações consecutivas da face superior no sentido horário escreve-se: S = U2. Como é possível perceber, a codi�cação dos movimentos é essencial, a �m de tornar tanto a leitura quanto a própria execução das macros mais simples e ágil2. No Capítulo 5 voltaremos a tratar dos códigos e sequências que compõem os algoritmos que levam à solução do cubo. 2A criação de códigos na Matemática é algo crucial para o seu próprio desenvolvimento e entendi- mento, e no cubo a ideia não é diferente. 3 Álgebra no Cubo Mágico Neste capítulo vamos abordar conceitos básicos de Álgebra, que podem ser encon- trados nas referências [1], [2], [3] e [4] como, por exemplo, a teoria de grupos e grupos de permutação, com o objetivo de relacionar movimentos especí�cos do cubo mágico com tais conceitos. A ideia é utilizar estas duas teorias para auxiliar a obtenção de macros que possibilitem, uma vez que o cubo esteja embaralhado, retorná�lo à posição original, isto é, as 6 faces estarem todas com suas respectivas cores. 3.1 Teoria Básica de Grupos De�nição 3.1. Um conjunto G não vazio, com uma determinada operação (∗) tal que G×G→ G (a, b) 7→ a ∗ b será chamado de grupo e denotamos por (G, ∗) se as três seguintes condições para tal operação forem satisfeitas: 1. Associatividade: a ∗ (b ∗ c) = (a ∗ b) ∗ c, ∀a, b, c ∈ G. 2. Elemento neutro: ∃ e ∈ G tal que e ∗ a = a ∗ e = a, ∀a ∈ G. 3. Elemento simétrico: ∀a ∈ G, ∃ a′ ∈ G tal que a ∗ a′ = a′ ∗ a = e. Um grupo é chamado de abeliano ou comutativo se apresenta também a seguinte condição: 4. Comutatividade: a ∗ b = b ∗ a, ∀a, b ∈ G. 29 30 Álgebra no Cubo Mágico Exemplo 3.1. Grupos: 1. (Z,+), (Q,+), (R,+), (C,+) são grupos aditivos e (Q \ {0} , ·), (R \ {0} , ·) e (C \ {0} , ·) são grupos multiplicativos. Note que todos eles são grupos abelianos, pois em todos eles a propriedade comutativa é válida. 2. Para aplicar propriedades da Álgebra no cubo mágico, vejamos um exemplo ge- ométrico, onde escreveremos o grupo GQ referente às simetrias espaciais de um quadrado. Seja Q1Q2Q3Q4 um quadrado cujo centro está na origem O dos eixos cartesia- nos. Chamaremos as retas que passam pelas diagonais do quadrado e por suas mediatrizes de d1, d2, r e s, respectivamente, conforme a Figura 3.1. Figura 3.1: Quadrado representativo do grupo GQ. As transformações espaciais (simetrias) que preservam a forma do quadrado po- dem ocorrer tanto no plano quanto no espaço: • Transformações planas: Denotaremos por id, Rπ 2 , Rπ e R 3π 2 as rotações em torno da origem O do quadrado, de ângulos 0, π 2 , π e 3π 2 , no sentido anti�horário, respectivamente. • Transformações espaciais: Denotaremos por R1, R2, Rr e Rs as rotações de ângulo π em relação aos eixos d1, d2, r e s, respectivamente. Assim GQ = { id, Rπ 2 , Rπ, R 3π 2 , R1, R2, Rr, Rs } e com a operação de composição de funções é um grupo. Note que o grupo GQ não é abeliano, pois a propriedade comutativa não é veri�- cada. De fato, vamos veri�car que as composições Rr◦R1 e R1◦Rr não são iguais. Grupos aditivos e multiplicativos de classes de restos 31 Figura 3.2: Composição Rr ◦R1. Logo Rr ◦R1 = Rπ 2 . Figura 3.3: Composição R1 ◦Rr. Logo R1 ◦Rr = R 3π 2 . Veremos mais adiante que o Grupo de Rubik não é abeliano. Em particular este é um dos motivos pelo qual o Cubo de Rubik apresenta alto nível de di�culdade em ser resolvido. 3.2 Grupos aditivos e multiplicativos de classes de restos O conjunto das classes de resto módulo m, é o conjunto quociente de Z pela relação de congruência, módulo m. Isto é Zm = {0, 1, 2, . . . ,m− 1},∀m > 1;m ∈ Z. Sendo assim 0 é formado por todos os inteiros côngruos a 0, módulo m, 1 por todos os inteiros côngruos a 1, módulo m, e assim sucessivamente. Agora seja a operação (+) de adição módulo m sobre Zm, a qual vale a associati- vidade e a comutatividade e que é de�nida de�nida por a+ b = a+ b, onde a, b ∈ Zm. Em relação à esta operação existe um elemento neutro e um oposto: 32 Álgebra no Cubo Mágico a+ 0 = a+ 0 = a. Portanto, 0 é o elemento neutro. a+m− a = a+ (m− a) = m = 0, já que m ≡ 0 (modm) Portanto, −a = m− a é o elemento oposto. Assim, (Zm,+) é um grupo abeliano, para todo inteiro m > 1, que é chamado de grupo aditivo de classes de resto módulo m. Note que a ordem deste grupo é m. Agora seja também a operação (·) de multiplicação módulo m em Zm onde também são válidas a associatividade e a comutatividade e que é de�nida por: a · b = ab, onde a, b ∈ Zm. Em relação à esta operação existe um elemento neutro: a · 1 = a · 1 = a. Portanto 1 é o elemento neutro. Agora é preciso notar que o elemento 0 não está de�nido no conjunto Zm com a ope- ração (·), pois ele não apresenta um inverso na multiplicação módulo m, logo devemos considerar apenas o conjunto Zm − {0}. Entretanto, mesmo observada esta restrição, não há garantias de que o conjunto restante será um grupo multiplicativo. Com efeito, temos que a restrição para a multiplicação módulo 4 aos elementos de Z4 − {0}, nem sequer é uma operação sobre este conjunto, uma vez que 2 · 2 = 4 = 0. Neste sentido, provaremos que a multiplicação módulo m aplicada aos elementos de Z∗m = Zm − {0} é uma operação sobre este conjunto se, e somente se, m é um número primo. Primeiramente vamos supor, por absurdo, que m não é primo. Como m > 1, podemos obter dois inteiros a, b > 1 tais que ab = m. Logo ab = m. E neste caso, como ab = a · b e m = 0, então teríamos que a · b = 0, o que é absurdo pela hipótese. Por outro lado, vamos supor, por absurdo, que ab = 0 para algum a, b ∈ Z∗m. Consequentemente temos que ab ≡ 0 (mod m). Logo, m | ab, e como por hipótese m é primo, então m | a ou m | b. Sem perda de generalidade vamos supor o primeiro caso, o que implica que a = mq, para algum inteiro q, e portanto temos: a = mq = m · q = 0 · q = 0 Classes Laterais 33 o que é absurdo, já que por hipótese a ∈ Z∗m. Por �m, vamos mostrar que, se m é primo, a multiplicação módulo m, quando restrita aos elementos de Z∗m, faz desse conjunto um grupo. Para isto, basta mostrar que ∀ a ∈ Z∗m, pode-se encontrar b ∈ Z∗m tal que a · b = 1. Com efeito, se a ∈ Z∗m, então a não é múltiplo de m, e como m é primo, então mdc(m, a) = 1. Logo, podemos escrever mx0 + ay0 = 1, para convenientes inteiros x0 e y0 (identidade de Bezout). Reduzindo-se essa igualdade módulo m temos: mx0 + ay0 = 1 = m · x0 + a · y0 = a · y0 = 1 onde obtemos que y0, que pertence a Z∗m, é o inverso de a. Assim, (Z∗m, ·) é um grupo, se e somente se, m é um número primo. Vejamos um exemplo: Exemplo 3.2. Usando o raciocínio utilizado na demosntração acima, vamos deter- minar o inverso de 4 em Z∗5. Logo, uma possível solução para a equação Diofantina 5x0 + 4y0 = 1 pode ser o par (x0, y0) = (1,−1), ou seja, y0 = −1. Portanto o inverso de 4 é −1 = 4, pois 4 ≡ −1 (mod 5). 3.3 Classes Laterais Seja G um grupo e seja H um subgrupo de G. À respeito de G, de�nimos a relação de equivalência ∼ E da seguinte maneira: y ∼ E x⇔ ∃ h ∈ H tal que y = xh. Por de�nição, a classe de equivalência que contém o elemento x é o conjunto{ y ∈ g | y ∼ E x } = {xh | h ∈ H}; denotaremos este conjunto por xH e o chamare- mos de classe lateral à esquerda de H em G que contém x. Caso não haja confusão, simplesmente a chamaremos de classe lateral de x à esquerda. Em particular, H é a classe lateral do elemento neutro e à esquerda. Observe que y ∈ xH ⇔ yH = xH. De maneira análoga, podemos ainda de�nir a seguinte relação de equivalência: y ∼ D x⇔ ∃h ∈ H tal que y = hx. Desta forma obtemos as classes laterais à direita de H em G. Portanto a classe lateral de x à direita é Hx = {hx | h ∈ H}. De�nição 3.2. A cardinalidade do conjunto das classes laterais à esquerda é o índíce de H em G. Denotaremos ele por (G : H). Observação 3.1. O índice de H em G também é a cardinalidade do conjunto das classes laterais à direita de H em G, pois a aplicação ϕ abaixo é uma bijeção: 34 Álgebra no Cubo Mágico ϕ : {classes laterais à esquerda} → {classes laterais à direita} xH → Hx−1 De�nição 3.3. Dada uma partição de um conjunto, um sistema de representantes é um conjunto {xα}α∈Γ que tem exatamente um elemento em cada subconjunto da partição. Em particular, a cardinalidade de qualquer sistema de presentantes das classes laterais à esquerda de H em G é igual a (G : H). Proposição 3.1. Todas as classes laterais de H em G têm a mesma cardinalidade, igual à cardinalidade de H. Demonstração. A função H → xH h 7→ xh é claramente uma bijeção. Teorema 3.1. (Teorema de Lagrange) Sejam G um grupo �nito e H um subgrupo de G. Então teremos |G| = |H|(G : H). Em particular, a ordem e o índice de H dividem a ordem de G. Demonstração. Vamos considerar a relação de equivalência à esquerda ∼ E em G. Desta forma iremos obter uma partição deG em classes de equivalência. A proposição anterior mostra que em cada uma dessas classes temos |H| elementos. Como, por de�nição, o número de classes é (G : H), temos a igualdade |G| = |H|(G : H) Corolário 3.1. Seja G um grupo �nito e seja α ∈ G. Então a ordem de α divide a ordem de G. Demonstração. Por de�nição, O(α) = |〈α〉|. Por �m aplicamos o Teorema de Lagrange ao subgrupo 〈α〉. Note que, equivalentemente, este corolário mostra que α|G| = e Corolário 3.2. Seja G um grupo de ordem prima. Então G é cíclico. Demonstração. Seja α ∈ G \ {e} e considere 〈α〉 o subgrupo gerado por α. Pelo Teorema de Lagrange, |〈α〉| divide |G| e portanto |〈α〉| = |G|, pois |G| é primo. Logo G = 〈G〉. 3.4 Grupo de Rubik Conforme visto no Capítulo 2, chamamos de R, L, F , B, U e D, os movimentos no sentido horário das faces direita, esquerda, frente, trás, cima e baixo, respectivamente. O conjunto de todos os movimentos permitidos no cubo, por exemplo, ao embaralhá-lo, chamaremos de Grupo R de Rubik. Vamos veri�car a existência das três condições que satisfazem a de�nição de grupo para o cubo de Rubik: Grupo de Rubik 35 1. Associatividade: Ao realizarmos uma sequência qualquer, por exemplo, de 3 movimentos genéricos X, Y , Z, veri�camos que: X(Y Z) = (XY )Z. Ao manipular o cubo a prova desta condição é evidente e a consideraremos como trivial. 2. Elemento neutro: A existência do elemento neutro é veri�cada pelo movimento �não fazer nada� em qualquer das 6 faces. Com isso garantimos a identidade I de qualquer uma das seis faces do cubo ou de qualquer sequência de movimentos. 3. Elemento inverso: O elemento inverso no GrupoR de Rubik signi�ca desfazer a sequência, de um ou mais movimentos, realizada. E aqui há duas importantes considerações a serem feitas: se o movimento foi de apenas uma face ou de uma macro. Seja um mo- vimento genérico X, uma rotação de uma das 6 faces de 90◦ no sentido horário, então seu elemento inverso será o movimento, também de 90◦, desta mesma face, porém no sentido anti-horário. Denotaremos este elemento inverso de X como sendo X−1 ou simplesmente X ′. Caso seja feito uma sequência de movimentos, então o elemento inverso será a realização dos inversos dos movimentos, porém na ordem inversa, como no exemplo a seguir. Exemplo 3.3. Seja uma macro S = FR ′ U , então seu inverso será S−1 = U ′ RF ′ . Observação 3.2. O elemento inverso em um grupo é único, por isso que no caso do cubo mágico é necessário que ele esteja bem de�nido para que se evite duplicidade quando se deseja obter o elemento inverso de um movimento ou o de uma combinação de movimentos. Por este motivo, devemos ter claro que realizar apenas um movimento é um caso particular de se realizar uma sequência de movimentos, e com isso garanti- mos a unicidade do elemento neutro dentro do Grupo R de Rubik. Apesar de valer a propriedade comutativa entre movimentos em faces opostas, a mesma não é veri�cada entre movimentos em faces adjacentes. Os movimentos FR e RF não são iguais, conforme a Figura 3.4. Alguns exemplos de movimentos comutativos são: FB = BF,RL = LR e UD = DU 36 Álgebra no Cubo Mágico Figura 3.4: Macros FR e RF . Portanto, concluímos que o Grupo R de Rubik não é abeliano. Este fato torna o cubo, em particular, um quebra-cabeças difícil de ser resolvido. 3.5 Subgrupos De�nição 3.4. Seja (G, ∗) um grupo, chamaremos de subgrupo de G, um subconjunto H de G não vazio (denotaremos por H < G) quando com a operação de G, este subconjunto H é um grupo com as seguintes condições satisfeitas para cada elemento h de H: 1. Fechamento: h1 ∗ h2 ∈ H, ∀h1, h2 ∈ H. 2. Associatividade: h1 ∗ (h2 ∗ h3) = (h1 ∗ h2) ∗ h3, ∀h1, h2, h3 ∈ H. 3. Elemento neutro: ∃eh ∈ H tal que eh ∗ h = h ∗ eh = h, ∀h ∈ H. 4. Elemento simétrico: ∀h ∈ H, ∃h‘ ∈ H tal que h ∗ h‘ = h‘ ∗ h = eh. Observação 3.3. A condição 2 é sempre satisfeita, pois a igualdade g1 ∗ (g2 ∗ g3) = (g1 ∗ g2) ∗ g3, é válida para todos os elementos de G. Subgrupos 37 Observação 3.4. O elemento neutro eh de H é necessariamente igual ao elemento neutro e de G. De fato, sejam e e eh, respectivamente os elementos neutros de G e H. Como eh ∗ eh = eh = eh ∗ e e para todo elemento do grupo é válido em relação à operação ∗, então e = eh. Observação 3.5. Dado h ∈ H, o inverso de h em H é necessariamente igual ao inverso de h em G. De fato, seja um elemento b ∈ H e indiquemos por b‘ e b‘ h seus simétricos em G e H, respectivamente. Como, porém, b‘ h ∗ b = eh = e = b‘ ∗ b então b‘ h = b‘. Na prática, para veri�car que um subconjunto H é um subgrupo de um grupo G, basta usarmos a seguinte proposição: Proposição 3.2. Seja (G, ∗) um grupo. Para que um conjunto, não vazio, H ⊂ G seja um subgrupo de G, é necessário e su�ciente que a ∗ b‘ seja um elemento de H sempre que a e b pertencerem a este conjunto. Demonstração. (⇒) Se a, b ∈ H, então a ∗ b‘ h ∈ H já que, por hipótese, (H, ∗) é um grupo. Mas pela observação 3.4 temos que b‘ h = b‘ e, portanto, a ∗ b‘ ∈ H. (⇐) Como, por hipótese, H é não vazio, então é possível considerarmos um ele- mento qualquer x0 ∈ H. Por este fato, e pela hipótese temos que x0 ∗ x‘ 0 = e ∈ H. Considerando agora um elemento b ∈ H, da hipótese e da conclusão anterior segue que: e ∗ b‘ = b‘ ∈ H. Agora vamos mostrar que H é fechado em relação à operação ∗. Com efeito, se a, b ∈ H, então pela conclusão anterior, a, b‘ ∈ H. De onde, usando novamente a hipótese, temos que: a ∗ (b‘)‘ = a ∗ b ∈ H. A associatividade em H é imediata, pois se a, b, c ∈ H, então a, b, c ∈ G e, portanto a ∗ (b ∗ c) = (a ∗ b) ∗ c (uma vez que essa propriedade é válida em G). Vejamos alguns exemplos: Exemplo 3.4. Se G é um grupo, então {e} e G são subgrupos de G, chamados de subgrupos triviais de G. 38 Álgebra no Cubo Mágico Exemplo 3.5. (2Z,+) é um subgrupo de (Z,+). De maneira mais geral, se n é um inteiro qualquer, (nZ,+) é um subgrupo de (Z,+). Exemplo 3.6. {id, Rπ} e { id, Rπ 2 , Rπ, R 3π 2 } são subgrupos de GQ. 3.5.1 Subgrupo gerado por um subconjunto Usaremos aqui a notação multiplicativa, por ser mais simples e de uso mais frequente em Teoria dos Grupos. Sejam G um grupo e S um subconjunto não vazio de G. Utilizaremos a seguinte notação: < S >= {a1 · a2 · ... · an;n ∈ N, ai ∈ S ou a−1 i ∈ S} Quando S é �nito da forma S = {a1, a2, ..., am} é comum denotarmos simplesmente por: 〈S〉 = 〈a1 · a2 · ... · am〉 no lugar de 〈S〉 = 〈{a1, a2, ..., am}〉 Note que se g ∈ G então 〈g〉 = {..., (g−1)2, g−1, e, g, g2, ...} E ainda, se usarmos a notação g−r para (g−1)r, r ∈ N teremos: 〈g〉 = {gt; t ∈ Z} Proposição 3.3. Seja S um subconjunto do grupo G, então o conjunto 〈S〉 é um subgrupo de G. Demonstração. Sejam x, y ∈ 〈S〉 temos: x = a1 · a2 · ... · an com ai ∈ S ou a−1 i ∈ S y = b1 · b2 · ... · bm com bi ∈ S ou b−1 i ∈ S Logo, x · y = a1 · a2 · ... · an · b1 · b2 · ... · bm e x−1 = a−1 n · a−1 n−1 · ... · a−1 2 · a−1 1 também estão em 〈S〉. De�nição 3.5. Se S é um subconjunto não vazio do grupo G, então 〈S〉 é chamado subgrupo gerado por S. Em particular, para todo elemento g do grupo G, o subgrupo gerado por g é 〈g〉 = {gt; t ∈ Z}. Subgrupos Normais e Grupos Quocientes 39 De�nição 3.6. Um grupo multiplicativo G é dito cíclico quando ele pode ser gerado por um de seus elementos, isto é, quando G = 〈g〉, para algum g ∈ G. Exemplo 3.7. Os grupos Z = 〈1〉 e Zn = 〈1〉 são exemplos de grupos cíclicos. De�nição 3.7. Seja G um grupo. O subgrupo 〈{xyx−1y−1|x, y ∈ G}〉 chama-se sub- grupo dos comutadores de G e é denotado por G‘. De�nição 3.8. Seja G um grupo. O subgrupo {x ∈ G;xg = gx,∀g ∈ G} chama-se centro de G, e é denotado por Z (G). De�nição 3.9. Seja G um grupo e x, y ∈ G. Diremos que x e y são conjugados em G, se existe g ∈ G tal que y = gxg−1. No Capítulo 4 veremos a utilidade destas duas operações XYX−1Y −1 e XYX−1 chamados de comutador e conjugados, respectivamente, para a resolução do cubo má- gico. De�nição 3.10. A ordem de um grupo G é o número de elementos em G. Ela será denotada por |G|. Se α é um elemento do grupo G, a ordem de α é a ordem do subgrupo gerado por α, e ela será denotada por O (α). Exemplo 3.8. |Z| =∞ e |Zn| = n. 3.6 Subgrupos Normais e Grupos Quocientes Seja G um grupo e seja H um subgrupo de G. Iremos agora observar se a operação de G induz de maneira natural uma operação sobre o conjunto das classes laterais à esquerda de H em G, isto é, se a operação (xH, yH) −→ xyH é bem de�nida, no sentido de não depender da escolha dos elementos x e y. Se tomarmos x, y ∈ G e h, k ∈ H arbitrários, então x e xh são representantes da mesma classe xH e, y e yk são representantes da mesma classe yH. Desta forma, a operação induzida sobre as classes laterais à esquerda é bem de�nida, se e somente se, xyH = xhykH, ∀x, y ∈ G, ∀h, k ∈ H 40 Álgebra no Cubo Mágico logo, y−1x−1xyH = y−1x−1xhyk, ou seja, H = y−1hyH, ∀y ∈ G, ∀h ∈ H, e portanto, yhy−1 ∈ H, ∀y ∈ G, ∀h ∈ H. Proposição 3.4. Seja H um subgrupo de um grupo G. As a�rmações a seguir são equivalentes: 1. A operação induzida sobre as classes laterais à esquerda de H em G é bem de�- nida. 2. gHg−1 ⊆ H, ∀g ∈ G. 3. gHg−1 = H, ∀g ∈ G. 4. gH = Hg, ∀g ∈ G. Demonstração. 1⇔ 2 já foi feito. 3⇔ 4 é óbvio. 3⇒ 2 é óbvio. 2 ⇒ 3 Suponhamos que gHg−1 ⊆ H, ∀g ∈ G; precisamos provar que H ⊆ gHg−1, ∀g ∈ G. Sejam então h ∈ H e g ∈ G; temos h = g(g−1hg)g−1 ∈ g(g−1Hg)g−1 ⊆ gHg−1. De�nição 3.11. Um subgrupo H é um subgrupo normal de G, denotado por H / G, se ele satisfaz qualquer uma das quatro a�rmações anteriores. Neste caso, as classes laterais à esquerda de H são iguais às classes laterais à direita de H; chamaremos simplesmente de classes laterais de H. Exemplo 3.9. {e} , G são subgrupos normais de G. Exemplo 3.10. G′ = 〈{xyx−1y−1|x, y ∈ G}〉 é um subgrupo normal de G. Demonstração. Primeiro, vamos observar que se chamamos de S o conjunto {xyx−1y−1 | x, y ∈ G} e se α ∈ S, então α−1 ∈ S; consequentemente, se ξ é um elemento qualquer Subgrupos Normais e Grupos Quocientes 41 de G ′ = 〈S〉, então ξ se escreve da forma ξ = α1 . . . αn com α1, . . . , αn ∈ S. Segundo, se g ∈ G, temos gξg−1 = g(α1 . . . αn)g −1 = (gα1g −1)(gα2g −1) . . . (gαng −1) e consequentemente, para ver que gξg−1 ∈ G′ , basta ver que gαg−1 ∈ S quando α ∈ S. Seja então α = xyx−1y−1 um elemento de S; temos gαg−1 = g(xyx−1y−1)g−1 = (gxg−1)(gyg−1)(gx−1g−1)(gy−1g−1) = (gxg−1)(gyg−1)(gxg−1)−1(gyg−1)−1 ∈ S. Teorema 3.2. Sejam G um grupo e H um subgrupo normal de G. Então o conjunto das classes laterais, com a operação induzida de G, é um grupo. Esta demonstração pode ser encontrada em [2]; O elemento neutro de G/H é a classe lateral H;o elemento inverso da classe gH é a classe g−1H. De�nição 3.12. Sejam G um grupo e H um subgrupo normal de G. O grupo de suas classes laterais com a operação induzida de G é o grupo quociente de G por H; ele será denotado por G/H ou por G H . Subgrupos gerados pela união de dois subgrupos Sejam H e K dois subgrupos de um grupo G. Temos 〈H ∪K〉 ⊇ HK := {hk | h ∈ H e k ∈ K} ⊇ H ∪K. Portanto é claro que 〈H ∪K〉 = HK ⇔ HK é um subgrupo de G Vejamos agora as condições para que HK seja um grupo. Proposição 3.5. Sejam H,K dois subgrupos de G. Então: HK é um subgrupo de G ⇔ HK = KH. Demonstração. (⇒) Seja α ∈ KH. Então existem k ∈ K e h ∈ H tais que α = kh. Te- mos α−1 = h−1k−1 ∈ HK. Como HK é por hipótese um subgrupo de G e α−1 ∈ HK, então α ∈ HK; assim provamos que KH ⊆ HK. Para provar a inclusão contrária, tome γ ∈ HK. Como HK é um subgrupo, temos γ−1 ∈ HK; logo γ−1 = h2k2 com h2 ∈ H, k2 ∈ K. Tomando inversos, obtemos γ = k−1 2 h−1 2 ∈ KH. Portanto temos HK = KH. 42 Álgebra no Cubo Mágico (⇐) Suponhamos que HK = KH. Para provarmos que HK é subgrupo basta provar- mos o seguinte: 1) xy ∈ HK, ∀x, y ∈ HK 2) x−1 ∈ HK, ∀x ∈ HK. Sejam x, y ∈ HK; se escrevermos x = h1k1 e y = h2k2 com h1, h2 ∈ H, k1, k2 ∈ K teremos xy = (h1k1)(h2k2) = h1(k1h2)k2. Como k1h2 ∈ KH e por hipótese KH = HK, existem h3 ∈ H e k3 ∈ K tais que k1h2 = h3k3; substituindo na expressão para xy, obteremos xy = h1(h3k3)k2 = (h1h3)(k3k2) ∈ HK Agora, teremos também x = h1k1 ⇒ x−1 = k−1 1 h−1 1 ∈ KH = HK Corolário 3.3. Sejam H e K dois subgrupos de G. Se H ou K for normal em G, então HK é um subgrupo de G. Demonstração. Faremos a prova no caso em que H / G e K é um subgrupo qualquer; o outro caso é totalmente análogo. Vamos mostrar que HK = KH. Seja α = hk ∈ HK. Temos α = hk = kk−1hk = kβ com β := k−1hk ∈ H pois H / G; portanto α = kβ ∈ KH. Provamos então que HK ⊆ KH. Para provar a inclusão contrária, seja γ = kh ∈ KH. Temos γ = kh = khk−1k = δk com δ := khk−1 ∈ H pois H / G; portanto γ = δk ∈ HK. 3.7 Homomor�smos de Grupos De�nição 3.13. Sejam (G, ·) e (G,×) dois grupos. Chamamos de homomor�smo uma função f : G→ G, que seja compatível com as estruturas de ambos os grupos, ou seja, se f(a · b) = f(a)× f(b), ∀a, b ∈ G. Exemplo 3.11. Sejam (R,+) e (R∗, ·) temos que f : R → R∗, onde f(x) = 2x é um homomor�smo. Para provarmos, basta tomarmos dois elementos x, y ∈ R. Assim temos que f(x) = 2x, f(y) = 2y e f(x + y) = 2x+y. Utilizando as propriedades de potência podemos escrever 2x+y = 2x · 2y. Finalmente temos que f(x + y) = 2x+y = 2x · 2y = f(x) · f(y). Homomor�smos de Grupos 43 Propriedades Elementares Seja f : (G, ·) → (G,×) um homomor�smo de grupos. Então são válidas as seguintes propriedades: 1. f(eG) = eG. Com efeito, eG · f(eG) = f(eG) = f(eG · eG) = f(eG)× f(eG)⇒ eG = f(eG) 2. f(x−1) = f(x)−1. Com efeito, eG = f(eG) = f(x · x−1) = f(x)× f(x−1). 3. Ker f := {x ∈ G|f(x) = eG} é um subgrupo normal de G chamado núcleo do homomor�smo f . Demonstração. Vejamos primeiramente que ker f < G. Dados x, y ∈ kerf , temos: f(x · y) = f(x)× f(y) = eG × eG = eG f(x−1) = f(x)−1 = e−1 G = eG portanto ker f < G. Para provar que ker f / G iremos mostrar que: gxg−1 ∈ ker f, ∀g ∈ G e ∀x ∈ ker f. E de fato, temos f(gxg−1) = f(g)× f(x)× f(g−1) = f(g)× eG × f(g)−1 = f(g)× f(g)−1 = eG. De�nição 3.14. Um homomor�smo f : G → G é chamado de isomor�smo se existe um homomor�smo g : G → G tal que f ◦ g = idG e g ◦ f = idG. Quando existe um isomor�smo entre dois grupos G e G dizemos que G e G são isomorfos e denotamos por G ' G. Temos a seguinte proposição: Proposição 3.6. Seja f : (G, ·) → (G,×) um homomor�smo de grupos. então, f é um isomor�smo se, e somente se, f for uma bijeção. Demonstração. (⇒) trivial (⇐) Precisamos mostrar que se f é um homomor�smo bijetivo, então f−1 é um homo- mor�smo, ou seja, f−1(α× β) = f−1(α) · f−1(β), ∀α, β ∈ G. Agora sejam α, β ∈ G, e também sejam a = f−1(α) e b = f−1(β) então temos que f−1 (α× β) = f−1 (f (a)× f (b)) = f−1 (f (a · b)) = a · b = f−1 (α) · f−1 (β) . 44 Álgebra no Cubo Mágico Com a noção de Grupos de Permutação que veremos a seguir é possível estabelecer isomor�smos entre Grupos Simétricos e Subgrupos de Rubik. E é desta forma que se dá a combinação destes dois conceitos para que sejam analisadas e criadas sequências de movimentos ou macros para resolver o Cubo Mágico. 3.8 Permutações Permutação é o termo usado para designar uma bijeção de um conjunto nele mesmo. Se E indica um conjunto não vazio, e S(E) o conjunto das permutações dos elementos de E, a composição de aplicações, é uma operação sobre S(E). De fato, se f e g são permutações de E, isto é, f : E → E e g : E → E são bijeções, então a composta g ◦ f : E → E também é uma bijeção. Pode-se provar que (S(E), ◦) é um grupo, chamado de grupos das permutações sobre E. Quando E = {1, 2, . . . , n}, n ≥ 1, usa-se a notação Sn para indicar o conjunto das permutações sobre E. O grupo (Sn, ◦) é chamado de grupo simétrico de grau n e tem ordem n!. De�nição 3.15. Uma permutação σ ∈ Sn é chamada de r-ciclo se existem elementos distintos a1, . . . , ar ∈ {1, . . . , n} tais que σ(a1) = a2, σ(a2) = a3, . . . , σ(ar−1) = ar, σ(ar) = a1, e tais que σ(aj) = aj,∀j ∈ {1, . . . , n} \ {a1, . . . , ar}. A notação para este r-ciclo será (a1 . . . ar). O número r signi�ca o comprimento do ciclo. Os 2-ciclos tam- bém são chamados de transposições. Há outras formas de representar um ciclo de elementos distintos a1, . . . , ar ∈ {1, . . . , n}: 1. Sucessivas transições de um elemento para outro até retornar ao elemento inicial. a1 → a2 → a3 → . . .→ ar−1 → ar → a1 e assim fecha o ciclo. 2. A forma matricial, onde cada coluna da matriz representa a transição de um elemento em outro: ( a1 a2 . . . ar−1 ar a2 a3 . . . ar a1 ) . Permutações 45 Em geral a notação ( 1 2 3 . . . a b c . . . ) representa a função de�nida por f(1) = a, f(2) = b, f(3) = c, e assim por diante. Vejamos alguns exemplos em S5: Exemplo 3.12. ( 1 2 3 4 5 2 3 4 5 1 ) é um 5-ciclo, denotado por (1 2 3 4 5). Outras possibilidades de notação seriam: (2 3 4 5 1), ou (3 4 5 1 2), ou (4 5 1 2 3), ou (5 1 2 3 4). Exemplo 3.13. ( 1 2 3 4 5 4 2 1 3 5 ) é um 3-ciclo, e pode ser denotado por (1 4 3), ou também por (4 3 1), ou ainda por (3 1 4). Note que as transições de 2 em 2 e 5 em 5, �cam omitidas na notação, já que seus elementos não são permutados, isto é, permanecem inalterados. Exemplo 3.14. ( 1 2 3 4 5 3 2 1 4 5 ) é uma transposição denotada por (1 3), ou então (3 1). Exemplo 3.15. ( 1 2 3 4 5 3 4 5 2 1 ) não é um r-ciclo, qualquer que seja r. Exemplo 3.16. O único 1-ciclo é a identidade, que denotamos por (1) ou por (α) com α ∈ {1, 2, 3, . . . , n}. Exemplo 3.17. ( 1 2 3 4 5 4 1 3 2 5 ) é um 3-ciclo, pois σ(1) = 4, σ(4) = 2 e σ(2) = 1, σ(3) = 3 e σ(5) = 5 . Em geral podemos pensar que efetuar uma permutação é a ação de reorganizar ou reordenar um conjunto de elementos ou objetos. No caso do cubo mágico este pensa- mento é aplicada aos cubinhos e também às suas cores. De acordo com a Figura 2.1, os cubinhos de quina possuem 3 cores e os cubinhos de aresta possuem 2 cores. Um fato importante, que decorre da teoria de grupos de permutação aplicada ao cubo de Rubik 46 Álgebra no Cubo Mágico que veremos mais adiante, é a impossibilidade de permutar, por exemplo, 2 cores de apenas um cubinho de aresta e manter todo o restante do cubo inalterado. De�nição 3.16. Seja σ ∈ Sn um r-ciclo e seja τ ∈ Sn um s-ciclo, diremos que as permutações σ e τ são disjuntas se nenhum elemento de {1, 2, . . . , n} é movido por ambas, isto é, ∀a ∈ {1, 2, . . . , n}, temos σ(a) = a ou τ(a) = a. Vejamos alguns exemplos em S5: Exemplo 3.18. Os ciclos (1 3 5) e (2 4) são disjuntos. Exemplo 3.19. Os ciclos (1 2 3) e (3 5) não são disjuntos, pois o elemento 3 é movido por ambas as permutações. 3.8.1 Produto de Ciclos Seja o conjunto {1, 2, 3, 4, 5} e σ, τ ∈ S5 duas permutações tais que σ = (1 2 4)(3 5) e τ = (1 3 5)(2 4). Queremos obter uma permutação ϕ = σ ◦ τ . Para isto basta seguirmos a transição de cada elemento do conjunto, de uma permutação para outra. Iniciamos em σ que leva o 1→ 2, mas em τ temos que 2→ 4. Portanto em ϕ temos o 1 → 4. Continuando em σ temos que 4 → 1, mas em τ temos que 1 → 3. Portanto em ϕ o 4 → 3. Seguindo em σ o 3 → 5, e em ϕ o 5 → 1. Portanto em ϕ temos que o 3 → 1. Com isso fechamos o ciclo. Note que em σ o 2 → 4 e em ϕ o 4 → 2, logo o 2 não se move. O mesmo ocorre com o 5, logo ele também não se move. Com isto chegamos ao resultado do produto ϕ = σ◦τ = (1 2 4)(3 5)◦(1 3 5)(2 4)⇒ ϕ = (1 4 3). Observação 3.6. Escrever o produto (1 2 4)(3 5)◦(1 3 5)(2 4) é o mesmo que escrever (1 2 4)(3 5)(1 3 5)(2 4). Proposição 3.7. Sejam σ, τ ∈ Sn dois ciclos disjuntos, então temos que στ = τσ. Demonstração. Sejam σ e τ ciclos de Sn disjuntos com relação aos conjuntos A e B, respectivamente. Se x é um elemento do conjunto In = {1, 2, . . . , n}, n ≥ 2, então há três hipóteses possíveis • x ∈ A. Então, σ ◦ τ(x) = σ(τ(x)) = σ(x), ao passo que (τ ◦ σ)(x) = τ(σ(x)) = σ(x). Portanto, σ ◦ τ e τ ◦ σ coincidem em A. Permutações 47 • x ∈ B (é análogo ao anterior). • x 6∈ A e x 6∈ B. Neste caso, (σ ◦ τ)(x) = σ(τ(x)) = σ(x) = x, ao passo que (τ ◦σ)(x) = τ(σ(x)) = σ(x) = x. Portanto, σ ◦ τ e τ ◦ σ também coincidem fora de A e B. Proposição 3.8. Seja a permutação σ ∈ Sn, σ 6= id, então podemos escrevê-la como um produto de ciclos disjuntos de comprimentos ≥ 2. Esta fatoração é única a menos da ordem dos fatores. Demonstração. Como α é id, existe i1 tal que α(i1) 6= i1. Considere a sequência i1, α(i1), α 2(i1), . . .; claramente, existe r1, 2 ≤ r1 ≤ n, tal que i1, α(i1), . . . , αr1−1(i1) são todos distintos e αr1(i1) ∈ {i1, α(i1), . . . , αr1−1(i1)}; é imediato veri�car que αr1(i1) = i1. Portanto a restrição de α ao conjunto {i1, α(i1), . . . , αr1−1(i1)} é tal que α |{i1,α(i1),...αr1−1(i1)}= (i1α(i1) . . . α r1−1(i1)). Denotaremos este r1-ciclo (i1α(i1) . . . α r1−1(i1)) por σ1. Se a restrição de α ao complementar de {i1, α(i1), . . . , αr1−1(i1)} é a identidade, aca- bou: α = σ1. Senão, tomamos um elemento i2 ∈ {1, 2, . . . , n}\{i1, α(i1), . . . , αr1−1(i1)} tal que α(i2) 6= i2; de maneira similar à etapa precedente, vai existir um inteiro r2 ≥ 2 tal que α |{i2,α(i2),...αr2−1(i2)}= (i2α(i2) . . . α r2−1(i2)). Denotaremos este r2-ciclo (i2α(i2) . . . α r2−1(i2)) por σ2. Observe que σ1 e σ2 são disjuntos. Se a restrição de α ao complementar do conjunto {i1, α(i1), . . . , αr1−1(i1), i2, α(i2), . . . α r2−1(i2)} é a identidade, acabou: α = σ1σ2 = σ2σ1. Senão, tomamos i3 ∈ {1, 2, . . . , n} \ {i1, α(i1), . . . , αr1−1(i1), i2, α(i2), . . . , α r2−1(i2)} tal que α(i3) 6= i3 e continuamos o processo. Claramente este processo vai ter que parar após um número �nito de etapas, e assim obteremos que α = σ1σ2 . . . σt, onde σ1, σ2, . . . , σt são ciclos disjuntos de comprimentos ≥ 2. Agora, para provar a unicidade, suponha que temos também α = τ1τ2 . . . τu com τ1, τ2, . . . , τu ciclos disjuntos, cada um deles de comprimento ≥ 2. Como τ1, . . . τu(i1) = α(i1) 6= i1 e como os τi's são ciclos disjuntos, existe um único τj tal que τj(i1) = α(i1). Como os τi's comutam entre si, podemos supor que j = 1 e então τ1(i1) = α(i1). Vamos mostrar que τ1 = σ1. O ciclo τ1 não pode deixar α(i1) �xo, isto é, τ1 não pode mandar α(i1) sobre α(i1), pois τ1 já manda i1 sobre α(i1); como os τi's são ciclos disjuntos, então, ∀j ≥ 2, τj deixa α(i1) �xo e portanto α(α(i1)) = τ1(α(i1)); assim τ1(α(i1)) = α2(i1). De maneira similar obtemos que τ1(α k−1(i1) = αk(i1),∀k ≥ 0, e portanto que τ1 = σ1. Similarmente, trabalhando com i2 no lugar de i1, iremos obter que τ2 = σ2; continuando assim, obteremos que u = t e que a menos da ordem σj = τj, para cada j = 1, . . . , t. 48 Álgebra no Cubo Mágico A unicidade do produto de ciclos disjuntos é de grande auxílio ao se realizar ope- rações no grupo Sn. Exemplo 3.20. A permutação ( 1 2 3 4 5 6 7 3 5 1 6 2 7 4 ) pode ser escrita como o pro- duto (1 3)(2 5)(4 6 7), ou seja, dois 2-ciclo e um 3-ciclo. Exemplo 3.21. A permutação de S8 σ = ( 1 2 3 4 5 6 7 8 1 6 8 3 7 5 2 4 ) pode ser escrita em ciclos disjuntos da seguinte maneira: Como σ(1) = 1, vamos começar o processo descrito na demonstração com o elemento 2: 2, σ(2) = 6, σ2(2) = σ(σ(2)) = σ(6) = 5, σ(5) = 7, σ(7) = 2. Portanto σ1 = (2 6 5 7). Repetindo-se o processo a partir do 3 obteremos: 3, σ(3) = 8, σ(8) = 4, σ(4) = 3. Então σ2 = (3 8 4). Portanto: σ = (2 6 5 7) ◦ (3 8 4). Proposição 3.9. Todo elemento de Sn é um produto de transposições, isto é, Sn = 〈{transposições}〉. Demonstração. Temos id = (1 2)(1 2) ∈ 〈{transposição}〉. Utilizando a proposição 3.8, basta mostrarmos que todo ciclo (a1 . . . ar) é um produto de transposições, e de fato, temos (a1 a2 . . . ar) = (a1 ar)(a1 ar−1) . . . (a1 a3)(a1 a2). Permutações 49 Exemplo 3.22. Vejamos como decompor, em transposições, a seguinte permutação em S8: σ = ( 1 2 3 4 5 6 7 8 1 6 8 3 7 5 2 4 ) . Como visto no exemplo 3.21: σ = (2 6 5 7) ◦ (3 8 4). Mas devido à identidade exibida na proposição: σ = (2 6 5 7) = (2 7) ◦ (2 5) ◦ (2 6) e (3 8 4) = (3 4) ◦ (3 8). Portanto σ = (2 7) ◦ (2 5) ◦ (2 6) ◦ (3 4) ◦ (3 8). Observação 3.7. A decomposição de um elemento α ∈ Sn como produto de trans- posições não é única, mesmo ao se estabelecer um número mínimo de transposições, como é o que acontence em (1 2 3) = (1 3)(1 2) = (2 3)(1 3). Entretanto, mais a frente veremos que a paridade do número de transposições é bem de�nida. 3.8.2 Repetição de ciclos e ordem Vejamos agora como se comporta a repetição de um ciclo, isto é, aplicar o produto de um n-ciclo a ele mesmo sucessivas vezes. Por exemplo, vamos considerar o 3-ciclo σ = (1 2 3), e veri�car o comportamento de σ1, σ2 e σ3. 1. σ1 = (1 2 3) = id 2. σ2 = (1 2 3)(1 2 3) = (1 3 2) 3. σ3 = (1 2 3)(1 2 3)(1 2 3) = (1 2 3) = id É possível notar que ao aplicar o 3�ciclo a ele mesmo 3 vezes, o resultado é ele próprio, isto é, a identidade. De�nição 3.17. Seja σ ∈ Sn um r-ciclo. O número mínimo de aplicações, a ele mesmo, necessário para que o ciclo retorne à sua posição original, isto é, a identidade (id) será chamado de ordem de σ (O(σ)), que é igual a r. Proposição 3.10. Se σ = (a1 a2 ar) ∈ Sn é um ciclo de comprimento r > 1, então O(σ) = r e, portanto, se ε indicar a permutação idêntica de Sn, [σ] = {ε, σ, σ2, . . . , σr−1}. 50 Álgebra no Cubo Mágico Demonstração. Da de�nição de ciclo decorre diretamente que σi−1(a1) = a1, (i = 1, 2, . . . , r) e σr(a1) = a1. então σi 6= ε sempre que 1 ≤ i < r, e, portanto, r ≤ O(σ). Por outro lado, se i é um índice tal que 1 ≤ i ≤ r, então σr(ai) = σr(σi−1(a1)) = σi−1(σr(a1)) = σi−1(a1) = ai. Considerando-se que σ(x) = x sempre que x 6= ai, (i = 1, 2, . . . , r), então σr = ε e, por conseguinte, O(σ) ≤ r. De onde, O(σ) = r. Proposição 3.11. Sejam σ1, . . . , σt ∈ Sn ciclos disjuntos de comprimentos r1, . . . , rt respectivamente. A ordem do produto σt . . . σ1 tem ordem igual ao m.m.c.(r1, . . . , rt), onde m.m.c. é a abreviação de mínimo múltiplo comum. Maiores detalhes podem ser encontrados em [2]. Exemplo 3.23. Seja σ = (1 2)(3 4 5) o produto disjunto entre um 2-ciclo e um 3- ciclo. Como a ordem de (1 2) é igual a 2 e a ordem de (3 4 5) é igual a 3, segue que O(σ) = m.m.c.(2, 3)⇒ O(σ) = 6. No caso do cubo mágico, temos o seguinte exemplo: Seja a macro S = F 4. Ao aplicarmos 4 vezes o movimento F retornamos à identidade, conforme a Figura 3.5. Figura 3.5: Macro F 4. Portanto a ordem de S é igual 4, isto é, O(S) = 4. Todos os 8 movimentos (UU ′ DD ′ RR ′ LL ′ FF ′ BB ′ ) das faces tanto no sentido horário quanto no sentido anti- horário são de ordem 4. Já as macros T = URU ′ R ′ e V = RU , possuem ordens O(T ) = 6 e O(V ) = 105, respectivamente. Utilizando o cubo mágico é fácil veri�car a ordem de uma macro. Por exemplo, a partir da posição inicial do cubo, isto é, com ele resolvido, basta repetir sucessivas vezes a mesma macro e contar o número de repetições até que se retorne, pela primeira vez, à posição inicial. Mais adiante no Capítulo 4 veremos que é possível calcular tais ordens. 3.9 Assinatura de uma Permutação Conforme visto na seção anterior, é possível realizarmos a decomposição de um ciclo em um produto de transposições, porém ela não é única. De fato, como (a b) ◦ (b a) é a aplicação idêntica de In, que é o elemento neutro de Sn, então num produto de Assinatura de uma Permutação 51 transposições podemos inserir tantas expressões deste tipo quanto desejarmos, o que não afetará o resultado. Por exemplo, em S7: (2 6 5 7) = (2 7) ◦ (2 5) ◦ (2 6) = (1 2) ◦ (2 1) ◦ (2 7) ◦ (2 5) ◦ (2 6) Entretanto é possível demonstrarmos que todas as decomposições de um mesmo ci- clo, em transposições, têm em comum a paridade. Isto é, se em uma delas o número de transposições é par (ímpar), então o mesmo acontecerá em todas as outras. Con- tudo, para provarmos este resultado, é necessário que antes introduzamos o conceito de assinatura de uma permutação. De�nição 3.18. A assinatura de uma permutação σ = ( a1 a2 . . . an b1 b2 . . . bn ) é o nú- mero real, aqui denotado por sgn(σ), e de�nido por: sgn(σ) = ∏ ai − aj bi − bj em que o produto é estendido a todos os pares (i, j) de índices tais que i > j. Da de�nição, decorre diretamente que a assinatura da permutação idêntica é igual a 1. Devemos observar que o produto que de�ne sgn(σ) independe da ordem das colunas na expressão de σ e que cada quociente ai − aj bi − bj é uma função do par (i, j). Exemplo 3.24. A assinatura da permutação σ = ( 1 2 3 2 3 1 ) é: sgn(σ) = 2− 1 3− 2 · 3− 1 1− 2 · 3− 2 1− 3 = (1)(−2)(−1/2) = 1. Proposição 3.12. A assinatura de uma transposição é -1. Demonstração. Seja τ ∈ Sn uma transposição. Podemos representá-la da seguinte maneira: τ = ( a1 a2 a3 . . . an a− 2 a1 a3 . . . bn ) . Se (r, s) é um par de índices da primeira linha da transposição τ e 1 6 r < s 6 n, então podemos ter as seguintes situações possíveis: (a) (r, s) = (1, 2) cujo fator correspondente em sgn(τ) é a2 − a1 a1 − a2 = −1. (b) r = 1 e s > 2, caso em que o fator correspondente de (r, s) em sgn(τ) é as − a1 as − a2 . 52 Álgebra no Cubo Mágico (c) r = 2 e s > 2, caso em que o fator correspondente de (r, s) em sgn(τ) é as − a2 as − a1 . (d) r > 2 e neste caso, o fator correspondente de (r, s) em sgn(τ) é as − ar as − ar = 1. Como os fatores de (b) e (c) aparecem em pares cujo produto é 1, então: sgn(τ) = a2 − a1 a1 − a2 = −1 Proposição 3.13. Para quaisquer permutações σ, ϕ ∈ Sn, sgn(ϕ◦σ) = (sgn(ϕ))(sgn(σ)). Demonstração. Permutando convenientemente as colunas de ϕ, podemos escrever: σ = ( a1 a2 . . . an b1 b2 . . . bn ) e τ = ( b1 b2 . . . bn c1 c2 . . . cn ) Portanto: (sgn(ϕ))(sgn(σ)) = (sgn(σ))(sgn(ϕ)) = ∏ ai − aj bi − bj ∏ bi − bj ci − cj = ∏ ai − aj ci − cj = sgn(ϕ◦σ) Corolário 3.4. Se σ ∈ Sn, então sgn(σ) = ±1. Demonstração. Como toda permutação pode ser escrita como um produto de transpo- sições, então: σ = τ1 ◦ τ2 ◦ . . . τr. para convenientes transposições τ1, τ2, . . . τr ∈ Sn. Então, se usarmos a generalização da proposicão anterior para r fatores e sabendo que a assinatura de uma transposição é igual a -1: sgn(σ) = sgn(τ1 ◦ τ2 ◦ . . . τr) = (sgn(τ1))(sgn(τ2)) . . . (sgn(τr)) = = (−1)(−1) . . . (−1) = (−1)r = ±1. 3.9.1 Paridade de Ciclos De�nição 3.19. Seja σ ∈ Sn. Diremos que σ é uma permutação par quando σ se escreve como um produto de um número par de transposições. E diremos que σ é uma permutação ímpar quando σ se escreve como um produto de um número ímpar de transposições. Exemplo 3.25. Seja a permutação σ = (1 2 4)(3 5) = (1 2)(1 4)(3 5), portanto σ é ímpar. Seja a permutação τ = (1 4 3) = (1 4)(1 3), portanto τ é par. O elemento neutro (1) ∈ Sn é par, pois (1) = (1 2)(1 2). Assinatura de uma Permutação 53 Podemos ainda de�nir: De�nição 3.20. Seja um elemento σ ∈ Sn escrito como o seguinte produto:∏ 16i 0. Então o ciclo (1 3 2) é par. Proposição 3.14. Seja σ ∈ Sn uma dada permutação e consideremos duas composi- ções de σ em transposições: σ = τ1 ∗ τ2 ∗ ... ∗ τr e σ = ρ1 ∗ ρ2 ∗ ... ∗ ρs então os inteiros r e s têm a mesma paridade. Demonstração. Devido ao corolário 3.4, sgn(σ) = (−1)r = (−1)s. Se r for par, então (−1)r = 1; daí (−1)s = 1 e, portanto, s também é par. O raciocínio é análogo no caso em que r é ímpar. Proposição 3.15. Seja An = {α ∈ Sn|α é uma permutação par} . Então An é um subgrupo das permutações pares de Sn e é chamado de grupo alternado. Observação 3.8. Note que a outra metade das permutações ímpares não é um sub- grupo já que não contém o elemento neutro (1). Veremos no próximo capítulo como o conceito de paridade nos auxilia não só na análise do cubo mágico, bem como na sua resolução. É também através deste conceito que se justi�ca a impossibilidade de se obter certas permutações entre os cubinhos como, por exemplo, permutar as 2 cores de um cubinho de aresta sem alterar todos os outros. 4 Aplicações da Teoria de Grupos e Grupos de Permutação no Cubo Mágico Neste capítulo utilizaremos os conceitos abordados no capítulo anterior com o obje- tivo de calcular o número de con�gurações possíveis que o cubo mágico pode assumir, além de compreender o funcionamento das macros em especial os comutadores e con- jugados. Com isto provaremos a impossibilidade de permutar posições e orientações especí�cas dos cubinhos e de suas cores. Mas acima de tudo é através deste capítulo que mostraremos que a justi�cativa da possibilidade da resolução do cubo mágico é ma- temática e não empírica. As principais referências utilizadas para o desenvolvimento deste capítulo foram [3], [4], [5] e [6]. 4.1 Calculando a ordem de uma macro Seja a macro S = URU ′ R ′ . No exemplo 3.23 vimos que O(S) = 6. De fato, para chegarmos neste valor precisamos primeiro observar, utilizando o pró- prio cubo mágico, quais cubinhos são afetados por esta macro. A �gura 4.1 mostra quais deles são permutados. Ao realizar esta macro uma ou mais vezes percebemos que todos os cubinhos que se movem ocupam apenas algumas posições, isto é, durante a permutação eles não são todos permutados entre si. Na verdade percebemos que estas permutações ocorrem em grupos formando um ciclo, onde somente os cubinhos pertencentes a um mesmo ciclo permutam entre si. Com efeito, notamos que os cubinho UB, UR e FR permutam entre si, da mesma forma que os cubinhos LUB e RUB permu- tam entre si e �nalmente os cubinhos RUF e RDF permutam entre si. Logo pode- mos escrever, em notação de ciclo, a macro S que provoca as seguintes permutações: S = (UB UR FR)(LUB RUB)(RUF RDF ), isto é, composta de 1 3-ciclo e 2 2-ciclo. 55 56 Aplicações da Teoria de Grupos e Grupos de Permutação no Cubo Mágico Figura 4.1: Cubinhos afetados pela macro S. Podemos ainda fazer uma associação com números da seguinte forma: UB UR FR LUB RUB RUF RDF ↓ ↓ ↓ ↓ ↓ ↓ ↓ 2 4 6 1 3 5 7 Portanto podemos escrever a permutação S da seguinte maneira: S = (2 4 6)(1 3)(5 7) Os comprimentos dos ciclos (UB UR FR), (LUB RUB) e (RUF RDF ), são res- pectivamente 3, 2, 2. Logo a ordem de S é dada pelo mínimo múltiplo comum (m.m.c.) entre 3,2,2. Portanto O(S) = m.m.c.(3, 2, 2) = 6. Concluímos também que a permu- tação gerada por S é par, a�nal S pode ser escrita como um produto de um número par de transposições, por exemplo: S = (2 4)(2 6)(1 3)(5 7). 4.2 Paridade dos movimentos das faces Vimos no capítulo 2 que uma macro nada mais é do que uma sequência de dois ou mais movimentos de qualquer uma das 6 faces do cubo, tanto no sentido horário quanto no sentido anti-horário, logo podemos associá-la com um produto de ciclos. Se analisarmos a paridade de apenas um movimento de uma face, por exemplo, o mo- vimento F (girar em 90◦ a face da frente no sentido horário), podemos estender esta paridade a qualquer macro. Ao efetuarmos o movimento F os cubinhos afetados são: FU, FUR, FR, FDR,FD,FDL,FL, FUL. A �gura 4.2 ilustra este movimento. Em notação de ciclos temos: F = (FU FR FD FL)(FUL FUR FDR FDL) ou ainda associando números F = (1 3 5 7)(2 4 6 8). Se escrevermos F como produto de ciclos disjuntos teremos: F = (1 3)(1 5)(1 7)(2 4)(2 6)(2 8). Paridade dos movimentos das faces 57 Figura 4.2: Cubinhos afetados pelo movimento F Portanto o movimento F tem paridade par. Sem perda de generalidade o mesmo ocorre para o movimento das outras 5 faces. Como uma macro é composta de dois ou mais movimentos é, portanto deste fato que decorre a impossibilidade de, com um ou mais movimentos, permutarmos apenas um par de cubinhos sem alterar todo o resto do cubo. Para isto o movimento da face necessitaria ter paridade ímpar. De maneira análoga não existe uma sequência que permute apenas 2 cores de um cubinho de aresta sem alterar todo o resto. Esta impossibilidade é outro motivo que torna a resolução do cubo bastante desa�adora. É deste fato também que ao permutarmos as 3 cores de um cubinho de canto em um sentido, invariavelmente será permutado no sentido contrário as 3 cores de um cubinho de canto adjacente, se quisermos que mais nenhum outro cubinho saia de sua posição. Mais a frente veremos como isto é possível. Seja a macro S = F 2R2. Ela move 13 cubinhos, portanto temos os seguintes ciclos: S = (UF DF )(DR UR)(FL FR BR)(UFL DFR UBR)(DFL UFR DBR) A macro S possui paridade par e ordem O(S) = 6. Se aplicarmos S por três vezes, isto é, S3, veremos que os cubinhos do 3-ciclo voltaram ao seu lugar e os cubinhos dos 2-ciclos permaneceram permutados. A�nal a ordem dos 3-ciclos é 3 e, portanto ao aplicarmos a macro 3 vezes eles retornaram às suas posições originais, enquanto que o 2-ciclo, que tem paridade par, foi executado um número ímpar de vezes não retor- nando ao seu estado inicial. Mais a frente veremos macros que permutam ciclicamente 3 cubinhos de mesmo tipo, deixando todo o resto do cubo inalterado. Tais macros evi- dentemente são permutações pares. É através dos conceitos de paridade e ordem que os métodos que resolvem o cubo em poucos movimentos são embasados, pois organizam os movimentos pelas suas ordens. 58 Aplicações da Teoria de Grupos e Grupos de Permutação no Cubo Mágico 4.3 Calculando o número de posições do cubo mágico Para contarmos o número (N) de posições, de acordo com [5], que o cubo mágico pode assumir, precisamos recordar que há 12 cubinhos de arestas, cada um contendo 2 cores diferentes e 8 cubinhos de canto, cada um contendo 3 cores diferentes. Portanto, teoricamente deveríamos ter para os cubinhos de aresta 12! ·212 possibilidades e para os cubinhos de canto 8! ·38 possibilidades, gerando um total de 12! ·212 ·8! ·38. Entretanto, vimos anteriormente que há algumas impossibilidades de posições devido à paridade do cubo. Não existe a possibilidade de alterarmos apenas um cubinho de aresta, logo somente 11 dos 12 cubinhos é que podem sofrer permutação, em nossa contagem. O mesmo ocorre com os cubinhos de canto, isto é, não podemos alterar apenas um cubinho de canto, logo somente 7 dos 8 cubinhos de canto é que sofrem permutação. Devido à paridade vimos também que metade delas são pares e ímpares, onde estas últimas não podem ser alcançadas devido à paridade dos movimentos das faces serem pares. Logo, teremos o seguinte cálculo: N = (12! · 211) · (8! · 37) 2 = 43 252 003 274 489 856 000 ∼= 4, 0× 1019 possibilidades. Diante de um número de tão grandes proporções, podemos concluir que é pra- ticamente impossível alguém, movendo o cubo aleatoriamente, resolvê-lo em algum momento sem utilizar qualquer método mais estratégico. A�nal somente 1 destas po- sições é a que o cubo se encontra montado, isto é, aquela em que apresenta todas as suas faces com suas respectivas cores. 4.4 Comutadores e conjugados Na seção 3.5.1 vimos a existência de subgrupos chamados de comutadores, cuja forma é XYX−1Y −1 e conjugados, cuja forma é GHG−1. Podemos ainda denotar um comutador da seguinte forma [X, Y ] = XYX−1Y −1, e um conjugado da seguinte forma ĤG = GHG−1. Através deles podemos pensar em sequências que permutem, por exemplo, apenas alguns cubinhos que se queira, sem alterar todo o resto do cubo. Para isso associamos X e Y , no caso dos comutadores, aos movimentos das faces, sejam eles simples ou sequências de movimento. Ao aplicarmos, tanto os comutadores quanto os conjugados, em um cubo mágico notamos que o efeito provocado é o que se pode dizer de �destruir e reconstruir�. E ainda com uma familiaridade maior com o cubo, tais movimentos tornam-se intuitivos no sentido de se compreender o que está acontecendo durante a execução. É nítido, por exemplo, observar um determinado cubinho saindo de sua Comutadores e conjugados 59 posição, indo para outra que se queira, e dando lugar a outro cubinho que também se queria posicionar no lugar do primeiro, enquanto que os restantes dos cubinhos, que não se queria alterar, mudam de lugar durante a execução, porém ao �nal retornam a suas posições em que estavam inicialmente. Vejamos agora alguns exemplos de comutadores e conjugados: Exemplo 4.1. Permutar 2 cubinhos de aresta que estão na face frontal. Sejam as macros S = UFU ′ F ′ e T = U ′ F ′ UF . A ação gerada por S leva o cubinho FU em FL e a ação gerada por T leva o cubinhos FU em FR. Ao �nal a orientação da cor do cubinho foi preservada. A �gura 4.3 mostra o efeito das macros S e T : Figura 4.3: Efeito gerado pelas macros S e T . Analisando temos: S = UFU ′ F ′ onde { X = U Y = F X−1 = U ′ Y −1 = F ′ T = U ′ F ′ UF onde { X = U ′ Y = F ′ X−1 = U Y −1 = F Note que ao aplicar S, o primeiro movimento é U , isto é, girar a face superior em 90◦ no sentido horário. Isto faz com que o cubinho em FU seja levado para a face da esquerda, terminando em FL. De modo análogo, ao aplicar T , o primeiro movimento é U ′ , isto é, girar a face superior em 90◦ no sentido anti-horário. Isto faz com o cubinho em FU seja levado para a face da direita, terminando em FR. Ambas as macros afetam outros cubinhos além daqueles que se desejam alterar. No caso da macro S, os cubinhos afetados formam os seguintes ciclos: S = (FL FU UR)(FLD FLU)(LUF LUB) Onde o que nos interessa é o 3-ciclo. Note que se aplicarmos S3, os cubinhos deste ciclo retornam às suas posições originais, deixando os demais permutados, a�nal O(S) = 6. 60 Aplicações da Teoria de Grupos e Grupos de Permutação no Cubo Mágico Se chamarmos de M = UF e N = U ′ F ′ , temos que S =MN e T = NM . Tal fato, em particular, faz com que as macros S e T produzam um efeito simétrico em relação à face frontal. Exemplo 4.2. Permutar 3 cubinhos de canto que estão na face superior, alterando suas orientações. Sejam as macros S = R ′ (ULU ′ )R(UL ′ U ′ ) e S−1 = (ULU ′ )R ′ (UL ′ U ′ )R. A ação gerada por ambas permutam os cubinhos UFL, UFR e UBR no sentido anti-horário e no sentido horário, respectivamente. Ao �nal além das posições as cores destes cubinhos também são reorientadas. A �gura 4.4 mostra o efeito das macros S e S−1: Figura 4.4: Permutação de 3 cubinhos de canto com alteração de suas orientações. Diferentemente do exemplo anterior, em que os elementos são movimentos simples das faces, neste caso um dos elementos do comutador é uma sequência de movimentos. Analisando temos: S = R ′ (ULU ′ )R(UL ′ U ′ ) onde { X = R ′ Y = ULU ′ X−1 = R Y −1 = UL ′ U ′ S−1 = (ULU ′ )R ′ (UL ′ U ′ )R onde { X = ULU ′ Y = R ′ X−1 = UL ′ U ′ Y −1 = R As macros ULU ′ e UL ′ U ′ são inversas, pois se realizarmos uma em ordem inversa, invertendo individualmente cada movimento, temos a outra. Por este fato, em S, o que é X = R ′ e Y = ULU ′ , em S−1 é o inverso, isto é, X = ULU ′ e Y = R ′ . E ainda se realizarmos uma macro em ordem inversa, invertendo individualmente cada movimento temos outra. Portanto, temos que o efeito provocado por ambas as macros permutam os mesmos cubinhos, porém em sentido contrário. Note que apenas os cubinhos do 3-ciclo, isto é, (UFL UFR UBR) é que foram per- mutados deixando todo o resto do cubo intacto, embora tenha sido permutado além Comutadores e conjugados 61 de suas posições, também suas cores. Exemplo 4.3. Permutar 3 cubinhos de canto que estão na face superior, sem alterar suas orientações. Sejam as macrosG = LD eG−1 = D ′ L ′ e os comutadoresH = (R ′ D ′ R)U(R ′ DR)U ′ e H−1 = U(R ′ D ′ R)U ′ (R ′ DR). Agora vamos compor os seguintes conjugados: W = ĤG = GHG−1 e W−1 = H−1̂G = GH−1G−1. Em notação do cubo mágico teremos: W = GHG−1 = LD[(R ′ D ′ R)U(R ′ DR)U ′ ]D ′ L ′ W−1 = GH−1G−1 = LD[U(R ′ D ′ R)U ′ (R ′ DR)]D ′ L ′ A ação gerada por ambas permutam os cubinhos UFL, UFR e UBR no sentido anti-horário e no sentido horário, respectivamente, sem alterar suas orientações. A �gura 4.5 mostra o efeito das macros W e W−1: Figura 4.5: Permutação de 3 cubinhos de canto sem alteração de suas orientações. Ao contrário do exemplo anterior esta macro conservou as orientações, já que no exemplo da �gura os 3 cubinhos permutados permaneceram com suas faces azuis vol- tadas para cima. Por este exemplo, �ca evidente que é impossível permutar apenas 2 cantos, conser- vando suas orientações, sem alterar o restante do cubo, a�nal a paridade de um 3-ciclo é par. Até agora vimos exemplos de permutações entre cubinhos, em que pode ocorrer ou não a reorientação das cores. Entretanto podemos realizar macros que gerem, ao �nal da execução, somente a permutação das cores dos cubinhos sem movê-los de lugar. Sabemos da seção 4.2 que é impossível permutar apenas as cores de um cubinho de aresta sem alterar todo o restante do cubo. Porém é possível permutar as 3 cores de dois cubinhos de canto adjacentes, a�nal são 2 3-ciclo, cuja paridade é par. É o que 62 Aplicações da Teoria de Grupos e Grupos de Permutação no Cubo Mágico veremos no próximo exemplo. Exemplo 4.4. Permutar as 3 cores de 2 cubinhos de canto da face frontal. Sejam as macros M = LD2L ′ F ′ D2FeN = U . Vamos compor os seguintes comuta- dores S =MNM−1N−1 e S−1 = NMN−1M−1, cujas formas são XYX−1Y −1: S = (LD2L ′ F ′ D2F )U(F ′ D2FLD2L ′ )U ′ S−1 = U(LD2L ′ F ′ D2F )U ′ (F ′ D2FLD2L ′ ) A ação gerada por ambas as macros permutam as cores dos cubinhos UFL e UFR. A permutação ocorre em sentidos contrários simultaneamente, isto é, enquanto para um cubinho as cores são permutadas no sentido horário, as cores do outro cubinho são permutadas no sentido anti-horário e vice-versa. A �gura 4.6 mostra o efeito das macros S e S−1. Figura 4.6: Rotação dos cubinhos de canto. Como neste exemplo, ao invés das posições, as cores é que são permutadas, podería- mos associar para cada cor de cada cubinho um número e escrever os seguintes 3-ciclo: (1 2 3) e (4 5 6), respectivamente para os cubinhos UFL e UFR. 5 Resolvendo o Cubo Mágico Este capítulo é dedicado às diversas abordagens de se resolver o Cubo Mágico de Rubik. Para efeito de organização, vamos classi�car tais abordagens em três catego- rias que se distinguem quanto à otimização: uma com relação ao menor número de movimentos, outra com relação ao menor tempo de resolução e outra com relação à menor memorização de algoritmos. O método que mostraremos ao �nal deste capítulo privilegia esta última. A razão da escolha feita se justi�ca por dois motivos, pois ela utiliza os resultados obtidos pela combinação das duas teorias abordadas nesta dis- sertação, a Teoria de Grupos e a Teoria dos Grupos de Permutação e também por ser relativamente simples para quem já possui familiaridade com o cubo mágico. As poucas macros que são adotadas neste método utilizam comutadores e conjugados, os mesmos apresentados no Capítulo 4. Já no Capítulo 6, o método que será apresentado privilegia resolver o cubo no menor tempo possível, entretanto é necessária a memori- zação de um número maior de macros. Ao detalhar as 3 categorias veremos que é muito difícil conciliar os 3 quesitos em um único método, isto é, elaborar um método que resolva o cubo mágico com o menor número de movimentos, no menor tempo e utilizando poucas macros memorizadas. Na verdade, o que se observa é: quanto mais um quesito é privilegiado, menos os outros dois são. Para os a�cionados pelo Cubo Mágico são realizadas competições nacionais e mun- diais1. Existem várias modalidades que vão desde resolver o cubo com os pés ou com os olhos vendados até outras que utilizam con�gurações diferentes do cubo ou até mesmo outros formatos que não são cúbicos. Entre elas podemos destacar duas: resolução no menor tempo e resolução no menor número de movimentos. A título de curiosidade atualmente (05/2016) os recordes mundiais são: • Modalidade resolução no menor tempo: Lucas Etter (Estadunidense) � Campeonato realizado em Clarksville, Maryland, USA em 21 de novembro de 2015. Melhor resultado: 4,90 segundos. 1WCA � World Cube Association www.worldcubeassociation.org 63 64 Resolvendo o Cubo Mágico • Modalidade resolução no menor número de movimentos: Marcel Peters (Alemão) � Campeonato realizado em Colônia, Alemanha em 9/10 de janeiro de 2016. Melhor resultado: 19 movimentos. Para o desenvolvimento deste capítulo as principais referências foram [6] e [7]. 5.1 Resolvendo o Cubo Mágico com o menor número de movimentos Entre as 3 categorias, esta sem dúvidas é a mais complexa de todas e exige um conhecimento sobre o Cubo Mágico bastante aprofundado, assim como toda álgebra envolvida nele. Veremos que, para este método, há dois tipos de algoritmos: um rea- lizado por computadores e outro realizável por humanos que seria uma adaptação do método efetuado por computadores, já que este é extremamente complexo e impossível de ser memorizado. 5.1.1 Método realizado por computador É conhecido como Algoritmo de Deus (God's Algorithm) o algoritmo que resolve o Cubo Mágico com o menor número de movimentos possível. Demonstra�se que qual- quer que seja a posição que o cubo está embaralhado, por pior que esteja, é possível resolvê�lo em um determinado número de movimentos ou menos. A este número é dado o nome de Número de Deus (God's Number), e atualmente seu valor é 20. Em geral este tipo de algoritmo só é possível de ser executado por um computador, pois sua memorização é extremamente complexa. Conforme vimos no Capítulo 2, ele foi construído por Ernö Rubik em 1974. Sete anos depois, em julho de 1981, o inglês Morwen Thistlethwaite, então professor no Poly- technic of the South Bank, em Londres, foi o primeiro a elaborar um algoritmo capaz de resolver o cubo mágico em poucos movimentos, na verdade em não mais que 52 mo- vimentos. Depois deste, outros métodos foram elaborados até chegarmos no número 20. A maioria dos algoritmos conhecidos para resolver o cubo mágico seguem basica- mente dois padrões: • Resolver por camadas, uma a uma, primeiro a camada de baixo, depois a do meio e então a camada de cima; Resolvendo o Cubo Mágico com o menor número de movimentos 65 • Ou então resolver primeiro todos os cubinhos de aresta para então resolver os cubinhos de canto. Um dos motivos que torna o algoritmo de Thistlethwaite impressionante é o fato de ele não seguir nenhum destes dois padrões. Seu método consiste em resolver todos os cubinhos simultaneamente até que haja somente um movimento possível, que é jus- tamente aquele que retorna o cubo à sua posição original, isto é, com todas as cores orientadas. Não faremos a demonstração deste método, entretanto vamos detalhar o princípio do algoritmo de Thistlethwaite. A primeira ideia em que este método se baseia é nas inúmeras simetrias que o cubo de Rubik pode assumir. Ao manusear o cubo �ca claro que podemos ter situações semelhantes que se diferem apenas pelas cores, por exemplo, com a face branca para cima, ter os cubinhos de arestas todos rotacionados apenas uma única vez, é o mesmo que ter esta mesma situação, porém com a face azul para cima. Neste caso, a sequên- cia de movimentos que resolve uma situação é idêntica à sequência de movimentos que resolve a outra. Portanto, Thistlethwaite separou todas as simetrias em subgrupos. Para aplicar este método com o intuito de resolver o cubo mágico que se encontre em- baralhado, tais simetrias somente poderiam ser observadas e identi�cadas a qual grupo pertencem, utilizando�se um computador, já que memorizá�las seria algo impossível. O método consiste de quatro estágios, cada qual possui um determinado grupo de si- metrias. A cada grupo é somente permitida uma classe de movimentos de modo que com eles se atinja o próximo estágio. E assim, uma vez identi�cado em qual subgrupo o cubo mágico encontra�se, a ele é aplicado os movimentos necessários com o objetivo de passar de um estágio para o outro, até atingir o último estágio e retornar o cubo à identidade. Vejamos como são estes grupos: Sejam os grupos • G0 = 〈L,R, F,B, U,D〉, • G1 = 〈L,R, F,B, U2, D2〉, • G2 = 〈L,R, F 2, B2, U2, D2〉 e • G3 = 〈L2, R2, F 2, B2, U2, D2〉. O objetivo é seguir a cadeia G = G0 → G1 → G2 → G3 → I. Esta sequência de Gi até Gi+1 é feita utilizando apenas movimentos em Gi que é o subgrupo onde o cubo se encontra. Em cada estágio a restrição de movimentos tem como consequência �xar determinadas condições dos cubinhos, como por exemplo, orientar todos os cubinhos 66 Resolvendo o Cubo Mágico de arestas apenas. Devido a este fato e às simetrias, podemos organizar em uma ta- bela, para cada estágio seus respectivos grupos, movimentos permitidos, números de elementos possíveis, isto é, todas as possíveis combinações que o cubo pode assumir para aquele grupo e um fator, que é de�nido pelo número de repetições que cada está- gio gera, isto é, a ordem do grupo. Vejamos a tabela 5.1 que representa estas condições. Tabela 5.1: Grupos do algoritmo de Thistlethwaite Grupo Movimentos Número de posições Fator G0 L,R, F,B, U,D 4, 33 · 1019 211 = 2048 G1 L,R, F,B, U2, D2 2, 11 · 1016 37 · ( 12 4 ) = 1082565 G2 L,R, F 2, B2, U2, D2 1, 95 · 1010 2 · 3 · ( 8 4 )2 = 29400 G3 L2, R2, F 2, B2, U2, D2 6, 63 · 105 4!5 12 = 663552 Por exemplo, no grupo G0 o número de posições são todas as possibilidades possí- veis que o cubo pode assumir e que foi demonstrada no Capítulo 4. Neste caso, o fator é obtido considerando que os cubinhos de aresta serão todos orientados corretamente e, portanto somente estes é que serão permutados. Como cada um deles possui 2 cores e pela paridade somente 11 dos 12 cubinhos poderão ter suas 2 cores alternadas, logo chegamos ao valor 211, que seria o pior caso onde todos os cubinhos precisariam ser orientados corretamente. Para os demais grupos o raciocínio é análogo, exceto pelas restrições de movimentos particulares de cada um deles. Cada estágio do algoritmo é baseado em tabelas2 que mostram a sequência de permutação de cada elemento do subgrupo em que o cubo mágico se encontra. 5.1.2 Método realizável por humanos Em 2003 um australiano chamado Ryan Heise conseguiu construir um método de resolução que tornou o algoritmo de Thistlethwaite adaptado a nós humanos. De todos os métodos conhecidos, este sem dúvidas é o mais e�ciente, porém o mais complexo. Seu princípio está baseado em um profundo conhecimento do cubo mágico, o que o torna um método intuitivo e com poucas memorizações. O resultado é que com poucos movimentos se chega à resolução do cubo mágico. Este método também se baseia em 4 etapas. Na primeira os cubinhos são montados de forma a se ter 4 quadrados3. Na 2Vide referência [7] 3Aqui considera�se um quadrado a con�guração 1x2x2 Resolvendo o Cubo Mágico no menor tempo 67 segunda etapa os quadrados são rearranjados de modo a orientar os cubinhos de aresta que os compõem. Na terceira etapa se orienta o cubinhos de arestas restantes e mais 2 cubinhos de canto quaisquer. Na quarta e última etapa os últimos 3 cubinhos de canto restantes são orientados corretamente através de comutadores. É na 3a etapa que en- contramos a complexidade deste método, pois a liberdade de movimentos é bastante diminuída, a�nal o principal objetivo é não se desmontar aquilo que já está montado. Por ser um método que não prevê formas pré�determinadas, a cada vez que se inicia a resolução, diferentes con�gurações são obtidas. Por esta razão se torna necessário ana- lisar muito bem como o cubo está antes de se realizar qualquer movimento e, portanto não é um método que visa a resolução do cubo no menor tempo possível. 5.2 Resolvendo o Cubo Mágico no menor tempo De todos os métodos que procuram otimizar o tempo, o mais e�ciente é o que foi proposto pela tcheca Jessica Fridrich no início dos anos 80. É conhecido como mé- todo CFOP , pois são as siglas, em inglês, de cada uma de suas 4 etapas: C = Cross, F = F2L (�rst 2 layers), O = OLL (Orientation of Last Layer) e P = PLL (Permuta- tion of Last layer). A primeira etapa tem como objetivo deixar corretamente orientado os 4 cubinhos de aresta de uma determinada face escolhida, formando assim uma �cruz�. Na segunda etapa o objetivo é orientar os 4 cubinhos de canto desta face escolhida jun- tamente com os cubinhos de aresta, adjacentes a cada um deles, da camada mediana em suas corretas orientações. Isto é feito em 4 partes, uma de cada vez, unindo�se o cubinho de canto com o seu respectivo cubinho de aresta adjacente da camada mediana e os coloca em suas posições corretas e já orientados. Ao �nal desta etapa já se obtém 2 camadas prontas. A terceira etapa tem como objetivo apenas orientar a face oposta àquela escolhida no início, sem se preocupar em deixar pronta a terceira camada, que é o que será feito no último passo. Na quarta etapa o objetivo é permutar os cubinhos, tanto de aresta quanto de canto da última camada de modo a colocá�los em suas po- sições corretas. A �gura 5.1 ilustra a sequência de montagem de cada uma das 4 etapas. Ao seguir este algoritmo, após a 1a etapa, observa�se um conjunto relativamente pequeno de casos que sempre se repetem, isto é, existe um padrão. Para cada caso o método prevê uma sequência de movimentos especí�ca, de modo a se atingir a próxima etapa. Por esta razão este método torna�se possível de ser memorizado e, portanto de rápida execução. Foi utilizando este método que se obteve o atual recorde mundial de montagem mais rápida do cubo mágico, de 4,90 segundos. A tabela 5.2 mostra o número de casos que cada etapa apresenta. Embora este método traga o benefício da velocidade, é necessária a memorização 68 Resolvendo o Cubo Mágico Figura 5.1: Sequência de montagem de cada uma das 4 etapas. Tabela 5.2: Etapas do método de Fridrich Etapa Número de casos 1a Etapa � Cross intuitivo 2a Etapa � F2L 41 3a Etapa � OLL 57 4a Etapa � PLL 21 de dezenas de sequências diferentes uma para cada caso. 5.3 Resolvendo o Cubo Mágico com a menor memo- rização Invariavelment,e ao se manipular o cubo mágico na tentativa de resolvê�lo, algumas sequências acabam sendo memorizadas, devido à sua repetição. Entretanto, através do entendimento do funcionamento do cubo e de suas regras, algumas sequências tor- nam�se intuitivas, que é o caso dos comutadores e conjugados. É possível portanto, elaborar uma estratégia de resolução do cubo de Rubik apenas utilizando tais sequên- cias. É o que iremos propor a seguir como uma proposta de resolução do cubo mágico com a menor memorização possível. Para isto utilizaremos alguns dos comutadores e conjugados analisados no Capítulo 4. Nossa estratégia terá 5 etapas. Na primeira escolheremos uma face para iniciar, e Resolvendo o Cubo Mágico com a menor memorização 69 nela posicionar e orientar os cubinhos de aresta formando a �cruz� vista no método de Fridrich. Na segunda etapa iremos posicionar e orientar os quatro cubinhos de aresta que pertencem à intersecção da camada mediana com as faces adjacentes àquela esco- lhida na primeira etapa. Na terceira etapa iremos posicionar e orientar os cubinhos de aresta da face oposta àquela escolhida na primeira etapa. Ao �nal desta etapa obser- varemos a formação da �cruz� em todas as seis faces do cubo. Na quarta etapa iremos apenas posicionar os cubinhos de canto, para então na quinta e última etapa orientar todos eles. Ao �nal desta etapa teremos o cubo resolvido. Vamos agora detalhar cada uma das etapas. 5.3.1 1a Etapa: formar uma cruz na face inicial Primeiramente escolhemos uma face para iniciar e recomenda�se escolher sempre a mesma de modo a facilitar a repetição do método. Uma sugestão é iniciar pela face branca, entretanto tal escolha não implica na perda de generalidade do método. Para formar a cruz, não há nenhuma sequência em especial, e para atingi�la é possível uti- lizar apenas a simples intuição. 5.3.2 2a Etapa: formar uma cruz nas faces adjacentes Para resolver a segunda etapa iremos sempre deixar para frente uma das 4 faces adjacentes àquela escolhida no início e será nela que iremos orientar os cubinhos RF ou LF . Por exemplo, vamos escolher o cubinho laranja/verde para colocar em sua posição e orientação correta. Se ele estiver na face superior iremos observar qual das duas co- res está na face frontal. Caso seja a laranja, então iremos posicioná�lo em UF na face laranja. Caso seja a verde, de modo análogo, então iremos posicioná�lo em UF na face verde. Se a posição correta dele for em RF então aplicaremos a macro U ′ F ′ UF . Caso contrário, se a posição correta dele for em LF então aplicaremos a macro UFU ′ F ′ . Mas caso ele esteja na camada mediana com a posição e/ou orientação errada basta aplicar qualquer uma das macros anteriores para movê�lo à camada superior. O pro- cesso se repetirá até que os quatro cubinhos de aresta da camada mediana estejam em suas posições e orientações corretas. 5.3.3 3a Etapa: formar uma cruz na face oposta à inicial Para esta etapa, como referência, deixaremos voltada para a frente a face oposta àquela escolhida no início. O objetivo será deixar os 4 cubinhos de aresta desta face em suas posições e orientações corretas. Primeiramente devemos deixar todos os quatro 70 Resolvendo o Cubo Mágico cubinhos orientandos corretamente, isto é, com suas cores correspondentes à face fron- tal, voltadas para frente. No caso de nossa sugestão deveremos deixar todos os quatro cubinhos com suas cores amarelas voltadas para frente. Para isso iremos utilizar a macro (RU ′ R ′ U)(F ′ UFU ′ ). Esta macro irá permutar a orientação dos cubinhos que estão em UF e RF . Uma vez orientados iremos posicioná�los corretamente utilizando a macro (U ′ F ′ )(U ′ F )(U ′ F ′ )(U ′ F )U ′ . Esta macro irá permutar a posição dos cubinhos que estão em UF e RF . Ao �nal desta etapa observaremos a formação da �cruz� em todas as seis faces do cubo. 5.3.4 4a Etapa: posicionar os cubinhos de canto Nesta etapa iremos permutar os cubinhos de canto de modo a apenas posicioná-los corretamente sem nos preocupar com suas orientações. As macros para esta etapa per- mutam, tanto no sentido horário quanto no sentido anti�horário, 3 cubinhos de canto da face superior que estão em FLU , FRU e BRU , sem preservar suas orientações. Para isto iremos sempre observar quais 3 cubinhos devem ser permutados de modo a serem posicionados corretamente. Uma vez entendido quais cubinhos de canto serão afetados pela macro e quais necessitam ser permutados aplicaremos os seguintes co- mutadores: R ′ (ULU ′ )R(UL ′ U ′ ) para o sentido horário ou (ULU ′ )R ′ (UL ′ U ′ )R para o sentido anti-horário. O processo se repetirá até que todos os cubinhos de canto estejam corretamente posicionados. Note que não é necessário memorizar as duas macros, uma vez que para ter o efeito de uma basta aplicar a outra duas vezes. 5.3.5 5a Etapa: orientar os cubinhos de canto Nesta última etapa, utilizaremos dois conjugados que permutam a orientação dos cubinhos que estão em FLU e FRU . De acordo com o capítulo anterior, devido à pari- dade, toda vez que permutamos a orientação do cubinho em FLU no sentido horário, a orientação do cubinho em FRU também tem sua orientação permutada, porém no sen- tido anti-horário e vice-versa. As macros para esta etapa são as seguintes: Rotacionar o cubinho em FLU no sentido horário é (LD2L ′ F ′ D2F )U(F ′ D2FLD2L ′ )U ′ e rotacionar o cubinho em FLU no sentido anti-horário é (F ′ D2FLD2L ′ )U ′ (LD2L ′ F ′ D2F )U . O processo se repetirá até que todos os cubinhos de canto estejam corretamente orien- tados. Note que não é necessário memorizar as duas macros, uma vez que para ter o efeito de uma basta aplicar a outra duas vezes. Resolvendo o Cubo Mágico com a menor memorização 71 5.3.6 Resumo No sentido de facilitar a visualização do método, a tabela abaixo resume cada uma de suas etapas, seus objetivos e as macros que são necessárias. Tabela 5.3: Etapas, objetivos e as macros necessárias. Etapa Objetivo Macros 1a etapa Formar uma cruz em uma das fa- ces. intuitivo 2a etapa Organizar os 4 cubinhos de aresta, na camada mediana, das faces adjacentes àquela escolhida na 1a etapa. U ′ F ′ UF ou UFU ′ F ′ 3a etapa Organizar os cubinhos de aresta da face oposta àquela escolhida na 1a etapa, formando uma cruz em todas as seis faces do cubo má- gico. (RU ′ R ′ U)(F ′ UFU ′ ) ou (U ′ F ′ )(U ′ F )(U ′ F ′ )(U ′ F )U ′ 4a etapa Posicionar corretamente todos os 8 cubinhos de canto R ′ (ULU ′ )R(UL ′ U ′ ) ou (ULU ′ )R ′ (UL ′ U ′ )R 5a etapa Orientar corretamente todos os 8 cubinhos de canto (LD2L ′ F ′ D2F )U(F ′ D2FLD2L ′ )U ′ ou (F ′ D2FLD2L ′ )U ′ (LD2L ′ F ′ D2F )U Este método apresenta poucas macros, que por sua vez, são intuitivas. Contudo em cada etapa, de maneira geral, será necessário repetir cada macro diversas vezes, o que torna o método lento e com muitos movimentos. 6 Aplicação Escolar Neste capítulo iremos apresentar, aos docentes, uma proposta didática que con- siste de um método básico para resolver o cubo mágico, por exemplo, em sala de aula, já que muito provavelmente os estudantes são leigos em sua resolução. A ideia mais importante para quem esteja começando é manipular o cubo individualmente. A fami- liaridade é imprescindível, sempre com o objetivo de se compreender o mecanismo do cubo, isto é, como girar as faces e mover apenas um cubinho para uma determinada posição e orientação como se queira. Devido ao fato de que é necessário uma boa abstração e noções espaciais, aconselha- se que esta proposta seja aplicada a partir do 6o Ano do Ensino Fundamental II. Muito embora não seja raro se deparar com crianças com idade inferior a 11 anos que saibam resolver o cubo mágico rapidamente. 6.1 Apresentação e funcionamento do cubo mágico Apresente aos alunos as 6 faces e como são seus movimentos, tanto no sentido- horário quanto no sentido anti-horário. Diferencie os 3 tipos de cubinhos e mostre que o cubinho central determina a cor da face, e que há um padrão em relação às faces opostas: a face branca é sempre oposta à amarela, assim como a azul é oposta à verde e a laranja é oposta à vermelha. Nesta etapa deixe livremente os alunos manipularem o cubo para que eles mesmos possam criar suas hipóteses e assim compreenderem melhor o seu funcionamento. 6.2 Códigos de cada movimento Apresente aos alunos as nomenclaturas tanto das faces quanto dos cubinhos. Aqui é importante ressaltar o padrão que é adotado aos códigos das faces bem como seus movimentos. Explique, por exemplo, que girar a face direita no sentido horário é feita neste sentido, porém em relação a alguém que a olharia de frente, e não em relação 73 74 Aplicação Escolar a quem está manipulando o cubo. Por conta deste padrão, mostre a importância de segurar o cubo corretamente, principalmente durante a execução das macros. Rotaci- onar o cubo durante uma sequência de movimentos seguramente acarretará em obter um resultado diferente do esperado. Uma vez entendido como são realizados os códigos em cada face do cubo é que pode-se passar para a sua resolução propriamente dita. 6.3 Resolução do Cubo Mágico pelo método de ca- madas Este algoritmo pode ser usado sem a necessidade de se compreender o signi�cado de cada movimento durante a execução das macros. Por conta disso, dizemos que um método quase que totalmente mecânico, exceto pela 1a etapa que exige a intuição para concluí-la. O restante das etapas torna-se um processo memorizado. 6.3.1 Etapa 1: Formar uma cruz branca Nesta primeira etapa o objetivo é alcançar, com a face branca voltada para cima, uma cruz, conforme a �gura 6.1. Figura 6.1: Objetivo da Etapa 1. Oriente os alunos a manterem sempre a face branca para cima, e escolherem entre as faces vermelha, azul, verde ou laranja para �caram voltadas para frente. A ideia é posicionar os cubinhos de aresta correta um de cada vez. 6.3.2 Etapa 2: Posicionar os cantos brancos O objetivo desta etapa é organizar a 1a camada, posicionando os cubinhos de canto corretamente, conforme a �gura 6.2. Ainda com a face branca voltada para cima, os cubinhos de canto devem ser posici- onados um de cada de vez. Por exemplo, vamos iniciar pelo cubinho branco, vermelho Resolução do Cubo Mágico pelo método de camadas 75 Figura 6.2: Objetivo da Etapa 2. e azul. O cubinho que estamos procurando pode estar na face debaixo, e neste caso devemos posicioná-lo na aresta que é o encontro das 3 cores que estamos querendo po- sicionar, utilizando apenas os movimentos D ou D ′ . As possibilidades são mostradas na �gura 6.3. Figura 6.3: Possibilidades da Etapa 2 � cubinhos na camada debaixo. Para levar o cubinho ao seu local correto repita, quantas vezes for necessário (no máximo 3), a seguinte macro: R ′ D ′ RD. Caso o cubinho procurado não esteja na face debaixo, então ele estará na face