Recientemente he descargado un juego para mi de TI NSPIRE CX llamado Completar el Cuadrado. http://www.ticalc.org/pub/nspire/lua/games/. Los jugadores se turnan para colocar las piedras en un período de seis por seis junta. Un jugador tiene piedras azules, el otro jugador tiene el rojo de las piedras. Sólo una piedra puede ser un cuadrado. Los jugadores continúan de esta manera, la colocación de piedras hasta que una persona piedras que forman las cuatro esquinas de un cuadrado. Ese jugador es el ganador. Mi pregunta es esta: ¿Es posible llene completamente el tablero de manera que el juego termina en empate? Claramente esto es cierto para un 2x2 de la junta, y, con un poco de pensamiento, uno puede ver esto también es cierto para un tablero de 3x3. Está allí y es una manera fácil de determinar si es o no un no de la junta puede ser un empate? ¿Qué acerca de NxM tablas? Creo que esta pregunta podría tener algo que ver con la teoría de grafos, así que deberá presentar como tal, pero se sienten libres para moverlo si usted cree que pertenece a otra parte. Hago esta pregunta porque yo quería encontrar una estrategia ganadora, y uno claramente debe existir si el juego nunca puede terminar en un empate. Además, debe ser un 1er jugador ganar, porque si existiera un segundo jugador estrategia ganadora, el 1er jugador podría hacer un movimiento aleatorio para su primer turno y, a continuación, siga el segundo jugador de la estrategia para el resto del juego.
Respuesta
¿Demasiados anuncios?
De que la mayoría sabe la respuesta a esta pregunta, pero no del todo.
Voy a ignorar la condición de que en un verdadero completa el cuadrado de juego, el número de azul y rojo de las piedras en el final debe ser igual o desactivada por uno. En lugar de ello, sólo podemos ver una arbitraria para colorear de la cuadrícula que evitar cuadrados con esquinas del mismo color. Si existe, entonces puede ser balanceada o casi equilibrada, y probablemente podemos hacer es equilibrada por juguetear con ella un poco. (Después de todo, muy desequilibrado colorantes debería tener muchas más plazas cuyas esquinas son del mismo color.)
He aquí uno de los resultados que es relativamente fácil de probar: si $M + 2N \le 36$ (o, por simetría, si $N + 2M \le 36$), a continuación, un squareless colorear existe en un $M \times N$ junta. Por ejemplo, un squareless colorear existe en un $12 \times 12$ cuadrícula.
Para crear este tipo de colorante, empezar con la siguiente coloración de los enteros $1, 2, \dots, 34$ (que se encuentra por Chvátal en 1970) $$ \color{blue}{1}\,\color{red}{2}\,\color{blue}{3}\,\color{red}{4}\,\color{red}{5}\,\color{red}{6}\,\color{blue}{7}\,\color{blue}{8}\,\color{blue}{9}\,\color{red}{10}\,\color{blue}{11}\,\color{red}{12}\,\color{red}{13}\,\color{blue}{14}\,\color{red}{15}\,\color{red}{16}\,\color{red}{17}\,\color{blue}{18}\,\color{blue}{19}\,\color{blue}{20}\,\color{red}{21}\,\color{blue}{22}\,\color{blue}{23}\,\color{red}{24}\,\color{blue}{25}\,\color{red}{26}\,\color{red}{27}\,\color{red}{28}\,\color{blue}{29}\,\color{blue}{30}\,\color{blue}{31}\,\color{red}{32}\,\color{blue}{33}\,\color{blue}{34} $$ en el que no hay una progresión aritmética de longitud $4$ tiene el mismo color. Siguiente, la etiqueta de los cuadrados de la cuadrícula de números enteros en la siguiente patrón:
\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & \cdots \\ 3 & 4 & 5 & 6 & 7 & \cdots \\ 5 & 6 & 7 & 8 & 9 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}
En esta etiqueta, $d \times d$ cuadrado cuya esquina superior izquierda está etiquetada $a$ contendrá las etiquetas de $a+d, a+2d, a+3d$ en otras de sus esquinas. Así que si la transferencia de la coloración de los enteros a una coloración de la red mediante el uso de esta etiqueta, a continuación, ninguna plaza será monocromática, que nos muestra cómo conseguir un empate.
(La condición de $M+2N \le 36$ garantiza que sólo se necesitan los números enteros $1,2,\dots,34$ para el etiquetado. Esto es importante porque no hay para colorear de los enteros $1,2,\dots,35$ con la misma propiedad.)
Para la plaza de redes, además de saber que (de nuevo, ignorando el número de piedras de cada color), un empate es posible en un $14 \times 14$ cuadrícula, pero no en un $15 \times 15$ cuadrícula. Lamentablemente, no hay construcción como "bonito" como el de arriba: es sólo que en este papel, el $14 \times 14$ $15 \times 15$ preguntas son verificados por el SAT solver.
Esto todavía deja abierta la cuestión de qué sucede cuando se juega en largo y delgado rectángulos. Por ejemplo, en una $3 \times N$ junta directiva, un empate es posible para todos los $N$: sólo ampliar el colorante \begin{array}{ccccc} \color{red}{\bullet} & \color{blue}{\bullet} &\color{red}{\bullet} &\color{blue}{\bullet} &\cdots \\ \color{red}{\bullet} & \color{blue}{\bullet}&\color{red}{\bullet} &\color{blue}{\bullet} &\cdots \\ \color{blue}{\bullet} & \color{red}{\bullet} &\color{blue}{\bullet} &\color{red}{\bullet} &\cdots \end{array} tan lejos como quieras. Es esto posible en un $4 \times N$ junta? Muy posiblemente. En un $13 \times N$ junta? Es casi seguro que no.
