Have the courage

Surely you have already worked with the Rubik’s Cube, or at least watched others do so. Of course, this cube has a lot to do with mathematics — but what exactly? The “Have the courage” puzzle is also of a similar nature. The commonality is that you can apply certain transformations one after the other, all of which can be reversed.

And now … the mathematics:

Group theory is a mathematical discipline that deals precisely with such structures: Given a certain structure (for example, the Rubik’s Cube or the sliding puzzle “Have the courage“), which can be transformed in a certain way. By this we mean that there are a lot of permissible Operations that transform into another state, so that two of these operations can be carried out in succession and there is a unique inverse Operation exists that will restore these undo. These operations on the structure now generate a Group. You probably already know many groups from school lessons. Here are a few examples:
- Let us assume that $X=\mathbb R$ is the real straight line on which we particularly mark out a point $\mathbf p$ . We can now apply to this straight line a displacement $\tau_r$ by a real number $r\in\mathbb R$ , i.e. $\tau_r$ transforms the point $x$ into $x+r$ and thus in particular $\mathbf p$ into $\mathbf p+r$ . Consider that performing the displacement $\tau_r$ and $\tau_s$ in succession is exactly the same as $\tau_{r+s}$ . Therefore, $\tau_r$ can be uniquely reversed by applying $\tau_{-r}$ . Thus a set $\{\tau_r \mid r\in R\}$ of admissible displacements generates a group $G$ operating on the real straight line. Here we can choose the set $R\subseteq\mathbb R$ arbitrarily, so that $r\in R$ is also $-r\in R$ . For example, if we set $R=\{-1,1\}$ , we get exactly the integer shifts for $G$ : Each shift by an integer $z\in\mathbb Z$ can be understood as a $|z|$ -fold execution of the shift $\tau_{\mathrm{sgn}(z)}$ . However, we can also choose $R=[-1,1]$ . Then we actually obtain for $G$ all displacements by arbitrary real numbers: Any displacement $\tau_s$ with $s\in\mathbb R$ arbitrary, can be understood as $\lceil|s|\rceil$ -fold of the displacement $\tau_r$ with $r=s/\lceil|s|\rceil\in[-1,1]$ .
- Similarly, you can also create a group by turning. For this we take as structure $X$ the unit circle $K=\{(x,y)\in\mathbb R^2\,|\,x^2+y^2=1\}$ together with the excellent point $\mathbf p$ . Let $\rho_\alpha$ be the rotation by the angle $\alpha\in\mathbb R$ (in radians). As above, one convinces oneself that the succession of $\rho_\alpha$ and $\rho_\beta$ yields exactly $\rho_{\alpha+\beta}$ ( $\alpha,\beta\in\mathbb R$ ). Again, we can consider the group $G$ generated by the rotations $\{\rho_\alpha \mid \alpha\in R\}$ (for a set $R\subseteq\mathbb R$ of admissible angles such that with $\alpha\in R$ also $-\alpha\in R$ ). For example, if we take $R=\{-2 \pi/n,2\pi/n\}$ , we get for $G$ exactly those rotations by a multiple of the angle $2\pi/n$ . These are exactly the orientation-preserving self-images of the regular $n$ -corner. But we could also choose $R=(-\pi,\pi)$ and in this way get for $G$ all rotations $\rho_\alpha$ around the origin.
- If we take as structure $X$ a deck of $n$ cards laid out face up on a table, we can consider as operations certain permissible rearrangements of these cards. If, for example, one chooses as permissible rearrangements the swaps of two adjacent cards each, these create a group: in fact, each of these rearrangements can be undone by simply applying it again. However, one also considers that any rearrangement of the cards can be combined from the pairwise swaps of two adjacent cards. This group of all permutations is called the fully symmetric group of degree $n$ .
There are many more such examples. Maybe you try to find some yourself. The exhibit “Have the courage” also hides a special group. This permutes and turns the nine tiles with the letters. In the following, we want to understand this group — and thus the exhibit — in more detail.

About the exhibit “Have the courage“

But which group exactly is hidden behind the exhibit? Let’s understand that better now. Given nine similar tiles arranged in a $3\times 3$ square, each of which we can rotate four, forming a small $2\times 2$ square at one corner. However, the individual parts are also tilted by $90^\circ$ each (see figure 1 below).

