Group games

Dipartimento di Scienze Matematiche
Università degli studi di Trieste

Java applets by: Alessandro Budai

Probably everybody had in his/her hands the puzzle called "Rubik's cube" or "Magic cube". It is made by a plastic cube whose faces can move in such a way that the small colored cubes which compose each face can permute. The aim of the game is to reconstruct the original cube.
One can prove that the number of different configurations of a Rubik's cube is:

227314537211=43252003274489856000,
that is, about 0.4*1020. In order to have an idea of how big is this number, suppose we want to show all the different configurations of the cube devoting precisely one second to each of them; this operation would take about 1370 billions of years (consider that the Sun will continue to burn for about 5 billions of years...). Hence to show all the possible configurations of a Rubik's cube seems to be an impossible task, but this should not discourage us: to find a solution to the puzzle it is not necessary to know all the possible configurations, it is enough to manage some of them with sufficient ability.
The aim of these animation is to introduce the interested reader to discover the strategy to follow in order to solve the Rubik's cube puzzle, without giving however the complete solution... On the contrary, some new puzzles will be introduced, similar but simpler than the Rubik's cube which will allow to discover possible solution strategies. We shall consider a generalized problem and we shall take the opportunity to introduce some mathematical concepts which are part of what is called group theory... In order to solve the puzzles here introduced no mathematical knowledge is necessary, although it maybe that people who know basic group theory can appreciate the exposition of known concepts in a slightly different way.

In the first puzzles, we shall play with a sequence of numbers, like this one: and with some rules which will establish how to exchange the numbers.

## Part A: first steps

Game 1: Here we have 5 numbers in five cells. To begin with, the numbers are ordered. The button "disorder" makes what it is supposed to do. There are 4 other buttons which give the allowed permutations: the first of them gives the exchange 1->2->1, that is exchanges the first two cells; analogously for the other buttons.

Problem 1: Starting from any configuration of the five numbers, is it always possible to rearrange the five cells in such a way that the cell with number 1 is in the first position, the cell with number 2 is in the second position and so on?

Clearly the same problem can be considered for a different number of cells, for instance 7, like in the:

Game 2: Same rules as above, but two more buttons, which exchange the cells in position 5 and 6 and the cells in position 6 and 7.

The answer to problem 1 is therefore affirmative: in order to permute in all possible ways the numbers 1,2,3,4,5 (or 1,2,3,4,5,6,7 or, in general, 1,2,...,n) it is enough to exchange all the consecutive cells.
This claim is a known math theorem (more precisely, it is a theorem in group theory) which is usually formulated as follows:

Theorem. The symmetric group Sn is generated by 2-cycles.

(The set of all the permutations of the numbers 1,2,...,n is called "the symmetric group Sn" and an exchange of two cells is called a "2-cycle"; another way to express the previous theorem is the following: any permutation of 1,2,...,n is a product of 2-cycles).

Let us go to the next game:

Game 3: Also here the button "disorder" exchanges the cells in all possible ways; there are now two other buttons: one exchanges the first two cells, the other one makes a shift which puts the first cell in the position of the second one, the second one in the position of the third one and so on; the last one goes in the first position. Finally, there is another button which makes the converse of the previous shift: it is unnecessary, since it makes the same effect that repeating 4 times the previous button, but it is useful.

Problem 2: Starting from any configuration of the cells, is it always possible to rearrange them? What about the case of more (or less) than 5 cells?

So, also here the answer is affirmative and also here the result is a well known theorem of group theory:

Theorem.  The symmetric group Sis generated by a 2-cycle and by an n-cycle.

Finally, let us consider another kind of permutations:

Game 4:  The allowed permutations are now: 1->2->3->4->5->1  and  1<->2 and contemporaneously 4<->5. The game starts with the configuration: [3,5,4,2,1] (we suggest not to use
the button "disorder" for the moment).

Problem 3: Starting from the configuration [3,5,4,2,1] is it possible to put the cells in the position [1,2,3,4,5]?

Game 5: Same as the previous game, but now we start from the configuration [3,5,2,4,1].

Problem 4: Same as problem 3.

The first of the two pervious games can be solved pretty soon. The second one however, despite of the number of tentative one could do, does not seem to be solvable. This is indeed the case. Here you can find an explanation:

So far, we have seen some groups: the symmetric groups Sn  and the alternating groups An (these last groups introduced in the previous solution).
If you want to further play with them and with some others groups click here.

## Part B: to the Rubik's cube

Let us now consider another category of games. Do not forget that our final aim is to manage the Rubik's cube.

