Moscow puzzle. Number lattice and number rearrangement. Quicker solution?

enter image description here

I have already considered chains of numbers like $4-19, 19-9, 9-22$, to solve the problem and got the answer. However just out of curiosity, can anyone think of a better/quicker solution?

(answer is 19 btw)

Solutions Collecting From Web of "Moscow puzzle. Number lattice and number rearrangement. Quicker solution?"

There is a fool-proof and quite elegant approach to this problem.

Imagine that the chips where originally placed correctly, then moving the chips around produced a permutation of the chips, this permutation sent chip $1$ to where chip $24$ was etc.

We can write down this permutation in it’s cycle decomposition. It is $(1,24,2,11,16,20,7)(3,5,18,14,23,10)(4,22,9,19)(6,25,13,15,12)(8)(17,21)$. To find this you just have to see chip $1$ went to position $24$, then chip $24$ went to position $2$ and so on until you go back to chip $1$, here a cycle closes, then look for the next smallest number that hasn’t appeared (3 in this case) and do the same thing, and so on until you finish.

So if you want to go back to the ordered version you have to apply the inverse of this permutation. It is a well-known fact that the inverse of a permutation can be found by writing each cycle backwards. So the inverse is:

$(7,20,16,11,2,24,1)(10,23,14,18,5,3)(19,9,22,4)(12,15,13,25,6)(8)(21,17)$.

What we would like to do is write this permutation as a factor of the least number of transpositions possible the least number of transpositions of a permutation of $n$ objects is going to be $n-r$ where $r$ is the number of cycles in the cycle decomposition of the permutation. In this case we have $6$ cycles, thus we need $25-6=19$ transpositions. For a proof of this result see here.


On second thought the proof in that link might be a little too non-combinatorial, here is a simpler proof:

To see it is possible in $n-r$ transpositions you just have to see a cycle of length $m$ can be written in $m-1$ transpositions, to see this you can use induction and observe $(1,2,3,\dots ,m)=(1,2,\dots ,m-1)(m-1,m)$.

You can also give a direct construction: $(1,2\dots m)=(1,2)(2,3)\dots(m-1,m)$

Note that to multiply non disjoint permutations you do it from right to left, so if you want to calculate $(12)(23)$ for example see that $2$ goes to three by the rightmost cycle and is not moved by the other cycle. So write $(23$, then notice $3$ is sent to $2$ by the rightmost cycle and the $2$ is sent to $1$ by the other cycle, so write $(321$. Notice $1$ must go to $3$ to finish the cycle as $(321)$.

Using this direct computation our permutation can be written as:

$\color{blue}{(7,20)(20,16)(16,11)(11,2)(2,24)(24,1)} \color{red}{(10,23)(23,14)(14,18)(18,5)(5,3)}\color{green}{(19,9)(9,22)(22,4)}\color{orange}{(12,15)(15,13)(13,25)(25,6)}(21,17)$

We now prove you need at least $n-r$ transpositions, consider a product of transpositions that gives us a permutation on $n$ vertices with $r$ cycles, we shall assign to such a product a graph: consider the graph where the vertices are the objects in the permutation and there is an edge between $u$ and $v$ if and only if the transposition $(u,v)$ is a factor of the product. The graph must have less than $r$ components, why? Because if two elements are in the same cycle they must be connected? why? because if two elements $a$ and $b$ are in the same cycle it means that you can get from $a$ to $b$ by applying the permutation a sufficient number of times, this would be impossible if $a$ and $b$ where not connected in the graph. Thus there is less than $r$ components, a graph on $n$ vertices with at most $r$ components must have at least $n-r$ edges, (minimality is obtained when the graph is a forest on $r$ components).


Also related is problem $1$ of day $1$ of the second selective test of Iran $2014$, available here and with solutions here