Demostrar que un juego de Tic-Tac-Toe juega en el toro nunca puede terminar en un empate. (Gráfico teórico de soluciones únicas.)

Question

He aquí un problema que he asignado a mi teoría de grafos la clase. La única salvedad es que me insistió en que sus soluciones estén completamente gráfico teórico. Tener diversión con ella.

Demostrar que un juego de Tic-Tac-Toe juega en el toro nunca puede terminar en un empate.

La idea es simular el juego (toroidal Tic-Tac-Toe) como $2$-edge-juego de colorear en un determinado gráfico bipartito. Una victoria aquí equivaldría a saturar un único (tipo específico) vértice con todos los bordes de un color.

Esto no tiene nada que ver en absoluto con nuestra estrategia o juego perfecto. El estándar de normas de Tic-Tac-Toe aplicar (horizontal, vertical, y diagonal gana), excepto que en el toro hay cuatro adicionales diagonal gana.

Como un ejemplo, si uno coordiantes los cuadrados de las Tic-Tac-Dedo del pie de la junta como $(i,j)$$1\le i,j\le 3$, entonces el conjunto $\{(1,2),(2,3),(3,1)\}$ constituye una diagonal de ganar en el toro. (Tenga en cuenta que estamos suponiendo que el Tic-Tac-Dedo del pie de la junta cubre la totalidad del toro.)

Recuerde que estamos pidiendo que la prueba será puramente de teoría de grafos, a pesar de que sería mucho más fácil sólo la lista de todos los posibles estrategia y nota que no hay empates que se produzcan. (PS: yo tengo una solución para este problema).

Answer 1

Vamos a volver a interpretar el tic-tac-toe juego en términos de borde para colorear para los dos gráficos asociados.

Tenga en cuenta que hay $12$ total maneras de ganar en el toro. Hay $3$ líneas horizontales y $3$ líneas verticales. De forma análoga, hay $3$ líneas diagonales y $3$ anti-líneas diagonales. Cada uno horizontal/vertical de la línea de par de forma exclusiva determina una celda a través de su intersección. Por el contrario, cada celda pertenece precisamente a uno de esos pares. El mismo contiene a la diagonal/anti-diagonal pares.

Vamos a no ser $6$ vértices en nuestro primer gráfico, uno para cada vertical/horizontal de la línea. Une cada vértice vertical a horizontales de cada vértice. El resultado es la completa bipartito gráfico de $K_{3,3}$ donde cada arista corresponde a una celda de la red de juego. Construir el segundo gráfico a través del mismo procedimiento para la diagonal/anti-líneas diagonales.

Ahora el juego puede ser interpretado como $2$-colorear los bordes de los gráficos (donde cada movimiento, los colores de un borde en ambos gráficos). Ganar el juego corresponde a saturar un vértice en uno de los dos gráficos con los bordes del mismo color. La clave ahora es la nota de los dos siguientes hechos:

1. Si existe un perfecto maridaje con los bordes del mismo color en una gráfica, entonces esto implica necesariamente la existencia de un vértice saturado con el mismo color en el otro gráfico.

2. Si cada vértice de $K_{3,3}$ es adyacente a los bordes de color, a continuación, no existe necesariamente un perfecto maridaje con los bordes del mismo color.

No es muy difícil demostrar que los dos anteriores hechos y no voy a hacerlo aquí (aunque la prueba de que no tengo todavía requiere un poco de caso-la comprobación, si alguien tiene una elegante prueba de los dos hechos anteriores, por favor compartir conmigo). La interpretación general es que el juego en el toro trae en una dualidad entre vertical/horizontal de la gana y diagonal/anti-diagonal gana. No ganar una manera en que las fuerzas de ganar de otra manera.

Answer 2

No estoy demasiado seguro de lo que constituye puramente gráfico teórico. Aquí es una prueba de que no los casos de uso.

Vamos a demostrar que, dado 5 puntos, debe ser de 3 que forman una línea.

Orden de los puntos de $p_i$ (en cualquier orden que desee). Considere la posibilidad de que el par sabio diferencia de puntos de $p_i - p_ j$$i> j$, Tomado del modulo 3. Hay 5 puntos por ende, de 10 pares, pero sólo el 9 posibilidades para su diferencia, por lo tanto 2 pares de diferencias debe ser el mismo.

Si las 2 parejas comparten un punto en común, debe ser el punto medio que es común, por lo tanto tenemos 3 puntos en una línea y hemos terminado.

Si los 2 pares no comparten un punto en común, tenemos un paralelogramo. Mediante la aplicación de un cambio de base y de la traducción, podemos suponer que WLOG que los puntos son los (1,1) (1,2) (2,1) (2,2). Ahora está claro que no importa donde el quinto punto, hemos de tener siempre una línea. Por lo tanto hecho.

Answer 3

Bueno, voy a publicar esta solución, de todos modos, aunque no es tan buena. Usted puede encontrar que es útil para tener algunas plumas coloreadas a mano a medida que lee.