Games 6: The problem, also here, is to rearrange a configuration of numbers inserted into cells. The allowed permutations are essentially two, which correspond to the first two buttons here denoted by f and g.

Maybe it is necessary to give some more explanations on the several buttons here defined:
• the button f rotates the first 4 cells of 90 degrees clockwise,
• the button g rotates the second square of cells of 90 degrees clockwise.
Moreover, in order to facilitate the study, there are some other buttons:
• f-1 denotes the inverse of the rotation f,
• g-1 gives the inverse of the rotation g.
Note that if you repeat f three times, you get f-1, and similarly for g: hence these two buttons are not necessary (but useful).
• In the white window you can write sequences of moves like, for instance: fgf^2g^-1 (which clearly means: make first the rotation f then the rotation g, then twice the rotation f and finally the rotation g-1. Note the syntax: for instance f-1 must be denoted by f^-1).
• To see the effect of a sequence of moves defined in the window, use the button "try".
• If you like the written sequence of moves, use  the "add" button, which adds a new button (which can be deleted with "del").
• The button "Store function" gives a name (for instance h, i,...) to the sequence of moves written in the window. The name, automatically assigned, appears in the right window. It can be used in the future expressions as well as f, g, ... hence, if for instance you have defined h:=fgf2g-1, now it is possible to write in the white window other expressions like fh^2gh^-1. Be careful of the syntax: for instance fg means: "apply first f and then g". Blank spaces are not allowed.
• The "reset" button puts the 6 cells in the original position (very useful if you want to start a new game).
Some practice will probably clarify the correct use of the buttons.

Problem 5: Mix up the six cells with the f and g buttons and then try to reconstruct the original sequence of numbers (the correct position of each cell is written in the background). Can you find a general strategy? Here there is a hint:

Problem 6: Find sequences of moves which, starting from the initial configuration, put the 6 cells again in the initial configuration (for instance: f^3f or f^2g^2g^2f^2 or f^2g^2f^2g^2f^2g^2 or...)

Problem 7: First of all, use the "reset" button, then define (with "add") a new button which contains a sequence of moves (say, for instance, fg^-1f^3g^2) and, starting from the initial configuration of the six numbers, press several times the new button. Is it true that after finitely many repetition of this button the six numbers occupy again the initial position? Let h be one of these sequences of moves then by h-1 (or h^-1) we denote the inverse sequence of moves (hence if you first apply h and then h-1 nothing happens). Suppose h is given by a sequence like fg or  fgf^-1gf^2 , how do you express h-1 in terms of f and g?

Finally, let us talk about Rubik's cube. To begin with, let us simplify the problem as much as possible: suppose we have a cube where only two adjacent faces can rotate. Furthermore, we shall concentrate only on the 6 small cubes which form the vertices of the two faces. What you get from a Rubik's cube with these restrictions is similar to what you get in the following:

Game 7: In this game the buttons have the same meaning of the buttons of the previous game. At the beginning we have 6 small cubes put in such a way that on the left (with respect to an observer) they all have the orange face, on the right the white face and above the yellow face (the three small squares colored in orange, white and yellow remain fixed and are useful to recall the correct position of the faces). Each small cube has moreover three hidden faces; their colors are: red (opposite to the orange), blue (opposite to the white face) and green (opposite to the yellow). Click randomly on the buttons in order to move the small cubes and then try to put them again in the correct position...

It is quite probable that after some steps you get a configuration from which it is not so easy to come back... However... Let's see... First of all, how is game 7 related to game 6? The explanation lies in the:

Game 8: The buttons have the same meaning of those in the previous games.

As you can see now, game 6 is a simplification of game 7: game 6 simulates the rotation of the 6 vertices of two adjacent faces of a Rubik's cube.
Click randomly on some buttons in order to mix up the small cubes and then try to rearrange them. While you are trying to rearrange the small cubes, however, forget about the right part of the animation and consider only the left part, (that is, consider only game 6). In this way, you are able to put the six small cubes in their correct position, but what you immediately discover is that: it is not enough to solve the left part of the game to solve the whole game: although the six small cubes occupy the correct position, they do not necessarily have the correct orientation. To be able to solve game 6 therefore is not enough in order to solve game 7. Nevertheless, we have done some steps to the whole solution of game 7.
What remains, is a problem with the orientations. But we also have another game:

Game 9: Same rules as above, but we have a third animation...

