Swapping Monkeys

(This problem should be familiar with those who know group theory and know the terminology in Thomas's answer. However, the proof regarding odd/even parity of permutations can be a little technical. This is a non-technical presentation and includes the most intuitive proof of parity that I know of.)

First, let's consider the problem with 3 monkeys. Here is a chart of every possibility. If one sequence can reach another by a single swap, they are connected with a line.

By swapping, you can only flip between the bottom and top rows.

Move 1 (on bottom, move number is odd) -> Move 2 (on top, move number is even) -> Move 3 (on bottom, move number is odd) -> etc.

That means any sequence on the top row is reachable by an even number of moves and any sequence on the bottom or is reachable by an odd number of moves.

The same principle applies to this kind of operation (called a permutation) in general - if a sequence can be reached by an even number of moves, it can't be reached by an odd number of moves, and vice versa.

The general explanation is a little more involved, but below.

---

Write you starting sequence ABCDE, and then below write your first swap. Draw curves connecting each pair of letters, being careful so that any intersection only happens between two curves at one time. Keep going like this for each step, writing ABCDE on top and your new sequence on the bottom.

Note something very important: between each step, you can only add or subtract an odd number of intersections in one move . (See an example below where ABCDE gets changed to DBCAE.)

This is because between the two letters that get swapped exactly 1 intersection is added or removed, and then any curves in between the swap overlap at exactly 2 intersections, so any extra points added or subtracted must be done 2 at a time; this results in an odd intersection change number like $1 + 2 + 2 - 2 + 2 = 5 .$

Since the sequence starts with an even number of intersections (0) each step of adding or subtracting an odd number of intersections swaps the number of intersections between odd and even.

(move 0) even number of intersections -> (move 1) odd number of intersections -> (move 2) even number of intersections -> (move 3) odd etc.

This means if we have a particular permutation where the final picture has an odd number of intersections, it will take an odd number of moves to get there. If we have a picture with an even number of intersections, it will take an even number of moves to get there.

In the case of our problem, we have a solution with an even number of intersections, so any solution at all will require an even number of moves.

The two examples provided show that the permutation (1,2,3,4,5) $\rightarrow$ (5,4,3,2,1) is pair .

The sign of a permutation $\sigma$ $($ denoted $\epsilon(\sigma))$ is defined as

$\displaystyle \epsilon(\sigma) = (-1)^{\text{inv}(\sigma)},$

where $\text{inv}(\sigma)$ is the number of inversions of $\sigma,$ or the number of pairs $(a,b)$ with $a,b \in \{1,2,\ldots,n\}$ such that $\sigma(a)>\sigma(b), a<b$ .

Therefore the permutation cannot be computed using 3 inversions.

more details

4 monkeys alone must be moved requiring if you imagine moving a monkey into the right place you can add 1. We need an addition of 5. In three moves this means that two of them must put two monkeys in the right place and one of them must only change one. There is no way to swap two monkeys such that one goes into the right place, without first swapping a pair of monkeys so that none are moved into the right place.

We can represent each permutation by its corresponding permutation matrix (having only zeroes except for exactly one $1$ in each column and each row), for example the wanted monkeys permutation $(A,B,C,D,E)\longrightarrow (E,D,C,B,A)$ is given by the matrix $P$ that reorder the monkey's vector throw multiplication:

$\left[\begin{array}{ccccc} &&&&1\\ &&&1&\\&&1&&\\&1&&&\\1&&&&\end{array}\right] \left[\begin{array}{c}A\\B\\C\\D\\E\end{array}\right] =\left[\begin{array}{c}E\\D\\C\\B\\A\end{array}\right]$

In this language, the problem consists in rewriting the matrix $P$ as a multiplication of transposition matrices (that only swap two letters), the first example given before is:

$\left[\begin{array}{ccccc}1&&&&\\&&&1&\\&&1&&\\&1&&&\\&&&&1\end{array}\right] \left[\begin{array}{ccccc}&&&&1\\&1&&&\\&&1&&\\&&&1&\\1&&&&\end{array}\right] \left[\begin{array}{c}A\\B\\C\\D\\E\end{array}\right] =\left[\begin{array}{ccccc}1&&&&\\&&&1&\\&&1&&\\&1&&&\\&&&&1\end{array}\right] \left[\begin{array}{c}E\\B\\C\\D\\A\end{array}\right] =\left[\begin{array}{c}E\\D\\C\\B\\A\end{array}\right]$

Now suppose that this could be done with three transpositions $P=T_1T_2T_3$ then we would have

$1=\det(P)=\det(T_1T_2T_3)=\det(T_1)\det(T_2)\det(T_3)=(-1)^3=-1$

which clearly can't be true. Can you see why $\det(T)=-1$ for any transposition matrix?

For 3 swaps the number of monkeys must be a multiple of 3.

Any permutation can be achieved by making a sequence of pairwise swaps. It is quite well known that the permutations of a given set fall into two classes:- those requiring an even number of swaps (and which cannot be done with an odd number of swaps), and those requiring an odd number of swaps (and which cannot be done with an even number of swaps).

Since the question shows us explicitly that the required permutation can be done with an even number of swaps we know immediately that it cannot be done with an odd number of swaps. In particular $\boxed{\text{it cannot be done with three swaps}}$

Here is a nice intuitive explanation of the parity property of permutations.

The give order is :A,B,C,D,E The required order:E,D,C,B,A In both the cases C remains in the middle(2 positions far from the right and 2 potions far from the left). So in 3 swaps this arrangement is impossible because we need to first take C and swap with some other position and then swap it back again with the correct position hence twice the work ,therefore this work takes place for 2n times and three times swapping doesn't hold a stand.

Monkey C has to stay in the middle, so there are 4 left who "take" two of three swaps. Now the order is reversed and any third swap would break it.

No. One can prove in algebra, that for all $n\in\mathbb{N}^{+}$ , that

$\pi:S_{n}\longrightarrow (\mathbb{Z}/2\mathbb{Z},+)$

given by $\pi(\sigma)=\mod(L,2)$ where $L=$ length of a decomposition of $\sigma$ into 2-swaps, is well-defined (and necessarily an homomorphism). Here we have an element (the permutation that reverses the order) in $S_{5}$ and we are counting up the length of a decomposition into 2-swaps: by the above, this is necessarily always even.

The fastest move is 2 steps. And if we want to let it slower, we only can add C move into it, but fastest move C to another position and back need 2 steps, 2+2=4, so we can't do it in 3 steps. (Maybe?)

I just thought, "The examples only show an even number of moves. There are an even number of monkeys that have to move, therefore, there can't be an odd number of moves to achieve the desired objective." Is this wrong?

Consider the following numeric function with 5 arguments:

$f(X_1,X_2,X_3,X_4,X_5)=(X_1-X_2)(X_1-X_3)(X_1-X_4)(X_1-X_5)(X_2-X_3)(X_2-X_4)(X_2-X_5)(X_3-X_4)(X_3-X_5)(X_4-X_5)$

Every two by two combination of the arguments are presented in the form of a unique difference, factor to the product. If all the arguments takes different numeric values, the result of the function will be different from zero, positive or negative. The signal of this value, changes when the values ( $x$ and $y$ ) of two arbitrary arguments ( $X_x$ and $X_y$ ) are swapped. This happens because:

• the single factor $(X_x - X_y)$ changes signal (since $(x-y)=-(y-x)$ ).
• the products $(X_x - X_z)\times(X_y - X_z)$ stays unchanged (since $(x-z)\times(y-z)=(y-z)\times(x-z)$ ).
• the products $(X_x - X_z)\times(X_z - X_y)$ stays unchanged (since $(x-z)\times(z-y)=(y-z)\times(z-x)$ ).
• the products $(X_z - X_x)\times(X_z - X_y)$ stays unchanged (since $(z-x)\times(z-y)=(z-y)\times(z-x)$ ).
• the other factors $(X_z - X_w)$ stays unchanged (since, as you must have guessed, $z$ and $w$ means values for non-exchanged arguments).
• when we exclude from the product that constitutes our function, all the terms like the previous ones, no other term remains.

A function defines an order over its arguments. I show here a function that changes its signal when we exchange an argument value for another, being numerical monkeys or otherwise. Another exchange and the signal returns to the original. An even number of exchanges leaves the function result invariant, an odd number flips its signal. Because a numerical result different from zero cannot be both positive and negative, a permutation achievable by an odd number of swaps cannot be reached by an even number, and vice-versa. This conclusion is not dependent on the number of monkeys.

Since we already verified that we can reverse the order of our monkeys by doing an even number of swaps, this excludes the possibility of doing it using an odd number of swaps, like three.

Given that the permutation can be performed using two swaps, the permutation is an element of the group A5. If we assume that the permutation can be performed using three swaps, then the permutation would not be an element of A5.