Juego de Grundy

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 la última persona que puede hacer un movimiento permitido gana.

Pilas de monedas. Cualquiera de estas pilas se puede dividir en dos pilas de diferentes tamaños: una vez que se ha dividido la pila de tres más a la izquierda, no se puede dividir más.

Ejemplo

Un juego 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 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 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+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+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+1
jugador 1: 3+1+2+1+1 → 2+1+1+2+1+1
al 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 On-Line Encyclopedia of Integer Sequences como 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 235 valores por Achim Flammenkamp, la cuestión no ha sido resuelta.

Véase también

Referencias
  1. E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays. Academic Press, 1982.

Enlaces externos

En inglés:

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.