Considerar las nueve plazas de la tic-tac-dedo del toro como los vértices de un gráfico de $G$. Cada cuadrado es adyacente a todos los demás de la plaza, ya sea horizontalmente, verticalmente o en diagonal, de modo que si queremos dibujar un borde entre todos los vértices correspondientes a las aristas adyacentes, nosotros tenemos la gráfico de $K_9$. Vamos a utilizar C para denotar un borde que es horizontal o vertical, y D para un borde diagonal. (C podría soportar para Cartesiano; yo no podía pensar mejor las palabras.) Supongamos que el juego ha terminado, por lo que cada vértice está marcado con una X o con un O. Nos va a llamar a un borde amable si une dos X o dos O vértices, y otra cosa la llamamos hostil.

El Color de los bordes de nuestra $K_9$ como sigue: todos los amistosos C y hostil D los bordes son de color rojo, y el resto de los bordes (hostil C y amistoso D) son de color azul. Ahora se sabe que el Ramsey número de $K(3,3)$ es $6 \le 9$ y por lo tanto nuestra $K_9$ debe contener un triángulo rojo o un triángulo azul.

Supongamos que contiene un triángulo azul. El triángulo rojo caso es isomorfo, ya que aquí es un isomorfismo que intercambiadores C y D tipo de ganado:

123    195
456 -> 843
789    627

Considere el triángulo azul. Por la paridad, debe ser que un número impar de estos 3 son los bordes de usar (por lo tanto de tipo D). Si todos los bordes son amables D, tenemos tres X o tres en la misma diagonal, y estamos hecho. De lo contrario, contiene dos hostil C bordes y un amistoso D. Este debe corresponder a una configuración como:

...
X..
OX.

hasta el isomorfismo. Pero cualquier consejo que contiene esta configuración debe tener una posición ganadora. Por si tratamos de llenar en el resto de los cuadros para evitar cualquier jugador ganador, nos vemos obligados a hacer

...    ..O    ..O    .OO
X.. -> X.. -> XX. -> XXO
OX.    OX.    OX.    OO.

y vemos que después de todo no podemos evitar una posición ganadora.

De hecho, podemos decir más: $K(3,4) = 9$ por lo que la junta debe contener un triángulo rojo o un azul $K_4$. Pero suponiendo que un monocromático $K_4$ no parece hacer las cosas más fáciles, de un triángulo.

Answer 4

Considerar el bipartito gráfico de $G$ con desdoblamiento $V(G)=\mathcal S\cup\mathcal W$ donde $\mathcal S$ se compone de la $9$ plazas $s_i$ ($1\le i\le 9$) del Tic-Tac-Dedo del pie de la junta, y $\mathcal W$ se compone de la $12$ triples $\{s_i,s_j,s_k\}$ que representan las posiciones ganadoras. Tenga en cuenta que cada cuadrado tiene un grado $4$, mientras que cada uno de los ganadores de la triple tiene un grado $3$.

Supongamos que tenemos un $2$-borde para colorear que corresponde a una partida termina en empate. Supongamos que el Jugador B (el segundo jugador a ir) tiene color de sus bordes de color azul, y considerar el "azul" gráfico, denotado $\mathcal B$. Para mayor comodidad, cambiar el nombre de las plazas en el gráfico $\mathcal B$$b_1,b_2,b_3,b_4$. Claramente $\mathcal B$ tiene 16 bordes desde $deg_{\mathcal B}(b_i)=4$$1\le i\le 4$.

Observar que $1\le deg_{\mathcal B}(T)\le 2$ todos los $T\in \mathcal W$, ya que el $deg_{\mathcal B}(T)=0$ indica una victoria para el Jugador a, y $deg_{\mathcal B}(T)=3$ indica una victoria para el Jugador B. Pero esto implica que existe $T^*\in\mathcal W$$deg_{\mathcal B}(T^*)=2$. De hecho, de lo contrario gráfico de $\mathcal B$ sólo $12$ bordes, una contradicción. Sin pérdida de generalidad, escribir $T^*=\{b_1,b_2,a\}$ donde $a$ es un cuadrado jugado por el Jugador A. Deje $T_1,T_2,T_3\in \mathcal W$ ser los otros tres triples que contengan $a$.

Ahora, considere el subgrafo de $\mathcal B$ inducida en el set $\{b_1,b_2,b_3,b_4,T^*,T_1,T_2,T_3\}$. Este gráfico debe tener al menos $5$ bordes, ya $deg_{\mathcal B}(T^*)=2$$deg_{\mathcal B}(T_i)\ge 1$$1\le i\le 3$. Por lo tanto existe $b_j$$deg_{\mathcal B}(b_j)\ge 2$.

Pero ahora, volviendo a la gráfica de $G$, esto crea un $4$ciclo de con $b_j$ $a$ antipodal vértices. (Recordemos que $a$ es adyacente a todos los de $T^*,T_1,T_2,T_3$.) Esta es nuestra última contradicción, ya que cualquiera de las dos plazas de la Tic-Tac-Dedo del pie de la junta de determinar un único ganador triple.