Théorème de Sprague-Grundy

[invite2b0650e6]

Bonjour à tous !

Alice et Bob jouent au jeu suivant :

Initialement, il y a jetons alignés :

Ensuite, chacun à leur tour, ils peuvent choisir de retirer ou jetons consécutifs. Le joueur qui retire le dernier jeton perd la partie.

Note : Deux jetons ne sont consécutifs que s'ils l'étaient déjà pour la position initiale.

Qui a une stratégie gagnante ?


J'ai fait un programme pour m'aider à répondre à cette question et je conjecture que Bob a une stratégie gagnante si ou et Alice en a une dans tous les autres cas.

Mon programme est quasi-exponentiel. Je l'ai fait tourner jusque mais je ne peux pas aller beaucoup plus loin.

Je me suis renseigné sur le théorème de Sprague-Grundy (sur Wikipedia entre autres) et j'ai l'impression qu'on peut s'en servir ici (pour, entre autres améliorer la complexité du programme jusqu'en et peut-être prouver ma conjecture).

Le jeu est bien un jeu de Nim (2 joueurs, impartial, etc). La situation finale (perdante) est .
Cependant, on ne peut pas directement utiliser les résultats sur la somme de deux jeux de Nim :
Supposons qu'il y ait jetons au départ et qu'Alice prenne le jeton n°3. On a donc la situation . On aimerait bien dire que cette situation est la somme de et de . Or, (Wikipedia) La position finale de G + H est constituée du couple (g, h) où g est la position finale de G et h la position finale de H. Ce n'est pas le cas ici puisque la position finale d'un des deux tas sera tandis que la position finale de l'autre sera la position vide, sans jeton.

Comment contourner le problème pour pouvoir utiliser toute la puissance du théorème de Sprague-Grundy ?

Merci beaucoup d'avance !!


-----

Publicité

[invite9dc7b526]

pourquoi est-ce que la position finale dans chaque tas n'est pas la position vide?

[invite2b0650e6]

N'est-ce pas un problème pour appliquer Sprague-Grundy que la position finale soit gagnante ?

Si on dit que la position finale (gagnante) est la position vide, quel nimber faut-il lui assigner ? Si c'est , alors la position à un jeton () a un nimber de (minimal excluded number de ) et la position a un nimber de (minimal expluded number de ). Or la position est gagnante et elle a un nimber non nul... ?

Doit-on faire autre chose que de calculer le minimal excluded number ? Et que va-t-on faire à la place du XOR de deux positions ?