Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

Théorème de Sprague-Grundy

  1. Gandhi33

    Date d'inscription
    septembre 2014
    Localisation
    Royaume de Belgique
    Messages
    421

    Théorème de Sprague-Grundy

    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 !!


    -----

    "Méfions-nous des citations sur Internet", Leonhard Euler
     


    • Publicité



  2. minushabens

    Date d'inscription
    juillet 2014
    Messages
    5 216

    Re : Théorème de Sprague-Grundy

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

  3. Gandhi33

    Date d'inscription
    septembre 2014
    Localisation
    Royaume de Belgique
    Messages
    421

    Re : Théorème de Sprague-Grundy

    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 ?
    Dernière modification par Gandhi33 ; 24/08/2017 à 12h09. Motif: correction
    "Méfions-nous des citations sur Internet", Leonhard Euler
     


    • Publicité







Sur le même thème :





 

Discussions similaires

  1. Théoreme de la base incomplete et theoreme du rang
    Par Emyyy12345 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 24/09/2016, 19h52
  2. Réponses: 10
    Dernier message: 18/08/2016, 21h23
  3. Théorème de Rolle et Théorème d'Accroissements Finis
    Par mikita2012 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 27/01/2016, 19h38
  4. Réponses: 0
    Dernier message: 30/05/2015, 15h18
  5. Sprague Filter
    Par JosePaldir dans le forum Électronique
    Réponses: 4
    Dernier message: 16/02/2015, 16h15