How do I write a formal proof related to this frog jumping puzzle.

Question

There is a fairly well known puzzle about moving frogs that can be seen here. I found an interesting property about these puzzles and am certainly not the first to notice it. I can state this property informally, but I don't know how to formally state or prove it.

For simplicity suppose there are $3$ of each type of frog, and designate the frog/empty space pattern in any configuration $p$ as going from $p[0]$ to $p[6]$ with $p[i]$ being a frog of one type or the other or an empty space.

Designate the move from one pattern to the next as $P_k \to P_{k+1}$. Consider now $P_{k+1} \to P_{k}$. This is well defined but is not a legal move, because it causes a frog to move backwards. We will define the transformation $R(P)$, which reflects each frog or empty space's position with $p[k]$ swapping positions with $p[6-k]$. If follows that $R(P_{k+1}) \to R(P_{k})$ is well defined and is also a legal move.

Suppose $P_{0} \to P_{1} \to \cdots \to P_{n}$ is a solution to the problem. Then $R(P_{n}) \to R(P_{n-1}) \to \cdots \to R(P_0)$ is a legal sequence and since $R(P(n)) = P_0$ and $R(P_0) = P_n$, this is also a solution. In the cases I checked, the two solutions turned out to be identical, giving $P_{n-k} = R(P_k)$. This can be used to complete the puzzle if it is found that for some $i$ such that, $P_i = R(P_i)$ or $P_{i+1} = R(P_i)$. That would mean that the puzzle is half-complete with an odd number of positions in the first case and an even number in the second. For each position $k$ after the center, set $P_k$ to $R(P_{n-k})$

I am hoping you can make sense of what I said. and can provide a formal method of stating it.

As an afterthought I will mention two other types of puzzle where symmetry operations apply.

There are a number of river crossing problems where doing the moves in the reverse order gives a solution.

Peg solitaire puzzles have an interesting symmetry. If P is position of the pegs, denote by C(P) as the complement, turning holes with pegs into empty holes and putting pegs into the empty holes. If X is the initial position and Y is the final position, the jumps done in reverse order will transform C(Y) into C(X). In particular, if you start with a single empty hole and end up with a single peg in that hole, then the moves done in reverse order will produce the same result. This is not that difficult to prove. It uses the fact that the 3 holes involved in a jump are complemented by the jump.

Answer 1

One convenient way of formally representing "moves" is to consider them as permutations acting on the functions that represent configurations. As you have specified in your question, a configuration of frogs can be represented by a function $\ P:\{0,1,2,\dots,6\}\rightarrow\{-1,0,1\}\ \big($or, more generally, $\ P:\{0,1,2,\dots,n\}\rightarrow\{-1,0,1\}\ \big)$, where $\ {-1}\ $ represents a left-moving frog on a space, $\ 1\ $ a right moving frog, and $\ 0\ $ an empty space.

A permutation on $\ \{0,1,2,\dots,6\}\ $ is a bijective function $\ \Pi:\{0,1,2,\dots,6\}\rightarrow$$\{0,1,2,\dots,6\}\ $ of that set onto itself, and the action of $\ \Pi\ $ operating on a configuration $\ P\ $ can be defined as the operation which transforms $\ P\ $ to $\ \Pi P\ $, defined by $$ \Pi P(i)=P\big(\Pi(i)\big)\ . $$ That is, $\ \Pi P\ $ is just the composition, $\ P\circ\Pi\ $, of $\ P\ $ with $\ \Pi\ $.

The reflection $\ R\ $ is just the permutation given by the table $$ R=\pmatrix{0&1&2&3&4&5&6\\6&5&4&3&2&1&0}\ , $$ one of the common ways of representing permutations, each number in the bottom row being the image under the permutation of the number in the same column of the top row. The result, $\ RP\ $, of the permutation $\ R\ $ acting on the configuration $\ P\ $ is exactly the same as the result of the transformation that you have defined as $\ P\rightarrow R(P)\ $ in your question.

The legal moves you can make on a position can be represented by a special type of permutation, called a transposition, which merely swaps the contents of two spaces. A general transposition is a permutation $\ \Pi\ $ for which $\ \Pi(i)=i\ $ for all integers in its domain except two, $\ j\ $ and $\ k\ $, with $\ j\ne k\ $, $\ \Pi(j)=k\ $, and $\ \Pi(k)=j\ $. A shorthand notation for representing such a permutation is $\ \big(j\ k\big)\ $, in which the two integers that get swapped are listed between parentheses.

The legal moves in the game that can be carried out on a particular configuration, $\ P\ $, of the game can be represented by any of four different types of transposition:

• $\ \big(i\ \ i+1\big)\ $, where $\ P(i)=1\ $ and $\ P(i+1)=0\ $. This represents a move in which a right-moving frog moves from the square $\ i\ $ to the empty square $\ i+1\ $;
• $\ \big(i\ \ i+1\big)\ $, where $\ P(i)=0\ $ and $\ P(i+1)={-1}\ $. This represents a move in which a left-moving frog moves from the square $\ i+1\ $ to the empty square $\ i\ $;
• $\ \big(i\ \ i+2\big)\ $, where $\ P(i)=1\ $, $\ P(i+1)\ne0\ $ and $\ P(i+2)=0\ $. This represents a move in which a right-moving frog on square $\ i\ $ jumps over a frog on the square $\ i+1\ $ to land on the empty square $\ i+2\ $; or
• $\ \big(i\ \ i+2\big)\ $, where $\ P(i)=0\ $, $\ P(i+1)\ne0\ $ and $\ P(i+2)=-1\ $. This represents a move in which a left-moving frog on square $\ i+2\ $ jumps over a frog on the square $\ i+1\ $ to land on the empty square $\ i\ $.

If $\ M\ $ is a legal move on the configuration $\ P\ $, transforming it into the position $\ MP\ $, then it's not difficult to show (although doing it does require quite a bit of tedious case work) that $\ RMR\ $ is a legal move on the configuration $\ RMP\ $, transforming it into the configuration $\ RP\ $.

To illustrate the procedure, I'll just carry it out for the first type of legal move, $\ M=\big(i\ \ i+1\big)\ $, which I suppose to be legal on the configuration $\ P\ $ with $\ P(i)=1\ $ and $\ P(i+1)=0\ $. Then $\ RMR\ $ is the permutation $\ \big(j\ \ j+1\big)\ $, where $\ j=$$5-i=$$R(i+1)\ \big($and $\ j+1=$$6-i=$$R(i)\ \big)$. Now $\ RMP(j)=$$MP\big(R(j)\big)=$$P\big(M(6-j)\big)=$$P\big(M(i+1)\big)=$$P(i)=1\ $, and $\ RMP(j+1)=$$MP\big(R(j+1)\big)=$$P\big(M(5-j)\big)=$$P\big(M(i)\big)=$$P(i+1)=0\ $. Thus, $\ RMR=$$\big(j\ \ j+1\big)\ $ satisfies the conditions of a legal move on the configuration $\ RMP\ $.

Answer 2

The frog puzzle solution does indeed have the symmetry you noticed, but I think it is a bit more subtle than that.

Consider these three kinds of transformations you might do to a solution:

1. Reflection, $R$. This is applying what you call $R$ to all states in a solution.
2. Time reversal, $T$. This reverses the order of the states in a solution, i.e. maps $P_k$ to $P_{n-k}$.
3. Colour reversal, $C$. This simply changes the colours of all the frogs.

All three of these transformations changes the starting state of a solution in the same way, resulting in a state where the frogs have the wrong starting colours. However, if you pick any two of these transformations and apply them (in any order) then you get the correct colours and therefore you still have a valid solution, which may be the same solution you started with or a different one. Note that these transformations all commute, i.e. it does not matter which order you apply them in (so $R\circ T=T\circ R$, $R\circ C=C\circ R$, and $C\circ T=T\circ C$).

If $s_1$ is a solution, then so are $s_2=R(T(s_1))$, $s_3=R(C(s_1))$, and $s_4=C(T(s_1))$. It is easy to see that $s_1$ and $s_3$ must be different because the first move is going in the opposite direction. For the same reason $s_2$ must differ from $s_4$ (because $s_2=R(C(s_4))$). Much less obvious is that $s_1$ and $s_4$ must be different, but you can show this by looking at what happens at the midway point of the solution.

The frog puzzle with just a single blank space is very constrained. So constrained in fact that it does not have four distinct solutions. This leaves only one possibility: $s_1=s_2$ and $s_3=s_4$, and the solutions have $RT$ symmetry, i.e. $s_1=RT(s_1)$ and $s_3=RT(s_3)$, the symmetry you found.

On the frog puzzle with more than one blank space there are many more solutions, and then there is no guarantee that there is some solution with this $RT$ symmetry, though there may well be. On the frog puzzle with unequal numbers of frogs of each colour you don't have the $C$ colour-swap transformation so only the $RT$ symmetry is even possible, but here too there can be multiple solutions and I'm not sure if there is always one with that $RT$ symmetry.