La Tejedora de la aplicación Android, $\rightarrow$ lindo combinatoria problema

Question

Hay un Androide aplicación de rompecabezas llamado "El Tejedor". Mi pregunta es ¿por qué cada nivel parece ser resueltos en la medida de movimientos menos de lo que uno podría pensar ingenuamente.

Aquí está un enlace para las personas que quieren jugar a lo largo de sus dispositivos Android, pero esto no es necesario para entender la cuestión. (NB estoy nada que ver con la promoción de este juego en cualquier forma; yo soy un usuario final que sólo se interesó en las matemáticas detrás del juego).

Es muy fácil explicar el objetivo de este juego de puzzle. Un nivel se parece a esto cuando se inicia:

y parece que esto cuando haya terminado:

Las cintas de "flujo" de arriba a abajo y se puede girar o desenrollar dos cintas tocando en donde se encuentran. Usted no puede cambiar el orden de las cintas se va "en" (desde la parte superior) o sus colores. El objeto es retorcer las cintas alrededor dentro de la cuadrícula rectangular de modo que la "salida" de la red coincida con los pequeños cuadrados de colores. Por ejemplo, en el juego anterior, inicialmente sólo una salida de la plaza se iguala -- el cuadrado verde que está permitiendo una cinta verde para "escapar" de la cuadrícula rectangular. Todas las otras plazas no coinciden y por lo que algunos de cinta de torsión es necesario. Un movimiento en un nivel consta de torsión o desenrollar dos cintas (pulsando sobre ellos). Es muy lindo.

También hay una "estrella" del sistema, y para conseguir 3 estrellas en un nivel debe resolver utilizando el mínimo número de "giros". Como se puede ver he hecho un muy mal trabajo en la resolución de nivel de 2.4; no tengo estrellas. Hay soluciones a este nivel con el menor número de giros, de hecho esto es obvio, porque en mi solución aquí la parte inferior "switch" se enciende pero no tiene que ser-los dos de naranja cintas sólo podía pasar por encima de cada uno de los otros.

La pregunta.

He trabajado a través de los niveles de este juego, y yo estaba muy sorprendido de encontrar que incluso en tarjetas grandes (el más grande es de 6x6) uno siempre parecía ser capaz de resolverlos en la medida de movimientos menos de lo que esperaba. Aunque el juego del tamaño de la junta directiva nunca se hace más grande que el de $6\times 6$ y también hay sólo 6 colores de la aplicación, uno puede, por supuesto, sólo soñar con arbitrariamente grandes tablas que involucran arbitrariamente de muchos colores.

Conjetura En un $a$ $b$ junta, si el nivel es solucionable, en absoluto, entonces es solucionable en la mayoría de los $a+b-1$ se mueve (es decir, en la mayoría de las $a+b-1$ "desenrolla").

En particular estoy las conjeturas de que el mayor número de vueltas que tiene que hacer es $O(a+b)$ lugar $O(ab)$.

Aquí es lo que yo sé acerca de esta conjetura.

Lema de La conjetura es verdadera si $a=1$.

Prueba: trivial (sólo hay $b=a+b-1$ interruptores en el tablero).

Lema de la conjetura es verdadera si $a=b=2$

Prueba: el único contraejemplo sería un consejo para los que la única solución sería con todos los cuatro interruptores de conmutación. Pero unswitching la parte superior y la parte inferior del interruptor conduce al mismo fin de la cinta de salida.

Lema de La conjetura es verdadera si $ab\leq 20$.

Prueba: la fuerza bruta del equipo de búsqueda.

Tenga en cuenta que en este último caso voy a permitir que un número arbitrario de colores (no sólo de 6 como en la aplicación).

Lema de La conjetura es verdadera para todos los 150 niveles que vienen con el juego.

Prueba: la fuerza bruta de verificación.

Lema Para determinado $a,b\geq1$ existe un nivel cuya única solución es $a+b-1$ giros (y, en particular, mi conjetura es el mejor posible).

Prueba: se verifica que el nivel de con $a+b$ entrada distintos cintas, y que se resuelve por el cambio en el $a+b-1$ interruptores que comprende la parte superior derecha e inferior derecha de la cuadrícula de interruptores, tiene esta propiedad (NB el cheque es bastante más fácil de hacer una vez que haya jugado un par de niveles y consiguió la caída de la combinatoria).

Creo que eso es todo lo que sé. ¿Alguien puede terminar el trabajo por probar mi conjetura?

---

[Añadido dos días más tarde] Aquí está mi interpretación de algunas discusiones (ahora suprimido) con Calum Gilhooley, un grupo de la teoría de la interpretación de la conjetura (pero es un poco extraño grupo de la teoría de la pregunta).

