Un Juego Combinatorio

Question

El siguiente es un juego combinatorio que he leído en una olimpiada matemática de la preparación de libros de hace algún tiempo. He olvidado las reglas exactas de este juego, pero la idea general de que el problema va algo como esto:

Dos jugadores a y B se turnan para colocar contadores en un 5 por 5 grid. Jugador siempre va primero. En cada turno, el jugador tiene la opción de colocar ya sea 1, 2 o 3 contadores en la red. El ganador del juego es la persona que tiene incluso una* número de fichas después de todos los cuadrados de la cuadrícula se han utilizado.

*Debido al hecho de que la primera vez que leí este problema hace varios años, soy incapaz de recordar si el ganador del juego fue el que con un par o un número impar de fichas al final del juego.

Sin embargo, estoy bastante seguro de que no fue una estrategia ganadora para el jugador B. no he sido capaz de demostrar por qué es que debe ser así, para cualquiera de los casos o encontrar la declaración original del juego. Alguien ha visto este problema antes? ¿Alguien tiene alguna idea de cómo encontrar una estrategia ganadora para cualquiera de los dos casos? Cualquier ayuda sería muy apreciada.

Answer 1

Persona $B$ tiene una estrategia ganadora como las reglas del juego ahora (usted gana si usted tiene incluso el número de piedras en la final). Un $1$ siempre es contestada por un $3$$3$$1$, pero un $2$ es atendido por una $1$ o $3$, dependiendo de cuántas plazas están a la izquierda. Supongo que la más fácil de criterio para hacer mentalmente aquí es "lo que hace que el número de plazas a la izquierda congruente a $0$ o $1$ modulo $4$".

Si es tu turno, y usted tiene un número par de piedras en el tablero, entonces usted pierde si no se $1$ o $4$ vacantes de plazas izquierda modulo $8$, y si usted tiene un número impar de piedras en el tablero, se pierde si no se $0$ o $5$ plazas izquierda modulo $8$.

Por ejemplo, si usted está en $0$ plazas izquierda modulo $8$ y usted tiene un número impar de piedras en el tablero, entonces el juego ha terminado, y usted ha perdido, o se tienen que colocar las piedras. Si el anticipo $2$ piedras, luego de que su oponente se pone $1$, y estás en impar piedras, $5$ modulo $8$ plazas de la izquierda. Si el anticipo $1$ o $3$, entonces usted tiene un número par de piedras en el tablero, y tu oponente puede hacer es $4$ plazas izquierda, modulo $8$.

Los otros tres casos tienen que ser registrados como también, por supuesto.

Habiendo $0$ piedras en el tablero (que es aún) y $25\equiv 1$ plazas de la izquierda es una posición perdedora, y si $A$ comenzó en una de las cuatro posiciones perdedoras, $B$ puede forzar a él sin importar lo $A$ intenta.

Answer 2

Supongo que es su turno y ya hay $x$ fichas en la cuadrícula; por otra parte, el uso de $e/o$ para indicar si el número de su token ya en la cuadrícula es $e$ven o $o$dd.

Por ejemplo, $24e$ significa que hay 24 contadores en la red y que han echado un número par. El solo se mueven a la izquierda es el lugar de $1$ token: $24e \rightarrow 25o$ y ha perdido. A continuación, $24e$ $L$osing posición. En resumen:

$24e$ $L$ .

$24o$ $W$entrada posición: poner un token y cerrar el juego en $25e$.

$23e$ $W$ : poner dos fichas y cerrar el juego en $25e$.

$23o$ $W$ : puesto un token, obligando a su rival a $24e$ que es una posición perdedora.

$22e$ $W$ : poner dos fichas, forzando al rival $24e$.

$22o$ $W$ : poner tres token y obtenga $25e$.

$21e$ $L$ : no importa la forma de jugar, el rival será en $22o$ (22 fichas en la red, y ella tiene un número impar) o $23o$ o $24o$ cuales son todas las de ganar posiciones para ella.

$21o$ $W$ : colocar tres fichas, forzando al rival $24e$.

$20e$ $W$ : puesto un token, forzando al rival $21e$.

