Joc de Grundy

Piles de monedes. Qualsevol d'estes piles es pot dividir en dos piles de diferents tamanys: una volta que s'ha dividit la pila de tres més a l'esquerra, no es pot dividir més.

El joc de Grundy és un joc matemàtic d'estratègia per a dos jugadors. La configuració inicial és un sol montó d'objectes, i els dos jugadors es turnan per a dividir un sol montó en dos montons de diferents tamanys. El joc termina quan solament queden montons de tamany dos o més menuts, cap dels quals es pot dividir de manera desigual. El joc generalment es juga com un joc normal, lo que significa que l'última persona que pot fer un moviment permés gana.

Eixemple

Un joc normal que comença en un únic montó de 8 és una victòria per al primer jugador sempre que comence dividint el montó en montons de 7 i 1:

jugador 1: 8 → 7+1

El jugador 2 ara té tres opcions: dividir el montó de 7 en 6 + 1, 5 + 2 o 4 + 3. En cada u d'estos casos, el jugador 1 pot assegurar-se de que en el pròxim moviment torne al seu oponent un montó de tamany 4 més montons de tamany 2 i més menuts:

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

Ara el jugador 2 té que dividir el montó de 4 en 3 + 1, i el jugador 1 posteriorment dividix el montó 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 li queden moviments i pert

Teoria matemàtica

El joc es pot analisar per mig del teorema de Sprague-Grundy. Açò requerix que els tamanys de pila del joc s'assignen a tamanys de pila Nim equivalents. Esta assignació es captura en l'On-line Encyclopedia of Integer Sequences com Plantilla:OEIS2C:

Tamany del montó        : 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...
Montó de Nim equivalent: 0  0  0  1  0  2  1  0  2  1  0  2  1  3  2  1  3  2  4  3  0 ...

Usant este mapage, l'estratègia per a jugar el joc Nim també es pot usar per al joc de Grundy. Si la seqüència de valors Nim del joc de Grundy aplega a ser periòdica és un problema sense resoldre. Elwyn Berlekamp, John Horton Conway i Richard Guy han conjeturado que la seqüència es torna periòdica eventualment, pero a pesar del càlcul dels primers 2³⁵ valors per Achim Flammenkamp, la qüestió no ha segut resolta.

Vore també

• Nim (joc)
• Teorema de Sprague–Grundy