Intereting Posts

Proving that every vector space has a norm.
Fermat numbers are coprime
How to solve for any given natural number n?
How can we show that $\ln{2}=\sum_{n=1}^{\infty}{(-1)^{n-1}\over n}\left({12\over e^{n\pi}-1}+{4\over e^{n\pi}+1}\right)$
Question on Good Pairs
Constructing a strictly increasing function with zero derivatives
A ring element with a left inverse but no right inverse?
How can I find equivalent Euler angles?
Prove $e^x=1+\frac{1}{\sqrt{\pi }}{\int_0^x \frac{e^t \text{erf}\left(\sqrt{t}\right)}{\sqrt{x-t}} \, dt}$
Vanishing at the infinity of a function in the Sobolev space.
Fibonacci identity proof
Prove that a holomorphic function injective in an annulus is injective in the whole ball
Is quotient of a ring by a power of a maximal ideal local?
Find exact value of $\cos (\frac{2\pi}{5})$ using complex numbers.
Graph of a matrix

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)

- $n$-Bit Strings Not Containing $010$
- An easy reference for genetic algorithm
- Number of horse races to determine the top three out of 25 horses
- Counting subsets containing three consecutive elements (previously Summation over large values of nCr)
- Problem with an algorithm to $3$-colour the edges of cubic graphs
- Computing GCD of all permutations (of the digits) of a given number

- Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number
- How to verify a shortest path tree with O(V+E) running time by giving node's predecessor and shortest distance
- Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$
- Problem with an algorithm to $3$-colour the edges of cubic graphs
- Finding a (small) prime great enough that there are at least m elements of order m
- Twenty questions against a liar
- $x+1/x$ an integer implies $x^n+1/x^n$ an integer
- Trees whose complement is also a tree
- Development of a specific hardware architecture for a particular algorithm
- Algorithm to get the maximum size of n squares that fit into a rectangle with a given width and height

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

- Proof of a special case of Fermat's Last Theorem.
- $2n^2-\lfloor m^b\rfloor=k$ has only finitely many integer solutions
- Proving Crapo's Lemma
- How to prove $AB$ is a diagonalizable matrix?
- Principal maximal ideals in coordinate ring of an elliptic curve
- Set Theory – Subset of set
- Relationship between Dixonian elliptic functions and Borwein cubic theta functions
- Finding the Derivative of |x| using the Limit Definition
- Question about basis and finite dimensional vector space
- Prove that a subspace of dimension $n$ of a vector space of dimension $n$ is the whole space.
- Can the following triple integral be computed via elementary calculus methods?
- What is larger — the set of all positive even numbers, or the set of all positive integers?
- Normal bundle of a section of a $\mathbb{P}^1$-bundle
- Intersect and Union of transitive relations
- Interchanging Summation and Integral