Seis Ranas - Puzzle (orden de reversión mediante transposiciones)

Question

Me había llegado a través de un rompecabezas:

Los seis educados ranas en la ilustración están capacitados para invertir su orden, por lo que el número de puestos de lectura 6, 5, 4, 3, 2, 1, con el cuadrado en blanco en su posición actual. Se puede saltar a la siguiente cuadrado (si la vacante) o saltar por encima de una rana a la siguiente plaza del más allá (si vacantes), tal como nos movemos en el juego de las corrientes de aire, y puede ir hacia atrás o adelante en el placer.

Se puede mostrar cómo realizar su hazaña en el menor número posible de movimientos?

Es muy fácil, así que cuando usted ha hecho es añadir un séptimo de la rana a la derecha y vuelve a intentarlo. A continuación, agregue más ranas hasta que son capaces de dar la menor solución para cualquier número. Para que siempre puede ser hecho, con la única plaza vacante, no importa cuántas ranas hay.

---

Respuesta: Mover las ranas en el siguiente orden: 2, 4, 6, 5, 3, 1 (repita estos movimientos en el mismo orden dos veces más), 2, 4, 6. Esta es una solución en veinte y uno se mueve - la menor cantidad posible.

Si $n$, el número de ranas, ser, incluso, se requieren $\frac{n^2+n}{2}$ se mueve, de los cuales $\frac{n^2-n}{2}$ será saltos y $n$ movimientos simples.

Si $n$ ser impar, tendremos $\frac{n^2+3n}{2}-4$ se mueve, de los cuales $\frac{n^2-n}{2}$ será saltos y $2n-4$ movimientos simples.

En los casos de escritura, para que los movimientos, todos los números en orden ascendente y la de los números impares en orden descendente. Esta serie debe ser repetido $\frac{1}{2}$ n veces, seguido por los números en orden ascendente sólo una vez. Por lo tanto la solución para el 14 de ranas será (2, 4, 6, 8, 10, 12, 14, 13, 11, 9, 7, 5, 3, 1) repite 7 veces, seguido por 2, 4, 6, 8, 10, 12, 14 = 105 se mueve.

En los casos aislados, escribe los números en orden ascendente y la de los números impares en orden descendente, repita esta serie $\frac{1}{2}(n-1)$ de veces, seguir con los números en orden ascendente (omitiendo $n-1$), los números impares en orden descendente (omitiendo 1), y concluir con todos los números (pares e impares) en su orden natural (la omisión de 1 y n). Por lo tanto para el 11 de ranas: (2, 4, 6, 8, 10, 11, 9, 7, 5, 3, 1) repite 5 veces, 2, 4, 6, 8, 11, 9, 7, 5, 3, y 2, 3, 4, 5, 6, 7, 8, 9, 10 = 73 se mueve.

(fuente)

que yo había tratado de resolver, pero no pudo encontrar el razonamiento detrás de los movimientos utilizados en la solución podría alguien decir cómo manejar este tipo de puzzles sin prueba y éxito?

Answer 1

