Before we go deeper into Conway’s M(13) puzzle, let us consider a more commonly known sliding puzzle: the 15-puzzle. A heated discussion went on a couple of years ago at sci-physics-research, starting with this message. Lubos Motl argued that group-theory is sufficient to analyze the problem and that there is no reason to resort to groupoids (‘The human(oids) who like groupoids…’ and other goodies, in pre-blog but vintage Motl-speak) whereas ‘Jason’ defended his viewpoint that a groupoid is the natural symmetry for this puzzle.
I’m mostly with Lubos on this. All relevant calculations are done in the symmetric group $S_{16} $ and (easy) grouptheoretic results such as the distinction between even and odd permutations or the generation of the alternating groups really crack the puzzle. At the same time, if one wants to present this example in class, one has to be pretty careful to avoid confusion between permutations encoding positions and those corresponding to slide-moves. In making such a careful analysis, one is bound to come up with a structure which isn’t a group, but is precisely what some people prefer to call a groupoid (if not a 2-group…).
Groupoids are no recent invention but date back to 1926 when Heinrich Brandt defined what we now know as the ‘Brandt groupoid’ in his study of _noncommutative number theory_. He was studying central simple algebras (the noncommutative counterpart of number fields) in which there usually is not a unique ‘ring of integers’ (in noncommutative parlance, a maximal order) and fractional ideals have a left- and a right- maximal order associated to it, leading naturally to left- and right- unit elements and the notion of a groupoid.
The algebraic notion of a groupoid is a set G with a partial multiplication and an everywhere defined inverse satisfying associativity $a \ast (b \ast c) = (a \ast b) \ast c $ whenever the terms are defined. Further, whenever $ a \ast b $ is defined one has $ a^{-1} \ast a \ast b = b $ and $a \ast b \ast b^{-1} = a $ and finally all $a^{-1} \ast a $ and $ a \ast a^{-1} $ are defined (but may be different elements). The categorical definition of a groupoid is even simpler : it is a category in which every morphism is an isomorphism. Both notions are equivalent.
Recall that the 15-puzzle is a 4×4 slide-puzzle with initial configuration with the hole at the right bottom square (see left) and one can slide the hole one place at a time in vertical or horizontal direction. For example, if one slides the hole along the path 12-11-7-6-2 one ends up with the situation on the right
$\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\
\hline 5 & 6 & 7 & 8 \\ \hline 9 & 10 & 11 & 12 \\ \hline 13 & 14 & 15 & \\ \hline \end{array} $ (initial position)
$\begin{array}{|c|c|c|c|} \hline 1 & & 3 & 4 \\
\hline 5 & 2 & 6 & 8 \\ \hline 9 & 10 & 7 & 11 \\ \hline 13 & 14 & 15 & 12 \\ \hline \end{array} $ (position after 12-11-7-6-2)
The mathematical aim is to determine the allowed positions, that is those which can be reached from the initial position by making legal slide moves. The puzzle aim is to return to the initial position starting from an allowed position. We will determine the number of allowed positions and why they are the elements of a groupoid.
We dont want to draw arrays all the time so we need a way to encode a position. Giving the hole label 16 we can record a position by writing down the permutation on 16 letters describing by which label in the given position, the label of the initial position is replaced. For example, the situation on the right arises by leaving 1 to position 1, 2 is replaced by 16, 3,4 and 5 are left in their position but 6 is replaced by 2 and so on. So, we can encode this position by the permutation
$\sigma = (2,16,12,11,7,6) $ and conversely, given such a permutation we can fill in the entire position encoded by it. We will denote the array or position corresponding to a partition $\tau \in S_{16} $ by the boxed symbol $\boxed{\tau} $.
Next, we turn to slide-moves. A basic move interchanges the hole (label 16) with a square labeled i (if i is a horizontal or vertical neighbor of the hole in the position) so can be represented by the transposition $~(16,i) $. We can iterate this procedure, a legal move from a position $\boxed{\tau} $ will be a succession of basic-moves written from right to left as is usual in composing permutations
$~(16,i_k) \cdots (16,i_2)(16,i_1) $
where legality implies that at each step the label $i_{m+1} $ must be a vertical or horizontal neighbor of the hole in the position reached from $\boxed{\tau} $ after applying the move $~(16,i_m)(16,i_{m-1}) \cdots (16,i_2)(16,i_1) $. Hence, we’d better have a method to compute the position we obtain from a given position by applying a legal sequence of slide-moves. The rule is : multiply the slide-move-permutation with the position-permutation in the group $S_{16} $ to get the code for the obtained position. In symbols
$~(16,i_k) \cdots (16,i_2)(16,i_1) \boxed{\tau} = \boxed{(16,i_k) \cdots (16,i_2)(16,i_1) \tau} $
For example, the initial position corresponds to the identity permutation, that is, is $\boxed{()} $ and applying to it the legal seuence of slides moved along the path 12-11-7-6-2 as before we get the position with code
$~(16,2)(16,6)(16,7)(16,11)(16,12) \boxed{()} = \boxed{(16,2)(16,6)(16,7)(16,11)(16,12)} = \boxed{(16,12,11,7,6,2)} $
which is indeed the code of the position obtained above on the right. Right, the basic ingredient to have full understanding of this puzzle are hence the combination of an allowed position together with a legal move-sequence starting from it. Therefore, we will take as our elements all possible combinations $\sigma \boxed{\tau} $ with $\sigma,\tau \in S_{12} $ where $\tau $ is the code of a reachable position and $\sigma = (16,i_l) \cdots (16,i_1) $ is a legal move from that position.
On this set of elements we only have a partially defined composition rule, for we can only make sense of the composition of moves
$\sigma_1 \boxed{\tau_1} \ast \sigma_2 \boxed{\tau_2} = \sigma_1 \sigma_2 \boxed{\tau_2} $
provided $\tau_1 $ is the code of the position reached from $\boxed{\tau_2} $ after applying the move-sequence $\sigma_2 $, that is, the multiplication above is defined if and only if
$\tau_1 = \sigma_2 \tau_2 $ in $S_{16} $
All conditions of the algebraic notion of a groupoid are satisfied. For example, every element has an inverse
$~(\sigma \boxed{\tau})^{-1} = \sigma^{-1} \boxed{\omega} $ where $\omega = \sigma \tau $ in $S_{16} $
and it is easy to check that all conditions are indeed satisfied. In the categorical definition, the groupoid is the category having as the objects the reachable positions, and morphisms $\boxed{\tau_1} \rightarrow \boxed{\tau_2} $ are of the form $\sigma_1 \boxed{\tau_1} $ such that $\sigma_1 \tau_1 = \tau_2 $ (hence, all morphisms are isomorphisms and there is just one morphism between two objects, namely corresponding to $\sigma_1 = \tau_2 \tau_1^{-1} \in S_{16} $. For example, each object $\boxed{\tau} $ also has an identity morphism $~() \boxed{\tau} $ and again all categorical requirements are met.
This groupoid we will call the the 15-puzzle groupoid and next time we will determine that it has exactly $\frac{1}{2} 16! $ objects.
One Comment