This last game shows what is still missing in the solution of the six small cubes game. The right picture is "active" precisely when the six small cubes occupy the correct position, that is precisely when the left part of the game is solved and, when active, denotes the orientation of the small cubes. Every triangle can assume one of the following three positions:   The first denotes that the corresponding cube is in the right orientation, the second one denotes that it is rotated of 120 degrees clockwise and the third denotes that it is rotated of 270 degrees clockwise. Some practice with the real Rubik's cube (or with game 7) shows that indeed every vertex (small cube) can occupy its correct position in only three different orientations, which correspond to the above possibilities and that can be summarized by:

• the right orientation;
• the position "rotated of 120 degrees clockwise with respect to one diagonal of the small cube";
• the position "rotated of 270 degrees clockwise with respect to the previous diagonal";
Clearly game 7 (or game 8 or game 9) is solved as soon as the six cells of the left animation of game 9 and, at the same time, the six triangles on the right are in the correct position.

Problem 8: Find some different orientations of the 6 triangles of game 9. In other words, mix up the game by clicking on the buttons f and g and then, as in game 6, fix only the six numbers of the left part of the game. In this phase of the game, you will probably find convenient to use the buttons "add" and "Store result".

From now on we shall call H the set of all possible moves which solve problem 8. Among all the elements of H, we focus our attention to the following move:

fg2f-1g-1fg-1f-1g2
(i.e. using the notation required in the white window: fg^2f^-1g^-1fg^-1f^-1g^2).

As you can immediately verify, this sequence of moves rotates the cubes 2,3 and 6 (that is, the upper central cube and the two right cubes) by 270 degrees clockwise. Let us denote by h this sequence of moves.

Problem 9: Find an element of H which rotates the cubes 2,3 and 5 by 270 degrees clockwise. (Among the several solutions, there is one particularly easy...)

Problem 10: Find:

a) an element of H which rotates the cubes 2,3 and 6 by 120 degrees clockwise;
b) an element of H which rotates the cubes 1, 4 and 5 by 270 degrees clockwise;
c) an element of H which rotates the cubes 2, 4 and 5 by 270 degrees clockwise;
Solution...

Problem 11: What do you get if in the h defined above you exchange f with f-1 and g with g-1 (which therefore gives i:=f-1g2fgf-1gfg2)?

The solution given to the previous problems allow in particular to construct new elements of H. If the idea followed to solve problem 9 and point c) of problem 10 is clear, then the following property of H should also be clear:

Property of H: if k is any element of H and if v is any move, then vkv-1 is again an element of H.

Solving the previous problems we have in particular constructed two elements of H which can be useful: the element h (given by fg^2f^-1g^-1fg^-1f^-1g^2) and the element i (that is f^-1g^2fgf^-1gfg^2). Try now to do the move hi (that is fg^2f^-1g^-1fg^-1f^-1g^2f^-1g^2fgf^-1gfg^2, (try it!)). It is clearly an element of H. Its effect (easy to predict, as soon as the effects of h and of i are known) is to rotate cube 2 by 270 degrees clockwise and cube 5 by 120 degrees clockwise.

Problem 12: Find a sequence of moves to:

a) rotate (only) cube 1 by 270 degrees clockwise and cube 2 by 120 degrees clockwise;
b) rotate (only) cube 1 by 270 degrees clockwise and cube 6 by 120 degrees clockwise;
c) rotate (only) cube 1 by 120 degrees clockwise and cube 6 by 270 degrees clockwise.
Solution...

At this point we have sufficiently may tools to give the complete solution to the puzzle proposed by game 7. The strategy to follow is the following: first of all put the 6 small cubes in the correct position, without considering their orientation. Successively, using for instance the move hi and considerations similar to those used to solve points a) b) and c) of problem 12, try to rotate a couple of small cubes, then another couple and so on, until the game is solved.

So far we have given a technique to solve a very specific sub problem of the general problem of the Rubik's cube. The introduced notions, however, are almost sufficient to fix the whole Rubik's cube. For two reasons: first of all, the strategy to follow in order to solve the whole puzzle is not different from the strategy here introduced and moreover the moves here introduced are already a good tool. Simply add to them the move:

hgig-1.
If you test it on a real Rubik's cube, its effect is very interesting: it rotates only three central small cubes. This move therefore, if used with cleverness, allows to fix all the central small cubes of a Rubik's cube. It still remains a problem to put in the correct position the 8 vertex cubes of a real Rubik's cube. This problem is not immediately solvable with the sequences of moves here introduced. As we said at the beginning, here we do not intend to give a complete solution to the puzzle...

If you are interested in some theoretical aspects of game 9, click here.

Comments or suggestions are welcome.
If you use these notes somewhere, you are
kindly request to cite the font.
e-mail to: logar@univ.trieste.it