El juego de Grundy es un juego matemático de estrategia para dos jugadores. La configuración inicial es un solo montón de objetos, y los dos jugadores se turnan para dividir un solo 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 manera desigual. El juego generalmente se juega como un juego normal , lo que significa que gana la última persona que pueda hacer un movimiento permitido.
Ilustración
Un juego de juego normal que comienza con un solo 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 ahora tiene 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 próximo 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 + 1al jugador 2 no le quedan movimientos y pierde
Teoría matemática
El juego se puede analizar mediante el teorema de Sprague-Grundy . Esto requiere que los tamaños de pila del juego se asignen a tamaños de pila 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 de 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 se puede usar para el juego de Grundy. Si la secuencia de valores nim del juego de Grundy llega a ser periódica es un problema sin resolver. Elwyn Berlekamp , John Horton Conway y Richard Guy han conjeturado [1] que la secuencia se vuelve periódica eventualmente, pero a pesar del cálculo de los primeros 2 35 valores por Achim Flammenkamp , la cuestión no se ha resuelto.
Ver también
Referencias
- ^ E. Berlekamp, JH Conway, R. Guy. Formas ganadoras para tus juegos matemáticos. Prensa académica, 1982.