¿Por qué hay una solución única para el puzzle de la rana?

Question

Estoy bastante seguro de que esta es una pregunta trivial, pero eh...

La Rana Puzzle es un famoso 8º grado de problema (jugable aquí):

$3$ ranas rojas y $3$ azul ranas están sentados en hojas de nenúfar, con un recambio de hoja de lirio entre ellos. Las ranas pueden deslizarse hacia adyacentes lirios o saltar por encima de una rana; las ranas no puede saltar por encima de más de una rana. Las ranas no puede moverse hacia atrás. Podemos intercambiar las ranas rojas con el azul de las ranas?

Es bastante fácil de solucionar, incluso para $n$ ranas rojas y $m$ azul ranas. Pero me resulta muy difícil "mathematize": si vemos el "charco" como un elemento de $(\mathbb{Z}_3)^7$ ? Entonces, ¿cómo podemos describir los posibles movimientos ?

Incapaz de traducir este familiar en términos matemáticos, estoy por lo tanto muy desconcertados por este... rompecabezas. En particular, me parece que no puede encontrar ¿por qué hay siempre una solución, y sólo uno (hasta symetry, por supuesto), para cualquier número de ranas. He tratado de hacer que funcione en Scylab pero estoy muy oxidado en programación...

Todo lo que he logrado demostrar es que una rana no puede saltar por encima de una rana del mismo color, pero no estoy seguro de que esto va a llevar a alguna parte.

Pregunta extra : es el número de la solución es igual al número de vacío de lirios?

Answer 1

He sido incapaz de encontrar nada parecido a una prueba formal, pero he notado varias cosas que pueden ayudar a alguien a hacerlo.

• En cada paso, usted debe elegir entre seguir una rana de color $A$ o de color $B$. (Bastante obvio, lo sé, pero dos ranas del mismo color que nunca están de ambos móviles.)

Por lo tanto, vamos a $a$ denotar mover el único móvil de la rana de color $A$ (hacia la derecha), y deje $b$ denotar mover el único móvil de la rana de color $B$ (mover a la izquierda).

• El número total de movimientos usadas en cualquier solución es fijo, y es igual a $mn + m+n$
• Hay exactamente $2$ soluciones para cualquier rana problema, como el OP señaló

• Si, en cualquier momento, dos ranas del mismo color están en posiciones adyacentes, hay un sapo de otro color por delante de ellos, y el lilypad que está detrás de ellas, se han perdido.

  • Perder el caso #1: ... $A$ ... $BB$ ... $\_$ ...
  • Perder el caso #2: ... $\_$ ... $AA$ ... $B$ ...

