Solving a "twisty puzzle" on $S_{20}$

Question

I'm trying to solve a twisty puzzle that permutes the integers 1 thru 20 according to the following rules:

• $R = \begin{pmatrix} 1 & 2 & \cdots & 19 & 20\\ 20 & 1 & \cdots & 18 & 19 \end{pmatrix},\quad$ a "slide" to the right

• $L = R^{-1} = \begin{pmatrix} 1 & 2 & \cdots & 19 & 20\\ 2 & 3 & \cdots & 20 & 1 \end{pmatrix},\quad$ a "slide" to the left

• $T = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & \cdots & 20\\ 4 & 3 & 2 & 1& 5 & \cdots & 20 \end{pmatrix},\quad$ a "twist" of the first four elements

After fidgeting around with it a bit, I quickly realized that if $n$ is at the front, and $n+1$ is in the third position, then the operation $RTRTLTL$ (from right to left, as operators) will leave $n$ fixed, and move $n+1$ after it as desired.

Repeating this procedure numerous times, it's not hard to solve most of the puzzle. However things get tricky when you get to the last 4 integers than need sorting. In particular, I'm currently stuck with only 1 and 20 swapped, and everything else in-order.

Does anyone have any suggestions about how one might create commutators (or other operations) to swap a single pair of adjacent integers?

And, more generally, how does this puzzle change with adjustments to the length of integers, or the size of the "twist"? More precisely, if we are working in $S_n$, and the "twist" operation reverses the first $k$ integers, with $k < n$, what can we say about the puzzles various states? Is this enough to generate the entire group $S_n$? Does the answer depend on the values of $n$ and $k$ explicitly? Is there something particularly interesting about $n=20$, or was this just a design choice by the manufacturer of the puzzle?

Answer 1

$(TRTLTR)^{17}=(1,2)$, an adjacent transposition (product from right to left). Together with the cycle $R$, it generates $S_{20}$. So it's always possible to solve the puzzle.

• The other adjacent transpositions: $(i,i+1)=L^{i-1}(1,2)R^{i-1}$ for $1<i<20$ and $(20,1)=R(1,2)L$.
• The transpositions $(1,i)$ are built as follows: $(1,3)=(1,2)(2,3)(1,2)$, then $(1,4)=(1,3)(3,4)(1,3)$, etc.
• The general transposition $(i,j)=(1,i)(1,j)(1,i)$.
• Now that all transpositions are built, a general cycle $(a_1,a_2,\dots,a_p)=(a_1,a_2)(a_2,a_3)\cdots(a_{p-1},a_p)$.
• Now that all cycles are built, use the cycle decomposition of any permutation.

The procedure is systematic, but does not necessarily produce the shortest sequence of products of $L, T$ and $R$ to achieve a given permutation.

Answer 2

Commutators are always even permutations. Therefore the odd permutation consisting of a single transposition is not possible using only commutators.

In this puzzle, the $T$ generator is an even permutation. To get an odd permutation you need to apply an odd number of $R$ and $L$ generators. What this means in practice is that when you only have the state $(2,1,3,4,5,6,...,20)$, in which 18 pieces are correct and two pieces need to be swapped, you should apply $L$ to get $(1,3,4,5,6,...,20,2)$ and really think of it as if piece $1$ is correct and all the others are incorrect relative to that. What you have left now is a 19-cycle, which is an even permutation. If you solve the rest of the pieces without involving piece 1 in a $T$ move, i.e. solve the rest of the loop relative to piece 1 which you consider correct, then you will always end up with an even permutation of pieces, so won't get a single transposition any more.

An easy way to solve the puzzle is by using the move sequence $TLTRTLTR$ (left to right notation). This rearranges the first 5 pieces from $(a,b,c,d,e,...)$ to $(b,c,d,e,a,...)$. The first piece has jumped over the next four pieces. Follow this by $LLLL$ to bring that piece to the first position again, and repeat. In this way you can jump one piece around the loop until it is in the correct place relative to the rest.
In particular, $(TLTRTLTLLL)^5$ jumps the first piece over 20 others, i.e. it goes all the way around the loop and then one extra place. Therefore $(TLTRTLTLLL)^5 R$ is a single transposition of the first two pieces.