Reparamos los enteros positivos $a$$b$, y definir un conjunto $S=\{r_1,r_2,\ldots,r_a,s_1,s_2,\ldots,s_b\}$ $a+b$ símbolos (pensamiento de como las cintas). Cada "cambio" puede ser pensado como una transposición, y es importante tener en cuenta que con el modelo que voy a describir, el estado inicial del switch es que las cintas de la cruz para la transposición en realidad es una transposición (es decir, se puede cambiar fuera de lugar de sobre). La siguiente imagen muestra el por qué de la convención es sensato -- cuando todos los interruptores se activan tenemos algo que se parece a la identidad como se puede ver en la imagen de abajo.

Leemos las transposiciones de arriba a abajo en la imagen; si el $r_i$ $s_j$ también se numeran de arriba a abajo, a continuación, la primera transposición es $(r_1\ s_1)$, en los próximos dos (que conmuta por lo que puede ser hecho en cualquier orden) $(r_1\ s_2)$ $(r_2\ s_1)$ y así sucesivamente; en el $n$th paso que consideramos $(r_i\ s_j)$ $i+j=n+1$ y esto va hasta el final de la transposición $(r_a\ s_b)$. Multiplicando todos estos $ab$ transposiciones juntos nos da un elemento $X=(r_1\ s_1)(r_1\ s_2)(r_2\ s_1)\cdots(r_a\ s_b)$. Este es el estado inicial de la junta.

Ahora para $S$ un subconjunto de a $\{1,2,\ldots,a\}\times\{1,2,\ldots,b\}$ se puede considerar el elemento $X_S$ obtenido por tomar la representación de los productos de $X$ y, a continuación, la eliminación de las transposiciones $(r_i\ s_j)$ $(i,j)\in S$ (y multiplicar esos que no nos quite juntos en el mismo orden en que lo hicimos para obtener $X$).

La reformulación de la pregunta ¿Es cierto que para $S\subseteq\{1,2,,\ldots,a\}\times\{1,2,\ldots,b\}$ la permutación $X_S$ es igual a $X_T$ algunos $T$ del tamaño en la mayoría de los $a+b-1$?

Aquí es un caso especial: es cierto que la identidad puede ser escrito como $X_T$ algunos $T$ del tamaño en la mayoría de los $a+b-1$? Eso es probablemente una relativamente fácil responder a esta pregunta. Es cierto que para $a=b$, que no es difícil de comprobar.

Answer 1

Esto puede ser resuelto por las siguientes codiciosos estrategia (donde suponemos que cada cinta tiene un color único y, por tanto, un objetivo único, como todos los casos puede ser reducido a este). El cuerpo principal del post demuestra que resuelve las cosas en la mayoría de los $n+m-1$ se mueve. La adición demuestra que es óptimo:

Rellenar la cuadrícula de abajo hacia arriba (es decir, que comienza en la parte más alta de la celda, pasando a los dos células debajo de él, a continuación, los tres en la fila siguiente, y así sucesivamente) y hacer una vuelta de tuerca* sólo cuando se hará una cinta para la cabeza directamente para su salida.

Esto funciona porque, como vamos por lo que se desplaza de arriba a abajo, sabremos que el saliente de la ruta de acceso de cualquier giro que hagamos será libre de giros, es decir, ir de arriba a abajo asegura que si enviamos una cinta en línea recta hacia su salida, no será desviada a lo largo del camino, a menos que hagamos un adicional de giro más tarde. Sin embargo, nunca vamos a hacer otro giro en la trayectoria de la cinta rumbo hacia su destino en nuestra estrategia, es decir, si tenemos una cinta de color $A$ hacia el objetivo de color $A$ intersección con una cinta de color $B$, luego de hacer el giro va a enviar la cinta de color $B$ a la meta de color $A$ y la cinta de color $A$ el objetivo de otro color - lo que significa que nuestra estrategia no hacer un giro. Esta situación se ilustra como sigue:

donde las líneas punteadas indican qué sucedería si nos hizo hacer un giro. Este sería estúpido, así que nunca hacer cosas como esa. (La figura también ilustra implícita la hipótesis de que existe una sección libre de giros, que nunca se violan tanto tiempo como nos movemos de arriba hacia abajo en nuestro torcer). Por lo tanto, utilizamos más de un giro por la cinta.

