Solution to problem 1
Starting from any permutation of [1,2,3,4,5] (or [1,2,3,4,5,6,7]), using the above rules, you can always order the numbers. A way to proceed is the following:
step 1: Find a sequence of moves which put the last cell in the
last place (in the two examples, to put the cell with nr. 5 in the fifth
place or the cell with nr. 7 in the seventh place respectively);
step 2: After the previous step, the problem is simplified: if you forget the last cell and the last button, now you are playing with a similar game, but with one cell less and one exchange button less; hence you can apply step 1 again to this new game.
Solution to problem 2
The answer is affirmative also in this case. One way to get the solution
is the following:
step 1: if the cell which is in the first position is different from 5 and contains a number bigger than the number contained in the cell in the second position, exchange them and go to step 2;
otherwise go directly to step 2;
step 2: if all the cells are in the right position, then the game is over, otherwise apply one shift and go back to step 1.
It is clear that this procedure works for any number of cells.
Solution to problem 3.
The problem does admit a solution: probably the fastest is the following:
1) click twice on the shift button;
2) click once on the exchange button.
Solution to problem 4
Game 5 does NOT admit a solution. Let us try to give an explanation.
To facilitate the argument, let us consider the following concrete example: five people are in a queue waiting to be served by a teller of an office, but the office has to close and will be opened the day after. Since the five people do not want to loose their position in the queue, the teller gives to each of them a number which corresponds to their position in the queue. Hence the person in position 1 gets number 1, the person in the second position gets number 2 and so on. The day after the five people come back randomly and start a new, different queue. Suppose that now at the first position we have the person that the day before had number 3, at the second position we have the person with number 5, then the person with number 2, then that with number 4 and finally, in the last position, suppose we have person with number 1. We can summarize the situation with this sequence of numbers (permutation):
that we shall denote also with [3,5,2,4,1] and which is precisely the permutation written at the beginning of game 4. What surely happens is that while these people are waiting, they start arguing: everybody has surely counted the number of people had passed her/him. For instance, the person which has number 2 in his pocket has been passed by two people: number 3 (which is now in the first position) and number 5 (which is now in the second position). Let us count the number of passing in our example:
the person with nr. 3 has been passed by 0 people;
the person with nr. 5 has been passed by 0 people;
the person with nr. 2 has been passed by 2 people (nr. 3 and nr.5);
the person with nr. 4 has been passed by 1 people (nr. 5);
the person with nr. 1 has been passed by 4 people (all the others);
The total amount of passing is: 7 (=0+0+2+1+4).
Let us suppose now that we want to order the queue of the 5 people with the two rules of game 5, that is with:
R1) the last person goes to the first position and all the other people shift of one position;
R2) the first two people can exchange and countemporarily also the last two people.
If for instance we apply the rule R1 to our queue, we get the new configuration (permutation):
In this case the number of total passing has become 3, i.e. rule R1 has decreased the number of passing by 4. It is easy to see that, whatever configuration you consider, both the rules R1 and R2 decrease or increase the number of passing of an even number. (If you are not convinced, try to count the number of passing for some configurations produced by game 5). Let us see now if it is possible, using only rules R1 and R2, to get the configuration:
(that is, the configuration where every person occupies the position
he/she should occupy). If we count the number of passing that we have in
this last permutation, we see that it is 0. If this configuration were
obtainable starting from the permutation [3,5,2,4,1] (those with 7 passing
considered at the beginning), it would mean that, starting from number
7 and adding or subtracting only even numbers we are able to get 0. Since
this is clearly impossible (odd plus even=odd and 0 is even), game 5 does
not admit a solution.
What here was caled "passing" in mathematics is called class. If for a permutation the number of passing is even, we say that the permutation is of even class (or simply even), otherwise is of odd class (or odd). For instance the permutation [3,5,2,4,1] is an odd permutation, while the permutation [3,5,4,2,1] is even.
The set of all even permutations of the numbers 1,2,3,4,5 gives a very important mathematical object which is called the alternating group A5. More generally, the totality of even permutations of the numbers 1,2,...,n (computed in the same way as above) gives what is called the alternating group An.
Exercise: Since game 5 cannot give the permutation [1,2,3,4,5], try at least to get the permutations [1,2,3,5,4] and [2,1,3,4,5].
Solution to problem 5
To immediately see the solution to the problem is probably not possible.
It is therefore a good idea to formulate some sub-tasks and try to solve
them. Let us therefore consider the following sub-tasks:
a) Put the cell with number 1 in the right position;
b) Put then the cell with number 2 in the right position;
c) Put finally the cell with number 3 in the right position.
If you want to try again the game after these suggestions, click here, otherwise continue.
Problem a) is easy and does not require further explanations. As soon
as problem a) is solved, problem b) is easy if the cell with number 2 is
not in position 4. In this case it is enough to apply g sufficientely many
times. If otherwise cell nr. 1 is in the right position, and cell nr. 2
is in position 4 (i.e. below 1), then it is convenient to apply, in the
order: f-1 then g-1 and then f. In this way cell
nr. 1 is again in the right position and cell nr. 2 is in position 6. If
now you apply g twice, you put cell nr. 2 in the right position. Finally,
if cells 1 and 2 are set and cell nr. 3 is not, a way to folow is the following:
f-1 (in this way cells with nr. 1 and nr. 2 go on the first
column and are not moved by g), then repeat g sufficientely many times,
until 3 is in the right position and then put 1 and 2 in their correct
position with f. What happens is that now necessarily also the other
cells are in the right positions. Hence problems a), b) and c) give the
complete solution to the game. This last claim sould be proved... we leave
it as an exercise.
An alternative way to proceed is that of putting first cells nr. 1 and nr. 2 in the right position.
Solution to problem 7
The answer to the first question is affirmative. The result shows a
well known group theory theorem which claims that the order of any element
in a finite group is a finite.
If h:=fg, then h-1 is given by g-1f-1; if h:=fgf-1gf2, then h-1 is given by f-2g-1fg-1f-1. In general, the inverse of a move h is obtained writing in the reverse order the moves which compone h after the substitution f-1 in the place of f, g-1 in the place of g, f in the place of f-1 and g in the place of g-1 (hence f-2 in the place of f2 etc.).
Solution to problem 9
A very simple solution is the following: ghg-1. Its meaning
should be clear: g puts the small cubes 2,3 and 5 in the places (respectively)
3, 6 and 2. Applying then h the position are not changed, but the upper
central cube and the two right cubes are rotated, that is precisely those
cubes where now we have put 2,3 and 5. Finally, g-1 puts all
the cubes in their correct position.
Solution to problem 10
a) probably the easiest solution is to consider the inverse of the move
h (which is fg2f-1g-1fg-1f-1g2),
hence the move: g2fgf-1gfg2f-1
(see the solution of problem 7).
b) It is enough to exchange f with g in h.
c) Let j be the move defined in b). Then fjf-1 produces what we need.
Solution to problem 11
You get a new element of H (which rotates the cubes 3, 5 and 6 of 120
Solution to problem 12
The way to proceed is the same considered when we solved problem 9.
b) g^2fhif^-1g^2: this move is composed by three parts. The first is g^2f and has the effect to put the cube 1 in the place of the cube 2 and the cube 6 in the place of the cube 5; the second part is hi which does not change the position of the cubes, but only the orientation of three of them; the third part is the inverse of the first part, so in this way the cubes go back to the correct position (although some of them are rotated).
c) f^-1gf^-1hifg^-1f (the move f^-1gf^-1, first part of the move here written, puts the cube 1 in the place of the cube 5 and the cube 6 in the place of the cube 2. The idea of this move is already explained above.
Some further theorical remarks
The game 7 (hence the central part of game 9) is a group G, the group of all permutations - compatible with the defined moves - of the 6 faces of the 6 small cubes. The set H defined in the text is a normal subgroup of G (the red property shows that it is indeed normal). Finally, game 6 (hence the left part of game 9) is a way to express the quotient group G/H.