Group Theory and the Rubiks Cube PDF

The Mathematics of Rubiks Cube

Jan 30 2011 mathematical structure called a group. One can solve Rubik's cube using two basic ideas from group theory: commutators and conjugation.

The Mathematics of the Rubiks Cube

Introduction to Group Theory and Permutation Puzzles. March 17 2009. Introduction. Almost everyone has tried to solve a Rubik's cube.

Group Theory and the Rubiks Cube.pdf

We will both develop methods for solving the. Rubik's cube and prove (using group theory!) that our methods always enable us to solve the cube. References.

Group Theory via Rubiks Cube

Group Theory via Rubik's Cube. Tom Davis tomrdavis@earthlink.net http://www.geometer.org. ROUGH DRAFT!!! December 6 2006

Adventures in Group Theory: Rubiks Cube Merlins Machine

http://www.sandal.tw/upload/Adventures%20in%20Group%20Theory_%20Rubik's%20Cube

Group Theory and the Rubiks Cube

In mathematics the Rubik's Cube can be described by Group Theory. The different transformations and configurations of the cube form a subgroup of a permutation

Solving the Rubiks Cube using Group Theory

theory the Rubik's Cube

Rubiks cube and Group Theory

Rubik's cube and Group Theory by. Carl Joakim Isaksen. Thesis for the degree of. MASTER OF SCIENCE. (Master i Anvendt matematikk og mekanikk).

Group Theory Visualized Through the Rubiks Cube

Feb 26 2021 Group Theory Visualized Through the Rubik's Cube. By. Ashlyn Okamoto. An undergraduate honors thesis submitted in partial fulfillment of the.

Group Theory and the Rubiks Cube

Oct 18 2019 People even make mosaics using multiple cubes! Robert A. Beeler

The moves that one can perform on Rubik’s cube form amathematical structure called agroup One can solve Rubik’s cube using two basic ideas from group theory: commutatorsandconjugation Some notation Basic moves on Rubik’s cube: F=rotate the front face one quarter turn clockwise B=rotate the back face one quarter turn clockwise

The Mathematics of the Rubik’s Cube - MIT

The Mathematics of the Rubik’s Cube Introduction to Group Theory and Permutation Puzzles March 17 2009 Introduction Almost everyone has tried to solve a Rubik’s cube The ?rst attempt often ends in vain with only a jumbled mess of colored cubies (as I will call one small cube in the bigger Rubik’s cube) in no coherent order Solving

Group Theory and the Rubik's Cube - Harvard University

There are several books about the Rubik’s cube; my favorite is Inside Rubik’s Cube and Beyond by Christoph Bandelow David Singmaster who developed much of the usual notation for the Rubik’s cube also has a book called Notes on Rubik’s ’Magic Cube’ which I have not seen

The Mathematics of the Rubik's Cube - MIT

Almost everyone has tried to solve a Rubik’s cube The rst attempt often ends in vain with only a jumbled mess of colored cubies (as I will call one small cube in the bigger Rubik’s cube) in no coherent order Solving the cube becomes almost trivial once a certain core set of algorithms called macros are learned Using

How to Solve the Rubik's Cube - Stanford University

How to Solve the Rubik's Cube by Shelley Chang (appropriated by Lucas Garron) Notation A letter by itself (e g F) means turn that face 90 degrees clockwise with respect to the center of the cube A letter with an apostrophe (F') denotes a 90 degree counter-clockwise turn A letter followed by the number 2 (F2) denotes 2 turns i e a 180

Searches related to theory of rubik+s cube PDF

In this paper we will investigate some ofthe interesting mathematical structure underlying the Rubik's Cube which wasdocumented by David Joyner in his bookAdventures in Group Theory[Joy] Let us consider a standard Rubik's cube unmarked 333 Rubik's Cube Furthermore we will imagine that we x the center facets of the cube so thatwe do not

How to solve a Rubik's cube?

Almost everyone has tried to solve a Rubik’s cube. The ?rst attempt oftenends in vain with only a jumbled mess of colored cubies (as I will call onesmall cube in the bigger Rubik’s cube) in no coherent order. Solving the c?comes almost trivial once a certain core set of algorithms, called macros,are learned.

What is the front face of a Rubik's cube?

Guide for beginner cubers When holding your Rubik’s cube, the side of the cube that is facing you is called the “Front Face”. This will be your basis for determining the other sides of the cube.

How many permutations are there on a Rubik's cube?

The number of possible permutations of the squares on a Rubik’s cube seemsdaunting. There are 8 corner pieces that can be arranged in 8! ways, eachof which can be arranged in 3 orientations, giving 38possibilities for eachpermutation of the corner pieces. There are 12 edge pieces which can bearranged in 12! ways.

What is a 90 degree turn in a cube?

