Six Frogs - Puzzle (order reversal using special transpositions)

I had come across a puzzle:

The six educated frogs in the illustration are trained to reverse their order, so that their numbers shall read 6, 5, 4, 3, 2, 1, with the blank square in its present position. They can jump to the next square (if vacant) or leap over one frog to the next square beyond (if vacant), just as we move in the game of draughts, and can go backwards or forwards at pleasure.

Can you show how they perform their feat in the fewest possible moves?

It is quite easy, so when you have done it add a seventh frog to the right and try again. Then add more frogs until you are able to give the shortest solution for any number. For it can always be done, with that single vacant square, no matter how many frogs there are.

---

Answer: Move the frogs in the following order: 2, 4, 6, 5, 3, 1 (repeat these moves in the same order twice more), 2, 4, 6. This is a solution in twenty-one moves - the fewest possible.

If $n$, the number of frogs, be even, we require $\frac{n^2+n}{2}$ moves, of which $\frac{n^2-n}{2}$ will be leaps and $n$ simple moves.

If $n$ be odd, we shall need $\frac{n^2+3n}{2}-4$ moves, of which $\frac{n^2-n}{2}$ will be leaps and $2n-4$ simple moves.

In the even cases write, for the moves, all the even numbers in ascending order and the odd numbers in descending order. This series must be repeated $\frac{1}{2}n$ times and followed by the even numbers in ascending order once only. Thus the solution for 14 frogs will be (2, 4, 6, 8, 10, 12, 14, 13, 11, 9, 7, 5, 3, 1) repeated 7 times and followed by 2, 4, 6, 8, 10, 12, 14 = 105 moves.

In the odd cases, write the even numbers in ascending order and the odd numbers in descending order, repeat this series $\frac{1}{2}(n-1)$ times, follow with the even numbers in ascending order (omitting $n-1$), the odd numbers in descending order (omitting 1), and conclude with all the numbers (odd and even) in their natural order (omitting 1 and n). Thus for 11 frogs: (2, 4, 6, 8, 10, 11, 9, 7, 5, 3, 1) repeated 5 times, 2, 4, 6, 8, 11, 9, 7, 5, 3, and 2, 3, 4, 5, 6, 7, 8, 9, 10 = 73 moves.

(source)

which I had tried to solve but could not find the reasoning behind the moves used in the solution could anybody tell how to handle this type of puzzles without hit and trial?

