¿Es posible lograr el objetivo de este puzzle de tres en raya?

Question

Yo era de jugar Tic-Tac-Dedo del pie con mi amiga cuando me encontré con un rompecabezas. Voy a tener que poner esto en el Desconcierto de Intercambio de la Pila, pero no sé si el objetivo del rompecabezas se puede lograr. Soy consciente de que las matemáticas(s) que se incorpora, es por eso que estoy publicando aquí.

---

Rompecabezas:

Usted tiene un $3\times 3$ Tic-Tac-Dedo del pie de la junta; es decir,

$$\begin{array}{r|c} \verb|X| &\verb|O| &\verb|X|\\ \hline \verb|O| &\verb|X| &\verb|O|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array}$$

Ahora, hay que intercambiar la posición de un $\verb|X|$ e una $\verb|O|$; por ejemplo,

$$\begin{array}{r|c} \verb|X| &\verb|O| &\verb|X|\\ \hline \verb|O| &\verb|X| &\verb|O|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array}\stackrel{\nwarrow}{\leftarrow}\rm swap \ posición\implica\begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\\ \hline \verb|O| &\verb|X| &\verb|X|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{array}$$

Ahora, el Tic-Tac-Dedo del pie de la junta puede ser dividido en cuatro secciones $A, B, C$ $D$ tal que

$$\begin{align}\color{red}{A}&=\begin{array}{c|c|} \verb|X| &\verb|O|\\ \hline \verb|O| &\verb|X|\\ \hline \end{array} \qquad \begin{array}{r|c} \color{red}{\verb|X|} &\color{red}{\verb|O|} &\verb|O|\\ \hline \color{red}{\verb|O|} &\color{red}{\verb|X|} &\verb|X|\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{de la matriz} \\ \color{darkorange}{B}&=\begin{array}{|c|c} \verb|O| &\verb|O|\\ \hline \verb|X| &\verb|X|\\ \hline \end{array} \qquad \begin{array}{r|c} \verb|X| &\color{darkorange}{\verb|O|} &\color{darkorange}{\verb|O|}\\ \hline \verb|O| &\color{darkorange}{\verb|X|} &\color{darkorange}{\verb|X|}\\ \hline \verb|X| &\verb|O| &\verb|X|\\ \end{de la matriz} \\ \color{blue}{C}&=\begin{array}{c|c|} \hline \verb|O| &\verb|X|\\ \hline \verb|X| &\verb|O|\\ \end{array} \qquad \begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\\ \hline \color{blue}{\verb|O|} &\color{blue}{\verb|X|} &\verb|X|\\ \hline \color{blue}{\verb|X|} &\color{blue}{\verb|O|} &\verb|X|\\ \end{de la matriz} \\ \color{verde}{D}&=\begin{array}{|c|c} \hline \verb|X| &\verb|X|\\ \hline \verb|O| &\verb|X|\\ \end{array} \qquad \begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\\ \hline \verb|O| &\color{green}{\verb|X|} &\color{green}{\verb|X|}\\ \hline \verb|X| &\color{green}{\verb|O|} &\color{green}{\verb|X|}\\ \end{array}\end{align}$$

Usted puede rotar estas secciones $k\cdot 90^\circ$ para algún número natural $k$. Por supuesto, el número de $\verb|X|$s y $\verb|O|$s en estas secciones variará dependiendo de cuáles son rotados y cuáles no lo son.

Objetivo: Intentar hacer la junta en lo que es en la caja de arena por encima.

---

Pregunta:

Esto es incluso posible? Yo no lo creo... pero no sé cómo demostrarlo. Tengo un ordenador, pero no tengo el programa de estos tipos de cosas. He probado el rompecabezas de mí mismo un montón de veces, pero no he resuelto. Sería muy apreciado si alguien puede averiguar si es posible o no.

Gracias de antemano.

P. S. Hay otras entradas relacionadas, pero no son exactamente lo que yo estoy buscando.

Answer 1

Uno puede hacer incluso mejor que eso. De hecho, usted puede colorear las plazas en su junta directiva en 9 diferentes colores y permutar ellos de cualquier manera, y usted todavía puede volver a la configuración original por una secuencia de rotaciones de los cuatro $2\times 2$ casillas de las esquinas.