All other operations are now composed — as in the examples above — of these four rotations, i.e. our group of rearrangements is generated by the four rotations $x,y,z,w$ . If one performs each of these rotations four times in succession, one returns to the initial state, i.e. the relations $x^4=y^4=z^4=w^4=\mathrm{id}$ (the identical figure) apply. But can any conceivable arrangement of the nine parts also be achieved by performing the four turns one after the other? That is, can any rearrangement and subsequent twisting of the nine parts be combined from the rotations $x,y,z,w$ ?

This is the question we want to explore in the following. (Mathematically expressed: Which subgroup of the wreath product $C_4\wr S_9$ of the cyclic group with four elements, corresponding to the possible rotations of a tile, and the symmetric group on nine digits, corresponding to the possible permutations of the tiles, produce the rotations $x,y,z,w$ ?)

To do this, we number the tiles from $1$ to $9$ and first identify them with each other according to Figure 2 below:

So what does this identification mean and why is our chosen identification so well suited to the study of the exhibit? Now, the identification allows us to add to each permutation $\sigma\in S_9=\mathrm{Sym}(\{1,\ldots,9\})$ to associate a rearrangement of the exhibit by transferring the platelet $i$ into the platelet $\sigma(i)$ — according to the chosen identification of the platelets in Figure 2. In this way we thus obtain an embedding of the symmetric group $S_9$ to nine digits in the group of all rearrangements of our exhibit. In addition, let $t$ be the rearrangement that twists only the middle tile (number $5$ ) by $180^\circ$ (so that $t^2=\mathrm{id}$ is the identical rearrangement). Our chosen identification is so convenient because the generators $x,y,z,w$ can now be expressed very nicely using the chosen copy of $S_9$ and the rotation $t$ :

The rotation $x$ rotates the platelets $1,2,5,4$ cyclically and corresponds exactly to the $4$ -cycle $(1,2,4,5)$ of $S_9$ (because it is compatible with the chosen identification of the platelets; here we use the cycle notation for permutations). Similarly, we also obtain that exactly $w=(5,6,9,8)$ holds. With the other rotations $y$ and $x$ we have to be be more careful. For example, if we compare the $4$ cycle $(2,3,6,5)$ with the rotation $y$ , we see that the $2$ and $3$ platelets are mapped the same under both rearrangements, but the $5$ and $6$ platelets are rotated to the same place, but end up opposite in orientation by $180^\circ$ under each of the two rearrangements. Therefore, consider that $y=t^{-1}(2,3,6,5)t=t(2,3,6,5)t$ . In the same way, one also obtains that $z=t(4,5,8,7)t$ holds. All this is again summarised in the following figure 3:

From the considerations just given, it follows that the group of rearrangements $G$ , which is generated by $x,y,z,w$ , is a subgroup of the wrath product $\langle t\rangle\wr S_9$ . Here $S_9$ is the “copy” chosen according to the identification in Figure 2 and $\langle t\rangle\cong C_2$ is the group with two elements generated by $t$ .

But which subgroup do we get now exactly? To this end, we note that any rearrangement $g\in G$ that can be generated from $x,y,z,w$ can be uniquely written as a product $g=\sigma.r\in S_9\ltimes C_2^9$ (as an element of the semidirect product). Here $\sigma$ transfers each tile $i$ to the desired position $\sigma(i)$ and $r$ then rotates each individual tile so that it gets the desired orientation (i.e. no longer changes the position of the tiles). We call $\sigma$ the permutation part of $g$ and $r$ the rotation part.

First, we want to understand the permutation part of $G$ , i.e. the possible rearrangements we can generate from $x,y,z,w$ if we neglect the rotations of the individual platelets (i.e. we want to understand the quotient $\overline{G}$ of $G$ along the natural mapping $\langle t\rangle\wr S_9\to S_9$ ). We claim that we can combine all permutations of the nine tiles of $x,y,z,w$ that are possible at all (i.e. $\overline{G}=S_9$ ):