$20o$ $L$ : no importa la forma de jugar, el rival será en $21o$ o $22o$ o $23o$.

$19e$ $W$ : puesto un token, forzando al rival $20o$.

$19o$ $W$ : poner dos fichas, forzando al rival $21e$.

$18e$ $W$ : colocar tres fichas, forzando al rival $21e$.

$18o$ $W$ : poner dos fichas, forzando al rival $20o$.

$17e$ $W$ : colocar tres fichas, forzando al rival $20o$.

$17o$ $L$ : no importa la forma de jugar, el rival será en $18e$ o $19e$ o $20e$.

$16e$ $L$ : no importa la forma de jugar, el rival será en $17e$ o $18e$ o $19e$.

$16o$ $W$ : puesto un token, forzando al rival $17o$.

El resto del patrón es claro: la próxima perder posiciones se $13e, 12o, 9o, 8e, 5e, 4o, 1o, 0e$. Jugador abre el juego en $0e$ así que comienza en una posición perdedora. Jugar de manera óptima, B se garantiza una victoria.

(Nota: esta técnica se denomina " inducción hacia atrás. Recuerdo similar de las preguntas que se hacen en la SE, pero no puedo encontrar una adecuada duplicado. Ver f.yo Trate de no conseguir la última pieza, pero con una torcedura! [La Teoría De Juegos])

Answer 3

Vamos a ver en el juego del Jugador Un punto de vista. En cualquier etapa en el juego, hay $N$ de las celdas de la cuadrícula de la izquierda abierta, y Jugador de Un estado puede ser descrito como "Par" o "Impar", dependiendo de si él ha representado un par o impar el número de ocupados de las células. (Como mencioné en un comentario debajo de la OP, prefiero pensar en el juego de take-away formato, con cada jugador extracción de $1$, $2$, o $3$ contadores de un montón de $25$, pero me estoy pegando con el OP descripción de evitar cualquier confusión.) Obviamente, el Jugador a Gana si no hay ninguna celda abierta y él está en el estado, y se Pierde si no hay ninguna celda abierta y él está en el estado raro.

En general, Un Jugador puede permanecer en el estado que se encuentra actualmente en jugando $2$ contadores, o revertir su estado jugando bien $1$ o $3$ contadores. Jugador permanecerá en ese estado, independientemente de cuántos contadores de su oponente juega. Esto hace que sea posible crear una tabla de Win/Loss resultados para:

$$\pmatrix{&0&1&2&3&4&5&6&7&8&9&10&11&12&\cdots\\ E&W&L&W&W&L&W&W&W&W&L&W&W&L&\cdots\\ O&L&W&W&W&W&L&W&W&L&W&W&W&W&\cdots\\}$$

Por ejemplo, la siguiente columna, para $N=13$, es una Victoria para el estado, debido a que Un Jugador puede jugar un contador, tomarse a sí mismo a la Extraña estado, por lo tanto aterrizaje en $(11,O)$, $(10,O)$, o $(9,O)$, todos los cuales están Ganando posiciones, después de que el Jugador B juega $1$, $2$, o $3$ contadores. Pero $(13,O)$ es una Pérdida: Si Un Jugador juega $2$ contadores, el Jugador B le puede enviar a Perder el estado de $(8,O)$ jugando $3$ contadores, mientras que si él juega $1$ o $3$ contadores, su oponente le puede enviar a Perder el estado de $(9,E)$ jugando $3$ o $1$ contadores. (Nota: El primer par de columnas de la tabla tienen pocas opciones a considerar.)

Una inspección casual de la tabla se observa una regularidad en las entradas, y un poco de reflexión se concluye que el patrón va a persistir: hay repetición con período de $8$. En consecuencia, para el OP del juego, el Jugador a la apertura de la posición es $(25,E)$, que es una Pérdida, ya que $25\equiv1$ mod $8$ $(1,E)$ es una Pérdida.

Nota: Si se invierte el criterio para ganar para jugar un Extraño número de contadores, resulta que la tabla simplemente intercambia las dos filas. En ese caso, el juego a partir de $N=25$ es una Victoria para el Jugador A.