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:
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.
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 S_{n} is generated by 2-cycles.
(The set of all the permutations of the numbers 1,2,...,n is called "the symmetric group S_{n}" 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 S_{n }is 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 S_{n}
and the alternating groups A_{n} (these last groups introduced
in the previous solution).
If you want to further play with them and with
some others groups click here.
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.
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:
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:
fg^{2}f^{-1}g^{-1}fg^{-1}f^{-1}g^{2}
(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;Solution...
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;
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^{-1}g^{2}fgf^{-1}gfg^{2})?
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;Solution...
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.
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:
If you are interested in some theoretical aspects of game 9, click
here.