A saber: Esta secuencia de movimientos

1. Gire la esquina superior derecha de las agujas del reloj
2. A continuación, la esquina inferior izquierda hacia la derecha
3. Gire la esquina superior derecha hacia la izquierda
4. A continuación, la esquina inferior izquierda hacia la izquierda

(en el grupo de teoría del lenguaje, este es un colector) tiene el efecto neto de permuting sólo la fila del medio de forma cíclica. Es fácil ver que podemos obtener cualquiera de las tres plazas que queramos en la fila del medio, si no nos importa lo que sucede a los otros seis, por lo que cualquier 3-ciclo de plazas puede ser realizado como un conjugado de este colector.

Por lo tanto (desde los 3-ciclos de generar la alternancia de grupo) podemos hacer cualquier incluso permutación de las plazas.

Sin embargo, un simple cuarto de vuelta de una de las esquinas es un extraño permutación, por lo que si tenemos que resolver a partir de un estado raro, simplemente gire una de las esquinas y luego resolver el resultado de que incluso los estados.

QED. Por lo tanto, la respuesta a la pregunta original es sí, se puede.

---

Extras

Extra: los símbolos con orientación

Cuánto de una restricción es que si uso el 9 símbolos que han orientación tal que se puede decir si uno de ellos es al revés?

Si tenemos puntos en dos esquinas de cada mosaico, como este:

    *   |   * | *
      * | *   |   *
    ----+-----+----
      * | *   |   *
    *   |   * | *
    ----+-----+----
    *   |   * | *
      * | *   |   *

a continuación, cada una de las hojas se mueven el patrón de puntos sin cambios, por lo que sólo hay dos orientaciones legales de cada azulejo en cada posición. Además, cada movimiento es un incluso permutación de los puntos (a saber, dos de 4 ciclos), por lo que no es posible voltear un solo azulejo al revés.

Pero podemos cambiar cualquier incluso el número de fichas boca abajo. La repetición de esta secuencia (conocido Rubik aficionados como la Y-colector) dos veces:

1. Inferior izquierda hacia la derecha
2. Inferior derecha hacia la izquierda
3. Inferior izquierda hacia la izquierda
4. Inferior derecha de las agujas del reloj

el efecto neto es el de flip cuatro baldosas al revés. Hacer que de nuevo desde el otro lado de la junta, y va a voltear tres de ellos de nuevo, y una quinta vez, para un efecto neto de un tirón dos baldosas. La conjugación de esto te permitirá dar la vuelta a un número par de azulejos.

Teniendo en cuenta orientaciones, hay por lo tanto, $9!\cdot 2^8=92{,}897{,}280$ posiciones válidas, porque la orientación de la última ficha se determina una vez que hemos elegido orientaciones para ocho de ellos.

---

Extra: los símbolos con orientación más vertical restricción

Qué configuraciones son posibles si se requiere que el orientable símbolos deben estar en posición vertical en el final, incluso si la plaza no está en el lugar correcto?

La imagen con los puntos anteriores hace claro que lo que no se puede mover una ficha entre una "X" la posición y una posición "O" y mantener su orientación. Así que el 5 de "X" las baldosas deben ser permutados entre sí, como debe de 4 "O" azulejos. Pero hay más restricciones? A priori, podría ser que algunas de las permutaciones que siga esta regla sólo puede ser realizada con un extraño número de arriba-abajo de las baldosas.

Supongamos que en la inicial posición en la que nos coloque dos puntos en diagonal en cada baldosa, como el anterior, pero ahora el "superior" punto rojo y la "baja" punto verde. Cada movimiento se convierte en el color de la "parte superior" de punto para dos de los azulejos que se mueve. Así que una vez que hemos metido todo en el justo lugar, hay una incluso el número de azulejos que están al revés en relación a su orientación original. Y sabemos que podemos arreglar eso!

Así que todos los $5!\cdot 4! = 2{,}880$ "vertical" permutaciones de las "X" y "O" baldosas por separado se pueden resolver, teniendo en cuenta la orientación.

Answer 2

