¿Ganar un juego restringido de Nim?

Existe una regla general, la regla mex , para calcular los valores de Grundy (o montones de Nim equivalentes) en juegos imparciales similares a Nim. Los movimientos que tienes disponibles son tomar un palo o tomar dos palos. Estos conducen a posiciones más pequeñas cuyos valores ya conoce. Haz una lista de esos valores y encuentra el primer número de$\{0, 1, 2, 3\dots \}$que no puedes alcanzar. Este valor mínimo excluido (mex) es el que desea.

Para una pila de cero el valor es$0$

Para una pila de uno, el único movimiento es a cero, el valor$0$se excluye por lo que el valor es$1$

Para una pila de dos, los movimientos son a uno.$(1)$y cero$(0)$así mex es$2$

Para una pila de tres hay movimientos a dos$(2)$y uno$(1)$así mex es$0$

Para una pila de cuatro hay movimientos a tres$(0)$y dos$(2)$así mex es$1$

$\dots$

Los valores de Grundy cuando se combinan las posiciones se suman usando la regla de adición de Nim que conoce.

Hay una extensa discusión sobre juegos imparciales de varios tipos en Winning Ways (Berlekamp, ​​Conway y Guy).

Para una pila, el$0$posiciones son los múltiplos de$(2+1)$, y los valores G deben ser todos$0,1$o$2$, entonces$G(n)=(n \mod 3)$. La teoría de la suma de Nim luego dicta los valores de G para el juego con varias pilas.