El juego de Grundy es un juego matemático estratégico para dos jugadores. Primero hay una pila de artículos. Los dos jugadores se turnan para dividir cualquiera de los montones en dos montones de diferentes tamaños. El juego termina cuando solo quedan montones de dos o un elemento, como ninguno se puede dividir en montones de diferentes tamaños. Gana el jugador que hizo el último movimiento.
Un juego que comienza con una sola pila de 8 elementos gana el primer jugador si divide la pila original en dos de 7 y 1 elementos:
jugador 1: 8 → 7+1El jugador 2 ahora puede hacer uno de tres movimientos: dividir 7 en 6 + 1, 5 + 2 o 4 + 3. En cada uno de estos casos, el jugador 1 puede devolver montones de 4 elementos y montones de tamaño 2 o menos al oponente. :
jugador 2: 7+1 → 6+1+1 jugador 2: 7+1 → 5+2+1 jugador 2: 7+1 → 4+3+1 jugador 1: 6+1+1 → 4+2+1+1 jugador 1: 5+2+1 → 4+1+2+1 jugador 1: 4+3+1 → 4+2+1+1Ahora el jugador 2 tiene que dividir una pila de cuatro objetos en 3 + 1, el jugador 1, en el futuro, dividirá 3 en 2 + 1:
jugador 2: 4+2+1+1 → 3+1+2+1+1 jugador 1: 3+1+2+1+1 → 2+1+1+2+1+1 El jugador 2 no puede hacer un movimiento y pierde.El juego se puede analizar utilizando la teoría de Sprague-Grundy . Para hacer esto, debe hacer coincidir los tamaños de los montones en el juego Grundy con los tamaños equivalentes de los montones en el juego Nim . Esta correspondencia se describe mediante la secuencia:
Tamaños de pila: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... Tamaños equivalentes de montones de Neem: 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ... (secuencia A002188 en OEIS )Usando esta correspondencia, la estrategia para jugar a Nim también se puede usar para jugar a Grundy. La cuestión de si la secuencia de valores de Nim para el juego de Grundy se vuelve periódica es un problema sin resolver. Alvin Berlekamp , John Horton Conway y Richard Guy han sugerido [1] que es periódica, aunque los primeros 235 valores encontrados por Achim Flammenkamp no lo confirman.