.jpg/1280px-Stacks_of_Canadian_Coins_(16269886909).jpg)
El juego de Grundy es un juego matemático de estrategia para dos jugadores. La configuración inicial es un único montón de objetos y los dos jugadores se turnan para dividir un único montón en dos montones de diferentes tamaños. El juego termina cuando solo quedan montones de tamaño dos o más pequeños, ninguno de los cuales se puede dividir de forma desigual. El juego suele jugarse como un juego normal , lo que significa que gana la última persona que puede realizar un movimiento permitido.
Una partida normal que comienza con un único montón de 8 es una victoria para el primer jugador, siempre que comience dividiendo el montón en montones de 7 y 1:
Jugador 1: 8 → 7+1
El jugador 2 tiene ahora tres opciones: dividir el montón de 7 en 6 + 1, 5 + 2 o 4 + 3. En cada uno de estos casos, el jugador 1 puede asegurarse de que en el siguiente movimiento le devuelva a su oponente un montón de tamaño 4 más montones de tamaño 2 y más pequeños:
Jugador 2: 7+1 → 6+1+1 Jugador 2: 7+1 → 5+2+1 Jugador 2: 7+1 → 4+3+1Jugador 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+1
Ahora el jugador 2 tiene que dividir el montón de 4 en 3 + 1, y el jugador 1 posteriormente divide el montón de 3 en 2 + 1:
Jugador 2: 4+2+1+1 → 3+1+2+1+1Jugador 1: 3+1+2+1+1 → 2+1+1+2+1+1El jugador 2 no tiene más movimientos y pierde.
El juego se puede analizar utilizando el teorema de Sprague-Grundy . Esto requiere que los tamaños de montón del juego se asignen a tamaños de montón nim equivalentes . Esta asignación se captura en la Enciclopedia en línea de secuencias de enteros como OEIS : A002188 :
Tamaño del montón: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...Montón Nim equivalente: 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ...
Usando este mapeo, la estrategia para jugar el juego Nim también puede ser usada para el juego de Grundy. Si la secuencia de valores nim del juego de Grundy alguna vez se vuelve periódica es un problema sin resolver. Elwyn Berlekamp , John Horton Conway y Richard Guy han conjeturado [1] que la secuencia eventualmente se vuelve periódica, pero a pesar del cálculo de los primeros 2 35 valores por Achim Flammenkamp, la cuestión no ha sido resuelta.