To do this, we calculate the expression $[\overline{x},\overline{y}]=\overline{xyx^{-1}y^{-1}}$ (the so-called commutator of the permutations $\overline{x}$ and $\overline{y}$ ): $\overline{xy}=(1,3,6,5,4)$ , $\overline{x^{-1}y^{-1}}=(1,4,6,3,2)$ , and thus

$\overline{xyx^{-1}y^{-1}}=(1,3,6,5,4)(1,4,6,3,2)=(1,2)(5,6).$

Through conjugation (i.e. shifting the four digits $1,2,5,6$ by means of precomposition with $\overline{g}^{-1}$ and composition with $\overline{g}$ for a suitable rearrangement $g\in G$ ), any permutation of the form $(a,b)(c,d)$ ( $a,b,c,d\in\{1,\ldots,9\}$ pairwise different) can now be obtained (i.e. of the same type of cycle). But this means that the entire conjugacy class of the element $(1,2)(5,6)$ under the symmetrical group on nine digits $S_9$ is contained in the group generated by the four base rotations $x,y,z,w$ . Thus, this must contain at least the alternating group $A_9$ generated by it (because this is simple). However, since each of the rotations $x,y,z,w$ is a cycle of even length, i.e. yields an odd permutation, the generated group must even be all $S_9$ . Thus, all conceivable permutations of the tiles from $x,y,z,w$ can be combined. So we only need to understand the possible rotational proportions of elements $g\in G$ .

We will now devote ourselves to this task: First, we observe that for all generators $x,y,z,w$ , the rotation fractions of the individual plates add up to zero (i.e. only an even number of plates are turned over by $180^\circ$ ). In fact, $x=(1,2,4,3)$ and $w=(5,6,9,8)$ — so these elements have no rotational components at all (i.e., in particular, zero $=$ just many platelets are re-rotated by $180^\circ$ ). For the elements $y,z$ we get: $y=t(2,3,6,5)t=(2,3,6,5)t^{(2,3,6,5)}t$ and $z=t(4,5,8,7)t=(4,5,8,7)t^{(4,5,8,7)}t$ (here $a^b=a^{-1}a$ means the element $b$ conjugated with $a$ ). Thus, at $y$ the $2$ and $5$ tiles and at $z$ the $5$ and $8$ tiles are re-rotated by $180^\circ$ (i.e. an even number).

Consider further that the condition that all rotations of the individual tiles sum to the identical rotation defines a subgroup $U$ of $C_2^9$ invariant under permutation of the “coordinates” (i.e., the tiles $1$ to $9$ ) (i.e., $u=(u_1,\ldots,u_9)\in U$ exactly when $u_1\cdots u_9=\mathrm{id}$ ). With this one calculates that then all rotational components of elements from $G$ must lie in $U$ (this follows from the invariance of the condition under permutation of the nine tiles and from the fact that the rotational components of the generators $x,y,z,w$ lie in $U$ ).

We now even claim that every rotation $u\in U$ lies in $G$ , i.e. can be combined from the generators $x,y,z,w$ . Thus $G=U\cdot S_9=U\rtimes S_9$ must then hold and we can check exactly whether a given rearrangement of the exhibit can be combined from the rotations $x,y,z,w$ by first “subtracting” the permutation part and then checking whether the remaining rotation part satisfies the above condition (i.e. lies in $U$ ).

So it remains to show that $U$ is a subgroup of $G$ . To do this, we calculate the expression $([x,y])^2=(xyx^{-1}y^{-1})^2$ (i.e. the square of the commutator of $x$ and $y$ ) in Figure 4 below:

The calculation shows that $g=([x,y])^2$ leaves all the tiles in place and flips exactly the $1,2$ and $5,6$ tiles by $180^\circ$ . So $g=([x,y])^2$ lies in the subgroup $U$ and is not the neutral element $\mathrm{id}$ , which does not change any platelet. However, from representation theory we know that the $S_9$ -module $U$ is irreducible, i.e. the subgroup generated invariant by $g$ under $S_9$ must be all $U$ . But with this we have shown that $\langle g^{S_9}\rangle=U\subseteq G$ holds (here $g^{S_9}$ is the set of conjugates of $g$ lower elements of $S_9$ ), which was to be shown. We have thus fully understood the group $G$ . It is therefore easy to check whether we can return a given arrangement of the exhibit to its original state.