The answer given is incorrect. The number of moves required to solve the puzzle should be this sequence, given by $(n^2+n-2)/2$ (where $n=\#\text{ of frogs}$).

Let's write the formation of the frogs as a string of numbers $ 0$ through $ n$, denoting the empty space by $ 0$. With this notation, we can see that each turn is defined by swapping the $ 0$ with the number one or two spaces to the left or right, corresponding to a frog on the left or right hopping or leaping to the right or left, respectively. Since we'll be focusing on the $ 0$, it will be easiest to say that the $ 0$ is leaping to the left when a frog is leaping to the right, and analagously for the other cases.

Now, for aesthetics, we can consider the formations as vertices of a layered tree, each layer of the tree corresponding to a turn of the frog moving game. We put a directed edge from formation $ a$ (in layer $ i$) to formation $ b$ (in layer $ i+1$) if a legal move takes us from $ a$ to $ b$. Viewed in this way we can consider the puzzle as a shortest path problem from $ 0123\ldots n$ to $ n\ldots 3210$ (or to $ n\ldots 3201$, $ n\ldots 3021$, $ n\ldots 0321$, etc). Since we are interested only in shortest paths, the layers of the tree will be disjoint, as moving to an in-neighbor would imply we could have gotten there in fewer moves.

The Even Case.

I find the even case a bit easier to visualize, so let's start with that. Here is what the puzzle looks like with $ 4$ frogs.

You can see there are several solutions, highlighted in red, with the shortest one bolded. Let's zoom into these paths and walk through them.

Every solution follows the same pattern. First, the $ 0$ is moved all the way to the right, then reverses direction. We don't want to undo our previous move, so there is only one one available option - if we leaped right, we need to hop left, and vice versa. When we get $ 0$ back to the leftmost position, we reverse direction again. This process repeats until all the numbers are in order. (See: "Why does this work?") The fastest way to do this is highlighted in the red path - every move to the right is a leap, and there are exactly two hops to the left.

If we say that moving $ 0$ all the way to the right, then all the way back to the left constitutes a "round," then each round takes $ n/2$ leaps to the right + $ 1$ hop to the left + $ (n-2)/2$ leaps to the left + $ 1$ hop to the left. That's $ n+1$ total moves, $ 2$ hops and $ n-1$ leaps. Since each round moves the biggest number to the left twice and the smallest number to the right twice, we only need to do this $ n/2$ times to get everything in order. Also, we can skip the last step (which would only serve to put $0$ on the far left), so the even case requires $$ \frac{n(n+1)}{2}-1 =\frac{n^2+n-2}{2} \text{ moves}$$ with $$\frac{n(n-1)}{2}\text{ leaps}$$ and thus $$n-1\text{ hops.}$$

The Odd Case.

For $5$-frogs, the full diagram is too big, but we can look at its solutions.

Here is where we diverge from the answer given. We can do it in $ 14$ moves, $ 2$ less than $ (5^2+3\times 5)/2-4=16$.

We use essentially the same strategy here as in the even solutions. Let's write out the algorithm explicitly. The starting formation is $ 0123\ldots n$ and the starting direction is $ d=1$. Every turn, check first if $ 0$ is at position $ 1$ or $ n-1$. If it's at position $ p_0= 1$, let the $ 0$ hop left to position $ 0$ and set $ d=1$. If it's at position $ p_0= n-1$, have the $ 0$ hop right to position $ n$ and set $ d=-1$. In any other position $p_0$, the $ 0$ leaps to position $ p_0+2d$. We continue in this manner until the frogs are in the formation $ n\ldots 3201$.

Again we can see that each round has $n+1$ moves, $n-1$ leaps and $2$ hops (now in opposite directions). After completing $ k$ rounds, there are $ 2k-1$ numbers to the right of $ n$. If we do this $ (n-1)/2$ times, we have $ n-2$ numbers to the right of $ n$. In this situation, we only need to complete a 'half round' to finish - that is, once we get $ 0$ back to position $ n-1$, everything will be complete. That's $ (n-1)/2$ leaps, so we have a total of $$\left(\frac{n-1}{2}\right)(n+1)+\frac{n-1}{2}=\frac{n^2+n-2}{2} \text{ moves, }$$ which breaks down to $$\left(\frac{n-1}{2}\right)(n-1)+\frac{n-1}{2}=\frac{n(n-1)}{2} \text{ leaps }$$ and $$2\left(\frac{n-1}{2}\right)=n-1 \text{ hops.}$$

Why does this work?

Luckily we can understand our solution using some permutation theory. Let's prove it works for the odd case. Taking $0$ from left to right induces the permutation $$(0,n,n-1,n-3,n-5,n-7,\ldots,8,6,4,2)$$ in $\text{Sym}(\{0,\ldots,n\})$. Taking it from right to left induces the permutation $$(0,1,3,5,7,9,\ldots,n-4,n-2,n).$$ Multiplying these permutations, we get $$\sigma:=(1, 3, 5, 7, 9, 11,\ldots, n,n-1,\ldots,10,8,6, 4, 2).$$ So if we let $\sigma=(\sigma_1,\ldots,\sigma_{n})$, then we have that $$\sigma_k=\left\{\begin{array}{lcl}2k-1&:&k=1,\ldots,\frac{n+1}{2}\\ 2 (n - k + 1) &:&k=\frac{n+1}{2}+1,\ldots,n\end{array}\right.$$ where the indices are taken mod $n$.

Let $m=(n-1)/2$. We have, in general, that in cycle notation we can write $$(i_1,i_2,i_3,\ldots,i_c)^{m}=(i_{1+m},i_{1+2m},i_{1+2m},\ldots,i_{1+cm}),$$ where the indices are taken modulo $c$. From this we obtain $$\begin{eqnarray*}\sigma^{m}&=&(1, 3, 5, 7, \ldots, 2m+1,2m,\ldots,8,6, 4, 2)^{m}\\&=&(2,n-2,4,n-4,\ldots,m+1,m,\ldots,3,n-1,1,n).\end{eqnarray*}$$ Applying this permutation to $0,\ldots,n$ yields the formation $$0,n-1,n,n-3,n-2,n-4,n-3,\ldots,5,2,3,1.$$ So now, we can see that we just need to leap $n$ to the left, then $n-2$, then $n-3$, etc. until we reach $n,n-1,n-2,\ldots,3,2,0,1$.

The even case is proven identically.

How do we know this is the smallest possible number?

Every move can at most reverse the order of $2$ frogs. We must put frog $n$ to the left of all $n-1$ of the other frogs, so that is at least $n$ leaps right there. This does not modify the order of the other frogs, so to move frog $n-1$ to be to the left of the $n-2$ remaining frogs, we will need at least $n-2$ leaps. Continuing in this fashion, we need at minimum $$\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}$$ leaps. However, discussed above, we need $1$ hop each for frogs $2$ to $n$ to change direction, so we need at least $$\frac{n(n-1)}{2}+n-1=\frac{n^2+n-2}{2}$$ moves. Thus our construction is of minimal length.