Have the courage

latexpage] Surely you’ve dealt with the Rubik’s Cube before, 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.

Figure 1: The “Have the courage” exhibit

And now … the mathematics of it:

Group theory is a mathematical discipline which deals exactly with such structures: Given a certain structure $X$ (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 is a set of permissible operations which transform $X$ into another state, so that two of these operations can be executed one after the other and there is a unique inverse operation for each operation which undoes it.

These operations on the structure $X$ now create 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 draw a point $\mathbf p$ in particular. We can now apply to this straight line a shift $\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 shift $\tau_r$ and $\tau_s$ one after the other is exactly the same as $\tau_{r+s}$. Therefore, $\tau_r$ can be uniquely reversed by applying $\tau_{-r}$. Thus a set $\tau_r\,|\,r\in R}$ of admissible shifts generates a group $G$ operating on the real straight line. Here we can choose the set $R\subseteq\mathbb R$ arbitrarily, so that with $r\in R$ also $-r\in R$ holds. 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 thought of as a $|z|$-fold execution of the shift $\tau_{\mathrm{sgn}(z)}$. Similarly, however, we can also choose $R=[-1,1]$. Then, in fact, we obtain for $G$ all shifts by arbitrary real numbers: Any shift $\tau_s$ with $s\in\mathbb R$ arbitrary, can be understood as $\lceil|s|\rceil$-fold of the shift $\tau_r$ with $r=s/\lceil|s|\rceil\in[-1,1]$.
  • In a similar way we can also generate a group by rotations. 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 distinguished point $\mathbf p$. Now let $\rho_\alpha$ be the rotation by the angle $\alpha\in\mathbb R$ (in radians). As above, we convince ourselves that the succession of $\rho_\alpha$ and $\rho_\beta$ gives exactly $\rho_{\alpha+\beta}$ ($\alpha,\beta\in\mathbb R$). Again, we can consider the group $G$ generated by the rotations ${\rho_\alpha\,|\,\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 for $R={-2 \pi/n,2\pi/n}$, we obtain for $G$ exactly those rotations by a multiple of the angle $2\pi/n$. These are exactly the orientation-preserving self-mappings of the regular $n$-corner. In the same way we could choose $R=(-\pi,\pi)$ and 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 admissible rearrangements of these cards. For example, if one chooses as admissible rearrangements the permutations of every two adjacent cards, these produce a group: in fact, any such rearrangement can be undone simply by applying it again. However, consider also that any rearrangement of cards can be combined from the pairwise swaps of two adjacent cards. This group of all permutations is called the full symmetric group of degree $n$.

There are many more such examples. Maybe you try to find some yourself. There is also a special group behind the exhibit “Have the courage”. This one permutes and rotates 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 is hidden behind the exhibit exactly? Let’s understand that better now. Given are nine similar platelets arranged in a $3\times 3$-square, and we can rotate four of each, forming a small $2\times 2$-square at one corner. However, in doing so, the individual pieces 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 executes 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 identity function) hold. But can also every conceivable arrangement of the nine parts be achieved by executing the four rotations 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$?