• El uso de este, es imposible que alguna vez se mueven $aa$ (si es que hay un $B$ rana a la derecha), a menos que una de las $A$ ranas salta un $B$ rana.

  • Por ejemplo, usted puede iniciar el juego con $aa$ o $bb$.
  • Si usted comienza con $a$, su próximo paso debe ser $b$. Usted puede hacer $b$ o $bb$, pero $bbb$ resultaría en (perder el #de caso 1) disposición $AAA$ ... $BABB\_$ ... $BBB$.

• La ampliación de este, si usted se ha mudado $k$ de la $A$color de las ranas, hay en la mayoría de las $k$ salta posible para el $B$ ranas, y que no puede hacer más que $(k+1)$ $b$-el tipo se mueve de forma consecutiva.

• Recorrer el juego, caso por caso, es bastante fácil manualmente muestran que hay una opción posible para la siguiente secuencia de movimientos. (No tengo pruebas de esto, pero todavía no he encontrado un contraejemplo).

  • Inicio: (debido a la simetría, dos movimientos posibles) \begin{gather} A...AA\_BB...B\\ aa = \mathrm{lose}\\ bb = \mathrm{lose}\\ ab = \mathrm{okay}\\ ba = \mathrm{okay} \end{reunir}
  • Supongamos que hemos elegido para mover $ab$ \begin{gather} A...ABA\_B...B\\ aa = \mathrm{lose}\\ bb = \mathrm{lose}\\ ab = \mathrm{lose}\\ ba = \mathrm{okay} \end{reunir}
  • Ahora hemos movido $abba$ \begin{gather} A...AAB\_BA...B\\ b = \mathrm{lose}\\ aaa = \mathrm{lose}\\ aab = \mathrm{okay}\\ aba = \mathrm{lose}\\ abb = \mathrm{lose} \end{reunir}
  • Ahora hemos movido $abbaaab$ \begin{gather} A...BA\_ABA...B\\ a = \mathrm{lose}\\ ba = \mathrm{lose}\\ bb = \mathrm{okay} \end{reunir}

Usted consigue la idea por ahora, pero no debería ser demasiado difícil escribir un fichero automatizado de armario para las pequeñas $m$$n$.

• Varios Ejemplo De Soluciones:
  • $3$ vs $3$: $abbaaabbbaaabba$
  • $4$ vs $3$: $abbaaabbbaaaabbbaab$
  • $5$ vs $3$: $abbaaabbbaaaaabbbaaabba$
  • $6$ vs $3$: $abbaaabbbaaaaabbbaaaabbbaab$
  • $7$ vs $3$: $abbaaabbbaaaaabbbaaaaabbbaaabba$

Answer 2

Cuando sólo hay un vacío de la almohadilla, Tim510 la respuesta puede ser mejorado en un algoritmo automático para predecir la (única) el próximo paso de sólo dos posiciones de la almohadilla de repuesto, izquierda y derecha. Voy a cambiar de notación un poco, denotando $R$ed ranas por $R$, $B$lue ranas por $B$ e las $S$pare lily pad por $S$.

Para mayor comodidad, se pueden agregar dos azul ranas en la izquierda y dos ranas rojas a la derecha, (como si fueran "ya colocado con éxito" de un desafío con más ranas) de esta manera siempre habrá al menos dos caracteres a la izquierda y a la derecha para S.

Como notado por Tim510, los patrones de $RBB(...)S$, $S(...)RRB$ no puede aparecer en cualquier momento, en cualquier solución. En particular, $RBBS$ $SRRB$ están prohibidas subpalabras. De ello se desprende que $RBSRB$ también está prohibido subword, puesto que lleva en uno mover a cualquiera de las dos prohibido subpalabras de arriba. Aquí va nuestro algoritmo :

$$ \begin{array}{rclcl} RR & S & RR &:& \text{unreachable state} \\ RR & S & RB &\to& RRBRS \\ RR & S & BR &\to& RSRBR \text{ ( nontrivial case, see explanation below )} \\ RR & S & BB &:& \text{initial state, choose } RSRBB \text{ or } RRBSB \\ & & & & \\ RB & S & RR &\to& SBRRR \\ RB & S & RB &:& \text{forbidden state} \\ RB & S & BR &\to& SBRBR \\ RB & S & BB &\to& SBRBB \\ & & & & \\ BR & S & RR &\to& BSRRR \\ BR & S & RB &\to &BRBRS \\ BR & S & BR &:& \text{unreachable state} \\ BR & S & BB &\to& BRBSB \text{ ( nontrivial case, see explanation below )} \\ & & & & \\ BB & S & RR &:& \text{final state} \\ BB & S & RB &\to& BBBRS \\ BB & S & BR &\to& BBBSR \\ BB & S & BB &:& \text{unreachable state} \\ \end{array} $$

Explicación en el trivial de los casos. El lector podría preguntarse por qué escribimos $RRSBR \to RSRBR$, ya que (a priori) nada de lo dispuesto en nuestras reglas nos prohíbe haciendo $RRSBR \to RRBSR$. Si nos fijamos en las entradas de nuestro algoritmo, podemos ver que una $RRSBR$ estado sólo puede venir de uno de

$$ \begin{array}{rclcl} RRRB & S & RR &\to& RRSBRRR \\ RRRB & S & BR &\to& RRSBRBR \\ RRRB & S & BB &\to& RRSBRBB \\ \end{array} $$

En los dos últimos casos, el prohibido subword $RBSRB$ nos deja sin opción de decidir el siguiente movimiento. Y el primer caso es en realidad inalcanzable, ya que es fácil demostrar por inducción que cualquier subword de la forma $R^{x}BSR^{y}$ o $R^{x}SBR^{y}$ $x,y\geq 2$ es inalcanzable.

El otro caso no trivial se explica de manera similar.

Answer 3

Vamos el rojo y el azul flog, $1$$2$, y el vacío de la almohadilla es $0$, en la primera nos movemos cada $1$s hacia la izquierda.

$$\\11・・・100・・・022・・・2$$

$→00・・・011・・・1022・・・2\tag 1$

Ahora, vamos a comprobar [ $11・・・1022・・・2$ ] [ $01212・・・12$ ].

Un paso previo es $10212・・・12$. Nos movemos cada $1$s a la izquierda, $$11212・・・121202$$ Next, move every $2$s right, $$11「01212・・・1212」22$$ Since $""$ is same with first sequence, repeating this operation, then we get first term $(1)$ [$11---1022---2$]. Por lo tanto podríamos decir que la pregunta tiene definitivamente una solución.

También Si una rana puede saltar mismo color, se genera una secuencia $1220$ o $0112$. Estos casos nunca puede ir adelantado ya. Sobre el bono de la pregunta, creo que se convierta en la recurrencia de la secuencia, sin embargo.

Si los números de color rojo y azul de las ranas y los vacíos de la almohadilla se $n,m,l$, el número de saltar movimiento es $nm$, secundarios movimiento es $l(n+m)$. Debido a la izquierda ranas se encuentran justo flog $nm$ veces. Tengo esto por un poco de endeudamiento de un sitio Japonés.

Answer 4

Bueno, supongo que no hay otra manera de inducción. Vamos a ir a la derecha, B, vaya a la izquierda. Decimos que las ranas están saltando en una sola dirección, a menos que una configuración de la forma $$\{..XX\}\_\{BABABA\}..AB\{YY..\}$$ o de su espejo inverso sean alcanzados y la dirección de salto se invierte.

La base: en realidad, Hay dos posibilidades para el primer movimiento. Así que vamos a considerar un caso en que el primer paso ya está hecho. Obviamente tenemos una configuración de la forma descrita anteriormente, sólo la parte de los soportes tiene longitud cero (que es la razón por la que está entre paréntesis, que implica que parte de la necesidad de no estar ahí en todo).

Supongamos que es cierto en algún momento durante el juego

Luego nos inevitable llegar a este tipo de estado otra vez. Ya que en esta configuración, sólo una de las ranas se puede mover, y es la X en el caso de que X=a ( si no queremos terminar en una configuración AB_AB, y B salta a ella o saltos, en ambos casos, usted no será capaz de terminar el juego). O en el caso de X=a a salta por encima de Una, pero que volverá a ser un fracaso. O para X=B o $\{..XX\}$ a no estar allí, y el único B se mueve a la misma, ya que simplemente no hay otra opción. En ambos casos se terminan en una configuración: $$\{...XXX\}\_ABABA...AB\{YYY...\}$$

Aquí es obvio que las ranas siempre tiene que saltar hasta la $B\{YYY...\}$ es alcanzado, de lo contrario Un "barriered" no se puede llegar a donde se necesita, porque el libre pod está a la izquierda de ella y no puede terminar en la derecha a menos que la rana se mueve, lo cual es imposible en el estado _BBA. Así que no les queda. Y va a llegar al estado de $$\{...XXX\}AB...BABA\_\{YY...\}$$, que es el mencionado estado de espejo, que se llevará a la preivous tipo de estado basado en la misma argumentación.

Ya que ninguna otra configuración es posible, siempre vamos a tener sólo una opción que nos acercará hasta el final. Nosotros siempre están saltando en una dirección o nos debe mover con el de la rana en la final(inicio) de la línea de las ranas, que no se ha movido todavía, o no se va a mover más. Así que siempre tenemos sólo y sólo una opción de cómo acercarse al éxito final.

No de las matemáticas, en lugar exhaustiva argumentación, pero a veces no hay otras formas de demostrar cosas.