La respuesta dada es incorrecta. El número de movimientos necesarios para resolver el rompecabezas debe ser esta secuencia, dada por $(n^2+n-2)/2$ (donde $n=\#\text{ de ranas}$).

Vamos a escribir la formación de las ranas como una cadena de números de $ 0 a$ través $ n$, lo que denota el espacio vacío por $ 0$. Con esta notación, podemos ver que cada vez está definido por el intercambio de de $ 0$ con el número uno o dos espacios a la izquierda o a la derecha, correspondiente a una rana a la izquierda o a la derecha de salto o salto a la derecha o a la izquierda, respectivamente. Desde que nos centraremos en el $ 0$, va a ser más fácil de decir que de los $ 0$ está saltando a la izquierda cuando una rana saltando a la derecha, y analagously para los otros casos.

Ahora, por la estética, podemos considerar las formaciones como los vértices de un árbol de capas, cada capa del árbol correspondiente a la vuelta de la rana en movimiento del juego. Ponemos un borde dirigido desde la formación de la $ $ (en la capa i$$) para la formación de la $ b$ (en la capa $ i+1$) si un movimiento legal nos lleva de $ a$ a $ b$. Visto de esta manera podemos considerar el rompecabezas como un problema de la ruta más corta desde $ 0123\ldots$ n $ n\ldots 3210$ (o $ n\ldots 3201$, $ n\ldots 3021$, $ n\ldots 0321$, etc). Dado que sólo estamos interesados en los caminos más cortos, las capas del árbol será distinto, como mudarse a un vecino implicaría podríamos haber llegado allí en menos movimientos.

Incluso El Caso.

Me parece el caso incluso un poco más fácil de visualizar, así que vamos a empezar con eso. Aquí es lo que el rompecabezas se ve como con $ 4$ ranas.

Usted puede ver, hay varias soluciones, resaltado en rojo, con la más corta en negrita. Vamos a acercar a estos caminos y caminar a través de ellos.

Cada solución sigue el mismo patrón. En primer lugar, el $ 0$ se mueve todo el camino a la derecha, luego cambia de dirección. No queremos deshacer nuestra jugada anterior, así que no hay solo una opción disponible - si nos saltó a la derecha, tenemos que saltar a la izquierda, y viceversa. Cuando llegamos $ 0$ de vuelta a la posición izquierda, se invierte de nuevo la dirección. Este proceso se repite hasta que todos los números están en orden. (Ver: "¿por Qué funciona esto?") La manera más rápida de hacer esto es resaltado en el camino rojo - cada movimiento a la derecha es un salto, y hay exactamente dos saltos a la izquierda.

Si decimos que el movimiento $ 0$ todo el camino a la derecha, luego todo el camino de vuelta a la izquierda constituye una "ronda", luego de cada ronda se lleva a $ n/a 2$ saltos a la derecha + $ 1$ hop a la izquierda + $ (n-2)/2$ saltos a la izquierda + $ 1$ hop a la izquierda. Eso es $ n+1$ total se mueve, $ 2$ lúpulo y $ n-1$ saltos. Ya que cada ronda se mueve el mayor número a la izquierda dos veces y el número más pequeño a la derecha dos veces, sólo necesitamos hacer esto $ n/2$ veces para poner todo en orden. También, se puede omitir el último paso (que solo serviría para poner $0$ en el extremo izquierdo), por lo que incluso en el caso requiere $$ \frac{n(n+1)}{2}-1 =\frac{n^2+n-2}{2} \text{ mueve}$$ con $$\frac{n(n-1)}{2}\text{ saltos}$$ y por tanto $$n-1\text{ lúpulo.}$$

El Extraño Caso.

Por $5$-ranas, el diagrama completo es demasiado grande, pero podemos buscar sus soluciones.

Aquí es donde nos separamos de la respuesta dada. Podemos hacerlo en $ 14$ se mueve, $ 2$ menos de $ (5^2+3\times 5)/2-4=16$.

Utilizamos esencialmente la misma estrategia que aquí como en las soluciones. Vamos a escribir el algoritmo de forma explícita. El once inicial es de $ 0123\ldots$ n y la dirección inicial es de $ d=1$. Cada vez, compruebe en primer lugar si $ 0$ en la posición $ 1$ o de $ n-1$. Si es en la posición $ p_0= 1$, vamos a la $ 0$ hop de la izquierda a la posición $ 0$ y $ d=1$. Si es en la posición $ p_0= n-1$, tiene los $ 0$ hop derecho a la posición $ n$ y $ d=-1$. En cualquier otra posición $p_0$, el $ 0$ salta a la posición $ p_0+2d$. Continuamos de esta manera hasta que las ranas son en la formación $ n\ldots 3201$.

De nuevo podemos ver que cada ronda tiene $n+1$ se mueve, $n-1$ saltos y $2$ lúpulo (ahora en direcciones opuestas). Después de completar $ k$ rondas, hay $ 2k-1$ números a la derecha de $ n$. Si hacemos esto $ (n-1)/2$ veces, tenemos $ n-2$ números a la derecha de $ n$. En esta situación, sólo tenemos que completar una 'ronda de la mitad de' hasta el final - que es, una vez que entramos $ 0$ regresar a la posición $ n-1$, todo va a estar completa. Que se $ (n-1)/2$ saltos, por lo que tenemos un total de $$\left(\frac{n-1}{2}\right)(n+1)+\frac{n-1}{2}=\frac{n^2+n-2}{2} \text{ mueve, }$$ que se rompe $$\left(\frac{n-1}{2}\right)(n-1)+\frac{n-1}{2}=\frac{n(n-1)}{2} \text{ saltos }$$ y $$2\left(\frac{n-1}{2}\right)=n-1 \text{ lúpulo.}$$

¿Por qué funciona esto?

Por suerte podemos entender nuestra solución con el uso de algunos de permutación de la teoría. Vamos a demostrar que funciona para el extraño caso. Tomando $0$ de izquierda a derecha induce la permutación $$(0,n,n-1,n-3,n-5,n-7,\ldots,8,6,4,2)$$ en $\text{Símbolo}(\{0,\ldots,n\})$. Tomando de derecha a izquierda induce la permutación $$(0,1,3,5,7,9,\ldots,n-4,n-2,n).$$ La multiplicación de estas permutaciones, tenemos $$\sigma:=(1, 3, 5, 7, 9, 11,\ldots, n,n-1,\ldots,10,8,6, 4, 2).$$ Así que si dejamos que $\sigma=(\sigma_1,\ldots,\sigma_{n})$, entonces tenemos que $$\sigma_k=\left\{\begin{array}{lcl}2k-1&:&k=1,\ldots,\frac{n+1}{2}\\ 2 (n - k + 1) &:&k=\frac{n+1}{2}+1,\ldots,n\end{array}\right.$$ donde los índices se toman mod $n$.

Vamos $m=(n-1)/2$. Tenemos, en general, que en el ciclo de la notación podemos escribir $$(i_1,i_2,i_3,\ldots,i_c)^{m}=(i_{1+m},i_{1+2m},i_{1+2m},\ldots,i_{1+cm}),$$, donde los índices se toman modulo $c$. De esto podemos obtener $$\begin{eqnarray*}\sigma^{m}&=&(1, 3, 5, 7, \ldots, 2m+1,2 m,\ldots,8,6, 4, 2)^{m}\\&=&(2,n-2,4,n-4,\ldots,m+1,m,\ldots,3,n-1,1,n).\end{eqnarray*}$$ La aplicación de esta permutación a $0,\ldots,n$ los rendimientos de la formación $$0,n-1,n,n-3,n-2,n-4,n-3,\ldots,5,2,3,1.$$ Así que ahora, podemos ver que sólo necesitamos salto $n$ a la izquierda, luego $n-2$, entonces $n-3$, etc. hasta llegar a $n,n-1,n-2,\ldots,3,2,0,1$.

Incluso el caso es demostrado de forma idéntica.

¿Cómo sabemos que este es el menor número posible?

Cada movimiento puede en la mayoría de invertir el orden de los $2$ ranas. Debemos poner rana $n$ a la izquierda de la totalidad de los $n-1$ de las otras ranas, por lo que es de al menos $n$ saltos a la derecha allí. Esto no se puede modificar el orden de las otras ranas, así que para mover la rana $n-1$ para estar a la izquierda de la $n-2$ restantes ranas, se necesitan al menos $n-2$ saltos. Continuando de esta manera, tenemos a un mínimo de $$\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}$$ saltos. Sin embargo, se discutió anteriormente, necesitamos $1$ hop cada una de las ranas $2$ $n$ a cambiar de dirección, por lo que se necesitan al menos $$\frac{n(n-1)}{2}+n-1=\frac{n^2+n-2}{2}$$ se mueve. Por lo tanto nuestra construcción es de longitud mínima.