We will explore this question in the following. (In mathematical terms: which subgroup of the wreath product $C_4\wr S_9$ of the cyclic group with four elements, corresponding to the possible twists of a tile, and the symmetric group on nine digits, corresponding to the possible permutations of the tiles, generate the twists $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 for studying the exhibit? Well, the identification allows us to associate to each permutation $\sigma\in S_9=\mathrm{Sym}({1,\ldots,9})$ 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. Thus, in this way, we obtain an embedding of the symmetric group $S_9$ on nine digits in the group of all rearrangements of our exhibit. In addition, let $t$ be the rearrangement that twists only the middle platelet (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. For the other two rotations $y$ and $z$, however, we have to pay more attention. For example, if we compare the $4$ cycle $(2,3,6,5)$ with the rotation $y$, we see that the platelets $2$ and $3$ are mapped the same under both rearrangements, but the platelets $5$ and $6$ are rotated to the same place, but end up being oriented in opposite directions 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$. Similarly, one also obtains that $z=t(4,5,8,7)t$. All this is again summarized in the following figure 3:

Thus, from the considerations just made, it follows that the group $G$ of rearrangements generated by $x,y,z,w$ is a subgroup of the wreath 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 two-element group 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 written uniquely as a product $g=\sigma.r\in S_9\ltimes C_2^9$ (as an element of the semidirect product). Here $\sigma$ transfers each platelet $i$ to the desired location $\sigma(i)$ and $r$ then rotates each platelet so that it gets the desired orientation (so it does not change the position of the platelets anymore). We call $\sigma$ the permutation part of $g$ and $r$ the rotation part.

First, we want to understand the permutation part of $G$, that is, 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 platelets of $x,y,z,w$ that are possible at all (i.e., $\overline{G}=S_9$):

To do this, we compute 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)$, und somit $$\overline{xyx^{-1}y^{-1}}=(1,3,6,5,4)(1,4,6,3,2)=(1,2)(5,6). $$

Now, by conjugation (i.e., shifting the four digits $1,2,5,6$ using precomposition with $\overline{g}^{-1}$ and Knachcomposition 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 distinct) can be obtained (i.e. i.e., of the same cylotype). But this means that the entire conjugacy class of the element $(1,2)(5,6)$ under the symmetric 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). But since each of the rotations $x,y,z,w$ is a cycle of even length, thus yielding an odd permutation, the generated group must even be all $S_9$. Thus, all conceivable permutations of the tiles of $x,y,z,w$ can be combined. So we only need to understand the possible rotational proportions of elements $g\in G$.

We now turn our attention to this task: To do this, we first observe that for all generators $x,y,z,w$, the rotational fractions of each tile sum to zero (i.e., only just many tiles are flipped by $180^\circ$). In fact, $x=(1,2,4,3)$ and $w=(5,6,9,8)$ — so these elements have no rotation 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}ba$ means the element $b$ conjugate with $a$). Thus, for $y$ the platelets $2$ and $5$ and for $z$ the platelets $5$ and $8$ are post-rotated by $180^\circ$ (i.e., even many).

Now consider further that the condition that all rotations of the individual platelets sum to the identical rotation defines a subgroup $U$ of $C_2^9$ invariant under permutation of the “coodinates” (i.e., the platelets $1$ to $9$) (i.e., $u=(u_1,\ldots,u_9)\in U$ exactly when $u_1\cdots u_9=\mathrm{id}$). Using this, we calculate 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$, so can be combined from the generators $x,y,z,w$. Thus $G=U.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 tiles $1,2$ and $5,6$ 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, we know from representation theory 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. Thus, we have fully understood the group $G$. Thus, it is easy to verify that we can return a given arrangement of the exhibit to its initial state.

The number of admissible (i.e., combinable from $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$ (where $n!=n\cdot(n-1)\cdots1$ is the factorial function). If we take it very carefully, we still note that the letters $\mathrm{H}$ and $\mathrm{N}$ are point symmetric. So whether these two perform a $180^\circ$ rotation or not, it doesn’t matter. Therefore, there would then be only $|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 now?

What is the maximum number of moves needed from an admissible arrangement of the exhibit to the initial state? This question is much harder to answer than determining the group $G$ generated by $x,y,z,w$ above. First, let us give a (much too rough) upper bound for it: Each element of the group $G$ can be written as a concatenation of the rotations $x,y,z,w$ and their inverses. 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 wonder how many such elementary operations we must perform at least in succession to reach any element $g\in G$.

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

Therefore we want to give a lower bound which is closer to reality: We consider how many permissible rearrangements we can get after 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, just generate 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 that would give us a rearrangement that can be achieved in $n$ or fewer moves already. 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. Thus, we obtain 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$. This is already much more realistic. But how big is the smallest number $n$ of required moves really? Find out for yourself by experimenting with the exhibit. Maybe you want to write a small computer program that solves the problem?

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


Literature

[1] https://de.wikipedia.org/wiki/Symmetrische_Gruppe

[2] https://de.wikipedia.org/wiki/Freie_Gruppe

[3] https://de.wikipedia.org/wiki/Cayleygraph

[4] https://de.wikipedia.org/wiki/Zauberwürfel

[5] https://de.wikipedia.org/wiki/Kranzprodukt