Esta es una elaboración de Exodd la respuesta. Escribí una secuencia de comandos de python para comprobar si es posible obtener a partir de cualquier junta con exactamente $5$ X para cualquier otra junta con exactamente $5$ X como se había conjeturado, y la respuesta es "sí". Resulta que no siempre puedes hacer en $3$ se mueve, sin embargo. A veces se necesita $4$.

La siguiente secuencia de comandos utiliza el algoritmo Floyd-Warshall para encontrar la longitud de la ruta más corta entre cada par de placas. La distancia entre dos tablas se inicializa a $200,$ cual es efectivamente $\infty$, ya que sólo hay $126$ tablas; si se puede llegar de uno a otro, que sin duda puede llegar en $125$ movimientos o menos.

from itertools import combinations
import numpy as np

def A(tic):
    tac = tic[:]
    tac[0]=tic[3]
    tac[1]=tic[0]
    tac[3]=tic[4]
    tac[4]=tic[1]
    return tac

def A2(tic):
    return A(A(tic))

def A3(tic):
    return A(A2(tic))

def B(tic):
    tac = tic[:]
    tac[1]=tic[4]
    tac[2]=tic[1]
    tac[4]=tic[5]
    tac[5]=tic[2]
    return tac

def B2(tic):
    return B(B(tic))

def B3(tic):
    return B(B2(tic))

def C(tic):
    tac = tic[:]
    tac[3]=tic[6]
    tac[4]=tic[3]
    tac[6]=tic[7]
    tac[7]=tic[4]
    return tac

def C2(tic):
    return C(C(tic))

def C3(tic):
    return C(C2(tic))

def D(tic):
    tac = tic[:]
    tac[4]=tic[7]
    tac[5]=tic[4]
    tac[7]=tic[8]
    tac[8]=tic[5]
    return tac

def D2(tic):
    return D(D(tic))

def D3(tic):
    return D(D2(tic))

def makeBoards():
    boards= []
    for c in combinations(range(9), 5):
        a=9*['0']
        for x in c:
            a[x]='1' 
        boards.append(a)
    return boards

def initialize():
    boards = makeBoards()
    answer = 200*np.ones((126,126), dtype = np.int)
    for n, brd in enumerate(boards):
        for F in (A,B,C,D,A2,B2,C2,D2,A3,B3,C3,D3):
            m=boards.index(F(brd))
            answer[n,m]=1
    for n in range(126):
        answer[n,n]=0
    return answer

def main():
    dist = initialize()
    vertices = range(126)
    for k in vertices:
        for i in vertices:
            for j in vertices:
                if dist[i,j] > dist[i,k] + dist[k,j] :
                    dist[i,j] = dist[i,k] + dist[k,j] 
    for n in vertices:
        for m in range(n+1,126):
            if dist[n][m]==200:
                print("Can't get to ", m," from ", n)
    print(m, list(dist.flatten()).count(m))

if __name__=='__main__':
    main()

Esto produce la salida:4 1382 lo que significa que la distancia máxima se $4$ y $1382$ de las parejas se encontró que requieren $4$ se mueve. Por supuesto, si se tarda $4$ se mueve a de $X$ $Y$también se lleva a $4$ se mueve a de$Y$$X,$, por lo que realmente sólo hay $691$ de estas parejas. No así muchos de $\binom{126}{2}.$

Answer 3

$$\begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\ \hline \verb|O| &\verb|X| &\verb|X|\ \hline \verb|X| &\verb|O| &\verb|X|\ \end{matriz} \to\begin{array}{r|c} \verb|X| &\verb|O| &\verb|O|\ \hline \verb|O| &\verb|X| &\verb|X|\ \hline \verb|X| &\verb|X| &\verb|O|\ \end{matriz} \to\begin{array}{r|c} \verb|X| &\verb|O| &\verb|X|\ \hline \verb|O| &\verb|O| &\verb|X|\ \hline \verb|X| &\verb|X| &\verb|O|\ \end{matriz} \to\begin{array}{r|c} \verb|X| &\verb|O| &\verb|X|\ \hline \verb|O| &\verb|X| &\verb|O|\ \hline \verb|X| &\verb|O| &\verb|X|\ \end{matriz} $ es posible demostrar que 3 es el número mínimo de movimientos necesarios en este caso.