Tratando de encontrar el nombre de esta variante de Nim

Question

Considere este ejemplo básico de la resta-base de Nim antes de llegar a mi pregunta:

Deje $V$ representan a todos los estados válidos de un Nim pila (el número de piedras que quedan):

$V = 0,1,2,3,4,5,6,7,8,9,10$

Deje $B$ ser el límite en el número máximo de las piedras me puede quitar de la Nim pila en un solo movimiento (el mínimo es siempre al menos 1):

$B = 3$

Estrategia óptima en un juego de dos jugadores, entonces, es siempre garantizar que al final de su turno, el número de piedras en la pila es un número que se encuentra en $V$, y que es congruente a $0$ modulo $(B+1)$. Durante mi primer movimiento me quite los 2 piedras porque $8$ modulo $4$$0$.

Mi oponente elimina cualquier lugar de 1 a 3 piedras, pero no importa porque me puede entonces reducir la pila a $4$ porque $4$ modulo $4$$0$. Una vez que mi oponente se mueve, puedo tomar el resto de la pila y ganar.

Esto es sencillo, pero mi pregunta es acerca de una versión más avanzada de este, específicamente al $V$ no incluye todos los números de un rango. Algunos de final de los estados de la pila no son válidas, lo que implica que no puedo encontrar en los puestos de seguridad mediante la aplicación del modulo $(B+1)$ regla.

¿Esta variante en particular de Nim tiene un nombre que puedo mirar para profundizar en la investigación? Hay otra forma de modelo de la pila?

Answer 1

Estos son conocidos como la resta de los juegos; en general, para algunos de $S=\{s_1, s_2, \ldots s_n\}$ el juego de $\mathcal{S}(S)$ es el juego donde cada jugador puede restar cualquier elemento de $S$ a partir de una pila. (Para que su simplificado caso es el juego de $\mathcal{S}(\{1\ldots B\})$) El nim-valores de una sola pila de las posiciones en estos juegos son conocidos por ser en última instancia periódica, y hay una vinculación fenómeno que se presenta entre 0-valores y 1-valores, pero de forma genérica no hay mucho que saber acerca de estos juegos con $n\gt 2$. Berlekamp, Conway y Guy la senda de la victoria Para Su Matemática Juega tiene una sección en la resta de los juegos; lo que puedo decir, es todavía el canónica de referencia para la combinatoria, la teoría de juegos. Los Juegos de Ninguna Oportunidad colecciones también tiene alguna información en específico de la resta de los juegos, y parece un artículo sobre los juegos con los tres elementos de la resta de conjuntos se presentaron recientemente en arxiv ( http://arxiv.org/abs/1202.2986 ); que podría ser otro punto de partida decente para las referencias en la literatura.

Answer 2

Has analizado el juego correctamente. Wikipedia lo enumera como "el juego de la resta" en "Otras variaciones de Nim".