Sabiendo que si nos envía una cinta hacia su objetivo, va a llegar a ella, sólo tenemos que demostrar de lo que somos, en algún punto, enviar cada cinta hacia su objetivo. Podemos hacer esto por inducción. En particular, supongamos que tenemos una salida de $O$ a la izquierda abajo lado (teniendo en cuenta que la simetría lleva el argumento a la derecha-lado inferior) de tal manera que todas las salidas por encima de ella (es decir, a la izquierda y arriba de $O$) estarán conectados a sus entradas apropiadas mediante el uso de mi estrategia. Se puede considerar la "fila" de intersecciones por encima de la de salida $O$. Si la cinta de opciones correspondiente se inicia en esta fila, luego fue siempre dirigida hacia su salida adecuada y nunca vamos a torcer en nuestra estrategia. De lo contrario, considerar que, si pensamos en el juego como un grafo con vértices en las intersecciones y los bordes donde las cintas son (con aristas y los vértices donde las cintas de entrar y salir), entonces podemos señalar que la eliminación de la fila por encima de la $O$ divide el gráfico en dos segmentos conectados uno "por encima" de la fila (es decir, los puntos donde $O$ podría ser alcanzado por el descenso de la cinta) y el de abajo. La cinta va a $O$ debe iniciar en el segmento por encima de la fila, ya que de lo contrario no podría llegar a $O$ y el rompecabezas sería irresoluble. Sin embargo, se debe terminar en el segmento de debajo de la fila porque la única salidas en la parte superior del segmento serían los de arriba $O$ -, que se conecta a sus correspondientes cintas y, por tanto, no el uno destinado a $O$. Así, la cinta debe de cabeza para una salida no en la sección superior - pero para hacer esto, se debe tener en algún punto de entrar en la fila de arriba $O$, momento en el cual serán desviados hacia la $O$ y, por tanto, encontrar su solución. Para ilustrar esto, tenemos otra bonita imagen: donde podemos ver que, no importa que sea posible entrada elegimos para poner la cinta púrpura pertenecientes a $O$, se debe cruzar la fila de $O$ desde todas las salidas en la parte superior de la sección ya están llenas. Cuando se cruza la fila de $O$, se desvía.

Por lo tanto, esta estrategia siempre funciona y se utiliza en la mayoría de un giro por la cinta. Si nos detenemos a considerar el estado después de que (en la mayoría) $n+m-1$ giros, todos excepto uno de la cinta será conectado a su salida. Sin embargo, dado que todas las otras salidas, que la última cinta debe también ser conectado. Por lo tanto, esta estrategia funciona en todos los puzzles y no toma más de $n+m-1$ se mueve.

Aquí una foto de la que se aplicó a los rompecabezas que has publicado, donde los números indican el orden en los movimientos que tienen lugar en. Ya que los colores no son únicas, he utilizado la regla de que me gustaría hacer un giro sólo si sería enviar una cinta directamente para su salida y, dadas las filas de arriba, no de otras cintas que podría salir a la salida:

*Yo creo que usted puede llamar a lo que yo llamo un "twist" de un "desenrolla". He encontrado que confuso, así que he cambiado.

---

Addendum:

Basado en los descubrimientos en Calum Gilhooley comentarios y respuestas, uno puede demostrar que la estrategia es óptima. En particular, vamos a $\pi$ ser una permutación en las cintas de tal forma que si $r$ es una cinta, $\pi(r)$ es la cinta con la que inicialmente pasa a la salida de ese $r$ se supone que es. Como está más explicado en Calum la respuesta, si pasamos a través de la rejilla de arriba a abajo y escriba las transposiciones $T_i=(r_1 r_2)$ si $i^{th}$ giro que nos encontramos es la torsión de las cintas $r_1$$r_2$, $$\text{id} =T_nT_{n-1}\ldots T_2T_1\pi$$ ya que, por cada giro, que esencialmente son el intercambio de identidad de $r_1$ $r_2$ para todos los otros giros, y la idea es que al final, nos hemos deshecho de los intercambian identidades en el inicio. Es un estándar de hecho en el grupo teoría de que un $c$-ciclo es un producto de, al menos, $c-1$ transposiciones, y no es demasiado difícil, además, muestran que si $\pi$ es una permutación en $R$ elementos con $C$ ciclos, entonces es el producto de, al menos, $R-C$ transposiciones. En particular, obtenemos la siguiente caracterización:

Cualquier posición de partida puede ser resuelto en $R-C$ se mueve, y no menos.

Para demostrar la optimalidad de mi estrategia, simplemente se observa que las cintas $r_1$ $r_2$ solo interactúa si están en el mismo ciclo de $\pi$. En particular, la siguiente verdad es que nunca ha cambiado mi estrategia:

Cada cinta es, en todo momento, yendo hacia una salida correspondiente a una cinta en el mismo ciclo.

Esto es porque si $r_1$$r_2$, retorcidos en un estado satisfactorio de lo anterior, de donde se envían $r_1$ hacia su objetivo, a continuación,$r_2$, de antemano, que apunta a la meta de $r_1$, y en la hipótesis anterior, se deduce que el $r_1$ $r_2$ son de un mismo ciclo. Por otra parte, si $r_1$ inicialmente se dirigió a la salida para$r_3$, $r_1$ $r_3$ están en el mismo ciclo, y por lo tanto, por transitividad, $r_2$ $r_3$ están en el mismo ciclo, y por lo tanto, $r_2$ será después, se dirigió a la meta de una cinta en su ciclo ($r_3$).

Entonces, ante esto y el hecho de que la estrategia de funciones y asigna a no más de un giro cada cinta, está claro que los que resuelve un ciclo en $C-1$ pasos. Por lo tanto se resuelve el juego en $R-C$ pasos y por lo tanto es óptimo. La única pregunta que queda es ¿cómo óptima de asignar las entradas a las salidas cuando los colores no son distintas.