Ya he considerado cadenas de números, como los $4-19, 19-9, 9-22$, para resolver el problema y la respuesta. Sin embargo, sólo por curiosidad, ¿alguien puede pensar en una mejor y más rápida solución?
(la respuesta es 19 por cierto)
Respuesta
¿Demasiados anuncios?
Hay un infalible y muy elegante, enfoque a este problema.
Imagino que las fichas donde originalmente colocado correctamente, a continuación, mover las fichas alrededor producido una permutación de los chips, esta permutación enviado chip $1$ a donde chip $24$ etc.
Podemos escribir esta permutación en su ciclo de descomposición. Es $(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)$. Para encontrar este sólo hay que ver el chip de $1$ acudió a la posición $24$, luego de la viruta $24$ acudió a la posición $2$ y así sucesivamente hasta que regrese a chip $1$, aquí un ciclo se cierra, a continuación, busque el siguiente número más pequeño que no ha aparecido (3 en este caso) y hacer la misma cosa, y así sucesivamente hasta terminar.
Así que si quieres volver a la versión solicitada se tiene que aplicar la inversa de esta permutación. Es un hecho bien conocido que la inversa de una permutación se puede encontrar mediante la escritura de cada ciclo hacia atrás. Así que la inversa es:
$(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)$.
Lo que nos gustaría hacer es escribir esta permutación como un factor de al menos el número de transposiciones posible el menor número de transposiciones de una permutación de $n$ objetos va a ser $n-r$ donde $r$ es el número de ciclos en el ciclo de descomposición de la permutación. En este caso tenemos a $6$ ciclos, por lo que necesitamos $25-6=19$ transposiciones. Para una prueba de este resultado vemos aquí.
En segundo pensamiento a la prueba del vínculo podría ser un poco demasiado no combinatoria, aquí es una sencilla prueba:
A ver que es posible, en $n-r$ transposiciones sólo tienes que ver un ciclo de longitud $m$ puede ser escrito en $m-1$ transposiciones, para ver esto, usted puede usar la inducción y observe $(1,2,3,\dots ,m)=(1,2,\dots ,m-1)(m-1,m)$.
También puede dar un directo de construcción: $(1,2\dots m)=(1,2)(2,3)\dots(m-1,m)$
Tenga en cuenta que para multiplicar no disjuntas permutaciones de hacerlo de derecha a izquierda, de modo que si se desea calcular el $(12)(23)$ por ejemplo ver que $2$ va a las tres por el de más a la derecha ciclo y no es movido por el otro ciclo. Así que escribe $(23$, entonces la notificación $3$ es enviado a $2$ por el de más a la derecha de ciclo y el $2$ es enviado a $1$ por el otro ciclo, por lo que escribir $(321$. Aviso de $1$ debe ir a $3$ al finalizar el ciclo como $(321)$.
El uso de este cálculo directo de nuestro permutación puede ser escrita como:
$\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)$
Ahora podemos demostrar que usted necesita, al menos, $n-r$ transposiciones, considere un producto de transposiciones que nos da una permutación en $n$ vértices con $r$ ciclos, se deberá asignar a un producto de un gráfico: considere la gráfica donde los vértices son los objetos en la permutación y hay una arista entre el $u$ $v$ si y sólo si la transposición $(u,v)$ es un factor del producto. El gráfico debe tener menos de $r$ componentes, ¿por qué? Porque si dos elementos están en el mismo ciclo que debe estar conectado? por qué? porque si dos elementos $a$ $b$ están en el mismo ciclo que significa que usted puede obtener de $a$ $b$mediante la aplicación de las permutaciones de un número suficiente de veces, esto sería imposible si $a$ $b$ cuando no está conectado en el gráfico. Por lo tanto hay menos de $r$ componentes de una gráfica en la $n$ vértices con en la mayoría de las $r$ componentes debe tener al menos $n-r$ bordes, (minimality se obtiene cuando el gráfico es un bosque en $r$ componentes).
También se relaciona el problema de $1$ día $1$ de la segunda prueba selectivas de Irán $2014$, disponible aquí y con soluciones aquí