A letter by itself (e.g. F) means turn that face 90 degrees clockwise with respect to the center of the cube. A letter with an apostrophe (F') denotes a 90 degree counter-clockwise turn. A letter followed by the number 2 (F2) denotes 2 turns, i.e. a 180 degree turn. Part 1: First Layer Edges

Group Theory and the Rubik's Cube

Lindsey Daniels

A project submitted to the Department of

Mathematical Sciences in conformity with the requirements for Math 4301 (Honours Seminar)

Lakehead University

Thunder Bay, Ontario, Canada

Abstract

The Rubik's Cube is a well known puzzle that has remarkable group theory properties. The objective of this project is to understand how the Rubik's Cube operates as a group and explicitly construct the Rubik's Cube Group. i

Acknowledgements

I would like to thank my supervisors Dr. Adam Van Tuyl and Dr. Greg Lee for their expertise and patience while preparing this project. ii

Abstracti

Acknowledgements ii

Chapter 1. Introduction 1

Chapter 2. Groups 3

1. Preliminaries 3

2. Types of Groups 4

3. Isomorphisms 6

Chapter 3. Constructing Groups 9

1. Direct Products 9

2. Semi-Direct Products 10

3. Wreath Products 10

Chapter 4. The Rubik's Cube Group 12

1. Singmaster Notation 12

2. The Rubik's Cube Group 12

3. Fundamental Theorems of Cube Theory 16

4. Applications of the Legal Rubik's Cube Group 20

Chapter 5. Concluding Remarks 22

Chapter 6. Appendix 23

Bibliography 24

iii

CHAPTER 1 Introduction

In 1974, Erno Rubik invented the popular three dimensional combination puzzle known as the Rubik's Cube. The cube was rst launched to the public in May of 1980 and quickly gained popularity. Since its launch, 350 million cubes have been sold, becoming one of the best selling puzzles [2]. By 1982, the cube had become part of theOxford English Dictionaryand a household name [5]. In 1981, David Singmaster publishedNotes on Rubik's `Magic Cube'which was the rst analysis of the Rubik's Cube, and provided an algorithm for solving it. Singmaster also introduced `Singmaster Notation' for the dierent rotations of the cube [10]. Today, numerous methods for solving the cube exist. When the cube was rst introduced to the public, the focus was on solving the puzzle. Today, the Rubik's Cube is still popular; however, the focus has changed. Speed-cubing competitions are held through the World Cube Association, where participants attempt to solve the cube as fast as possible [2] (the current world record for solving the cube is 5:55 seconds [7]). There is also interest in nding the maximum number of minimum moves needed to put the cube into its solved state from any position. This number is called God's Number and in 2010 was determined to be 20 [9]. God's Number, however, does not say which twists and turns are needed to solve the cube, it merely states what the maximum number of moves is. The challenge for the solver is to nd the 20 moves (or less) that are required [8]. Since its creation, the cube has been studied in a variety of elds such as computer science, engineering and mathematics. In mathematics, the Rubik's Cube can be described by Group Theory. The dierent transformations and congurations of the cube form a subgroup of a permutation group generated by the dierent horizontal and vertical rotations of the puzzle [2]. The solution to the cube can also be described by Group Theory [5]. Group Theory allows for the examination of how the cube functions and how the twists and turns return the cube to its solved state. This project will explore the construction of this permutation group, as well as the associated properties and theorems. This project will follow the method of David Joyner'sAdventures in Group Theory: Rubik's Cube, Merlin's Machine and Other Mathematical Toysto construct the Rubik's Cube Group. To begin, in Chapter 2, the preliminary properties of a group are reviewed. The dierent types of groups needed to construct the Rubik's Cube Group will be dened, as well as the First Group Isomorphism Theorem. Chapter 3 presents the three dierent products that are used in the Rubik's Cube Group. Some of the related properties of these products are also described. In Chapter 4, Singmaster Notation will be introduced 1

Chapter 1. Introduction2

and the First and Second Fundamental Theorems of Cube Theory are presented. Here, the Rubik's Cube Group will be explicitly constructed. In Chapter 5 a short summary is provided, along with some possible extensions of this paper. Finally, in Chapter 6 an appendix of move sequences is provided.

CHAPTER 2 Groups

In this chapter, the denition of a group and some of the associated properties are reviewed. Several dierent types of groups are discussed, as well as the dierent isomor- phism theorems. The main sources for this chapter are [4] and [5].

1. Preliminaries

Before the Rubik's Cube Group can be constructed, many denitions from group theory will be needed. A review of the essential denitions from group theory are provided. Definition2.1.LetGbe a set with a binary operationsuch that :GG!G (g1;g2)7!g1g2: ThenGis agroupunder this operation if the following three properties are satised: (1) F orev erya;bandcinG, (ab)c=a(bc) (associativity). (2) Ther ee xistsan el ementesuch thatae=ea=afor allainG(identity element). (3) F orev eryelemen tainG, there existsa1such thataa1=a1a=e (inverses). Example2.2.LetGbe the set of integers,G=Z, andx;y;z2Gunder the operation of addition.

Since (x+y) +z=x+y+z=x+ (y+z),Gis associative.

The identity element ofGis 0 sincex+ 0 = 0 +x=x.

For eachx2G, there existsx2Gwithx+ (x) = 0. SoGcontains inverses.

SoGis a group under addition.

Notice that if the operation on the integers is changed to multiplication, thenGwould not be a group since the set would not contain inverses. For example, take the number

22Z. The inverse of 2 would be12

since 212 = 1, but12 =2Z. Definition2.3.Theorderof a groupG, denotedjGj, is the number of elements in G. 3

Chapter 2. Groups4

Definition2.4.LetHbe a subset of a groupG. IfHis a group with the same operation asG, thenHis asubgroupofG. Example2.5.LetGbe the set of integers modulo 6,G=Z6=f0;1;2;3;4;5g. Then Gis a group under addition mod 6. The order ofGisjGj= 6. A subgroup ofGwould beH=f0;2;4gunder addition mod 6.

Definition2.6.A groupGis anite groupifjGj<1.

Example2.7.For each positive integern >1,G=Znis a nite group sincejGj=n. Definition2.8.LetGbe a group andHG. The setaH=fahjh2Hgfor any a2Gis aleft cosetofHinG. Likewise the setHa=fhajh2Hgfor anya2Gis a right cosetofHinG. Theorem2.9 (Lagrange's Theorem).IfGis a nite group andHis a subgroup of G, thenjHjdividesjGj. Furthermore, the number of distinct right (or left) cosets ofH inGisjGj=jHj. A proof of Lagrange's Theorem can be found in [4]. Definition2.10.LetGandHbe nite groups andHG. TheindexofHinG is [G:H] =jGj=jHj. Example2.11.IfG=Z6=f0;1;2;3;4;5gandH=f0;2;4g, then [G:H] = jGj=jHj= 6=3 = 2:So there are 2 distinct left cosets ofHinG, and these two cosets are f0;2;4gandf1;3;5g. Definition2.12.LetGandHbe groups andHG. The subgroupHis anormal subgroup ofG, denoted byH / G, if, for eachainG,a1Ha=H(oraH=Ha). Example2.13.LetG=Z6=f0;1;2;3;4;5gandH=f0;2;4g. For eachg2G, g+H=H+gsince inZaddition is commutative. SoHis a normal subgroup ofGand denote byH / G.

Lemma2.14.LetS1,S2, ...,Sndenote nite sets. Then

jS1S2:::Snj=jS1j jS2j ::: jSnj. Proof.LetS1S2:::Sk=f(s1;s2;:::;sn)jsi2Sig. Now, there arejS1jchoices fors1,jS2jchoices fors2,jS3jchoices fors3, and so on. By the multiplication principle: jS1S2:::Skj=jS1j jS2j ::: jSkj:

2. Types of Groups

Many special types of groups can be constructed. In this section, the relevant groups that will be needed to construct the Rubik's Cube Group are outlined.

Chapter 2. Groups5

Definition2.15.A groupGis acyclic groupif there is some elementginGsuch thatG=fgnjn2Zg. The elementgis ageneratorof the groupG, denotedG=hgi.

The groupCndenotes the cyclic group of ordern.

Example2.16.IfG=Z6=f0;1;2;3;4;5g, then a cyclic subgroup would be<2>= f0;2;4g. Definition2.17.Apermutationof a setGis a one-to-one and onto function from

Gto itself.

Definition2.18.Acycleis a permutation of the elements in a setX=f1;2;3;:::;ng such thatx17!x27!x37!:::7!x1wherexi2X. Definition2.19.Any permutation can be written as a product of its cycles. This is calledcycle notation. If in the permutation, an element is sent to itself, the cycle is omitted from the cycle notation. Also, the identity permutation is denoted by (1). Example2.20.Take the setX=f1;2;3;4gand the permutation:X!Xwhere (1) = 2,(2) = 4,(3) = 1 and(4) = 3. As a cycle,is 17!27!47!37!1 and the cycle notation is (1243). Definition2.21.A cycle (x1x2:::xk) is called acycle of length k. Moreover, a permutation that can be expressed as a cycle of length 2 is called a 2-cycle. Definition2.22.If a permutation can be expressed as an even number of 2-cycles, then the permutation iseven. If a permutation can be expressed as an odd number of

2-cycles, then the permutation isodd.

Example2.23.Consider the permutation1 2 3 4 5

2 1 4 3 5

:In cycle notation, the permutation would be (12)(34)(5) or more simply, (12)(34). Since the permutation can be expressed by two 2-cycles, the permutation is even. Definition2.24.Thepermutation groupof the setSis the set of all permutations ofSthat form a group under composition. Example2.25.LetT=f1;2;3g. A permutation ofTwould be:T!Twhere (1) = 2,(2) = 3, and(3) = 1. The permutation can be written completely as =1 2 3 2 3 1 or in cycle notation= (123). The set of all permutations ofTis T

1=1 2 3

1 2 3 ;1 2 3 1 3 2 ;1 2 3 2 1 3 ;1 2 3 2 3 1 ;1 2 3 3 1 2 ;1 2 3 3 2 1 In cycle notation,T1=f(1);(23);(12);(123);(132);(13)g. The identity ofT1is the per- mutatione=1 2 3 1 2 3 = (1). Definition2.26.The permutation group ofnelements, denotedSnis called the symmetric group.

Chapter 2. Groups6

Definition2.27.The group of all even permutations, denotedAn, is called the alternating group. Definition2.28.LetGbe a group andH / G. Then thefactor groupis the group G=H=faHja2Ggunder the operation (aH)(bH) =abHfora;b2G. Example2.29.IfG=Z6=f0;1;2;3;4;5gandH=f0;2;4g, then the factor group

G=H=fa+Hja2Gg

=f(0 +f0;2;4g);(1 +f0;2;4g);(2 +f0;2;4g);(3 +f0;2;4g);(4 +f0;2;4g);(5 +f0;2;4g)g =ff0;2;4g;f1;3;5gg:

3. Isomorphisms

One of the important concepts in group theory is understanding how to construct isomorphisms. Definition2.30.A functionfrom a groupGto a groupHis ahomomorphism ifpreserves the group operation; that is, if(ab)=(a)(b) for alla;b2G. Example2.31.TakeG=S4andH=f1;1gunder the operation multiplication.

Dene the map:G!Hwith(a) =1aeven

1aoddfor everya2G.

To check thatis a homomorphism, the 4 possible cases will be veried:aandbboth even,aodd andbeven,aeven andbodd,aandbboth odd. Also, recall that the product of two even functions is even, the product of two odd functions is even, and the product of an even function with an odd function is odd.

Ifaandbare even, then(ab) =(a)(b) = (1)(1) = 1

Ifais odd andbis even, then(ab) =(a)(b) = (1)(1) =1 Ifais even andbis odd, then(ab) =(a)(b) = (1)(1) =1

Ifaandbare odd, then(ab) =(a)(b) = (1)(1) = 1

It is clear that even permutations are sent to 1 and odd permutations are sent to1.

Thusis a homomorphism.

Definition2.32.Anisomorphismis a homomorphism:G!Hthat is a one- to-one and onto. If such a function exists, thenGisisomorphictoHand denote this byG=H. Example2.33.LetG=ZandH= 2Zboth under the operation addition. Then :Z!2Zis an isomorphism where(a) = 2afor alla2Z. Definition2.34.Anautomorphismis an isomorphism from a groupGonto itself. The set of automorphisms of a groupGis denoted byAut(G).

Chapter 2. Groups7

Example2.35.TakeGto be any group under the operation of addition. Then :G!Gis an automorphism where(a) =afor alla2G. Definition2.36.LetGandHbe groups and letf:G!Hbe a homomorphism. Then thekernelofGis the set ker(f) =fg Gjf(g) =eHg, whereeHis the identity element ofH. Example2.37.Takef:Z!Znwherea7!a(modn). The identity ofZnis 0. So ker(f) =fa Zja=bn; b Zg=nZ. Lemma2.38.Letf:G!Hbe a homomorphism for any two groups,GandH. Thenker(f)is a normal subgroup ofGandG=ker(f)is a group. Proof.First, note that ker(f)6=;sinceeG7!eHby properties of homomorphisms. Next, to showker(f) is a subgroup ofG, it is enough to show that ifa;b2ker(f) thenab12ker(f). Leta;b2ker(f), thenf(a) =eHandf(b) =eH. Sof(ab1) =quotesdbs_dbs19.pdfusesText_25

[PDF] there is almost always a good reason for slow downs on an expressway

[PDF] there is no additive powder or tablet

[PDF] there is only single copy of member function in memory when a class is loaded

[PDF] therefore however nevertheless although exercises

[PDF] thermal decarboxylation

[PDF] thermochimie cours pdf psi

[PDF] thermodynamics 2 pdf

[PDF] thermodynamics notes pdf

[PDF] thermodynamics open system problems and solutions

[PDF] thermodynamics solution

[PDF] thermodynamics steam table problems pdf

[PDF] thermodynamics: closed system problems and solutions

[PDF] thermodynamique chimique smc s4 pdf

[PDF] thermodynamique cours pdf

[PDF] thermodynamique cours pdf mpsi

[PDF] Group Theory and the Rubiks Cube