The number of admissible (i.e. combinable out of $x,y,z,w$ ) arrangements is thus equal to the size of the group $G$ , i.e. $|G|=|U||S_9|=2^8\cdot 9!=92897280$ (here $n!=n\cdot(n-1)\cdots1$ is the factorial function). If we are very precise, we note that the letters $\mathrm{H}$ and $\mathrm{N}$ are point-symmetrical. So whether or not these two perform a $180^\circ$ rotation doesn’t matter. Therefore, there would then only be $|G|/2=46448640$ possible arrangements (because, if you “flip” one of the two letters, you must also flip the other, according to the condition on the elements of $U$ ).

But how do you solve the puzzle?

What is the maximum number of moves needed from a permissible arrangement of the exhibit to the initial state? This question is much more difficult to answer than the determination of the group $G$ generated by $x,y,z,w$ above. First, let us give a (much too rough) upper bound for this: Each element of the group $G$ can be written as a concatenation of the rotations $x,y,z,w$ and their inverse. Let us say that the “elementary operations” are exactly the rotations $x,x^2,x^3,y,y^2,y^3,z,z^2,z^3,w,w^2,w^3$ .

We now ask ourselves how many such elementary operations we have to perform at least one after the other in order to reach any element $g\in G$ .

We know that $|G|=2^8\cdot 9!$ holds (see above). With this we consider that at the latest after $(|G|-1)$ -many moves we can reach any permissible rearrangement $g\in G$ , so until we can read the words “Have the courage” again. However, this number is much much much too large. for comparison: A Rubik’s Cube can always be transformed into its initial state in at most $22$ moves.

Therefore, we now want to specify a lower bound that comes closer to reality: To do this, we consider how many permissible rearrangements we can obtain at most after performing exactly $n$ -many elementary operations ( $n\in\mathbb N$ ). Let $u_n$ be the number of these rearrangements. For $n=0$ we simply get $u_n=1$ , because we can, without doing anything, only produce the identical rearrangement. For $n=1$ we get $u_1=4\cdot 3$ , because this is exactly the number of elementary operations and each of them yields a different rearrangement. Now suppose we knew $u_n$ ( $n\geq 1$ ). Let us say that we have performed exactly $n$ elementary operations $x,x^2,x^3,y,y^2,y^3,z,z^2,z^3,w,w^2,w^3$ and that the last one was a multiple of $x$ . Then it makes no sense to apply a multiple of $x$ again, because this would give you a rearrangement that can already be achieved in $n$ or less moves. So it can be assumed that then in the $(n+1)$ -th move one of the elementary operations $y,y^2,y^3,z,z^2,z^3,w,w^2,w^3$ is performed. Therefore, we get that $u_{n+1}\leq 9u_n$ . Thus, for $n\geq 1$ and the number of all configurations $s_n$ achievable in $n$ or fewer moves, it follows that

$s_n\coloneqq\sum_{i=0}^n{u_n}\leq 1+12\cdot\sum_{i=0}^{n-1}{9^i}=1+12\frac{9^n-1}{9-1}=1+\frac{3}{2}(9^n-1).$

So what is the minimum number of moves needed to achieve each permissible rearrangement? Let $n\geq 1$ be the smallest number such that all elements $g\in G$ can be reached in at most $n$ moves. Then surely $s_n=|G|$ must hold, and thus according to our calculation above

$z_n=|G|\leq 1+\frac{3}{2}(9^n-1).$

This leads to $n\geq 9$ . That is much more realistic. But how big is the smallest integer $n$ for the needed moves really? Find out for yourself by trying out the exhibit. Maybe you want to write a small computer programme that solves the problem?

It makes sense to divide the problem into stages: First, rotate the $1$ plate (as $\mathrm{H}$ ) to the correct position (top left). Then one solves the smaller remaining sub-problem and so on.

Literature

[1] https://en.wikipedia.org/wiki/Symmetric_group

[2] https://en.wikipedia.org/wiki/Free_group

[3] https://en.wikipedia.org/wiki/Cayley_graph

[4] https://en.wikipedia.org/wiki/Rubik%27s_Cube

[5] https://en.wikipedia.org/wiki/Wreath_product