Page fibonacci.txt : http://perso.wanadoo.fr/jean-paul.davalan/jeux/nim/fibonacci/fibonacci.txt version du 29 mars 2005 -------------------------------------------------------------------------- Jeux de Nim (Fibonacci) Question : ========== Pourriez-vous m'expliquer comment calculer le nombre de pions à enlever. --------------------------------------------------------------------------- A - Le GRAPHE B - ÉTUDE DU JEU Noyau d'un graphe Sous-ensemble stable. Sous-ensemble absorbant. Noyau. Positions gagnantes et noyau C - Et FIBONACCI dans tout ça ! Écriture de Zeckendorf d'un entier. Propriété Algorithme Exemple Noyau gagnant et Zeckendorf ? un exemple Démo remarque Résumé 1. - version Zeckendorf 2. - version Fibonacci Utilisation des cartes Exemples D - Le GRAPHIQUE E - PLUSIEURS TAS F - PROGRAMMES --------------------------------------------------------------------------- A - Le GRAPHE ============= Dans le jeu de Fibonacci-Nim à un seul tas, le nombre n de jetons ne suffit pas à caractérier un état du jeu, on a besoin de connaître aussi soit le nombre x de pions pris au coup précédent par l'adversaire, soit le nombre maximum 2*x de pions que l'on peut retirer du tas. Prenons par la notation a = (n, p=2*x) pour un état possible du jeu, (n pions, p pions retirables), on pourra aussi se limiter aux cas où p <= n. Si le nombre initial de pions est N, l'état initial est (N, N-1). La position finale est (0, 0). Exemple : supposons le jeu dans l'état (8, 4), vous pouvez retirer au minimum 1 et au maximum 4 pions, les états possibles sont donc : (7, 2) lorsqu'on retire 1 pion (6, 4) -- 2 pions (5, 5) -- 3 pions ce n'est pas (n=5, p=2*3=6) car on a décidé que p <= n (4, 4) -- 4 pions On peut alors étudier le graphe ayant pour sommets tous les couples (n, p) possibles avec p <= n. les arcs de ce graphe iront d'un état de jeu (n, p) à tous les (états (n', p') qui peuvent lui succéder dans le jeu. Exemple (suite) : du sommet (8, 4) partent 4 arcs vers les sommets (7, 2) (6, 4) (5, 5) et (4, 4) Remarque : Dans la notation (n, p) des états, p est supérieur ou égal à 2. La solution donnée un peu plus bas sur cette page est vraiment très simple car il suffit même de connaître la valeur de n pour être en mesure de gagner. B - ÉTUDE DU JEU ================ Noyau d'un graphe ----------------- À propos du jeu de chomp j'ai donné des explications sur les graphes et leurs noyaux à la page http://perso.wanadoo.fr/jean-paul.davalan/jeux/nim/chomp/chomp.txt On pourra y trouver en particulier les définitions suivantes : Sous-ensemble stable. ~~~~~~~~~~~~~~~~~~~~~ Un sous-ensemble A de sommets est dit stable si tout sommet x de A n'a aucun successeur dans A Sous-ensemble absorbant. ~~~~~~~~~~~~~~~~~~~~~~~~ Un sous-ensemble A de sommets est dit absorbant si tout sommet n'appartenant pas à A possède au moins un successeur dans A. Noyau ~~~~~ Un sous-ensemble A de sommets est un noyau du graphe s'il est à la fois stable et absorbant. Positions gagnantes et noyau ---------------------------- L'état (0, 0) est gagnant, c'est aussi le seul sommet sans successeur dans le graphe considéré pour le jeu de Fibonacci-Nim. Il est gagnant en ce sens que si vous prenez les derniers jetons et que vous placez le jeu dans l'état (0, 0), alors vous gagnez la partie. On peut montrer que le graphe considéré possède un noyau et un seul. Ce est d'ailleurs très facile à construire de manière progressive. 1) (0, 0) est dans le noyau K 2) Tous les sommets qui ont pour successeur (0, 0) ou un élément de K seront dans S \ K (où S est l'ens. des sommets et S \ K = S - K est l'ens. des élts. qui ne sont pas dans le noyau). 3) Les sommets dont tous les successeurs sont dans S\K (ne sont pas dans K) seront eux dans K. Reprendre en 2) jusqu'à épuisement des sommets. Les positions gagnantes sont les sommets du noyau, les autres sont perdantes. explication : a) Si vous héritez d'une position perdante P1 (hors du noyau), cette position a pour successeur au moins une position gagnante G1 (du noyau), allez à cette position. Soit vous gagnez directement car le jeu se termine, soit vous laissez la main à votre adversaire. b) Vous savez jouer et vous laissez à votre adversaire une position gagnante G1. La position gagnante G1 (du noyau) n'a pour successeurs que des positions perdantes (hors du noyau), votre adversaire vous laissera une position perdante P2. On continue ainsi a) et b) alternativement jusqu'à la conclusion du jeu qui arrive nécessairement car le nombre de pions diminue à chaque coup. C - Et FIBONACCI dans tout ça ! ============================== Écriture de Zeckendorf d'un entier. ------------------------------------ Notations : Prendre ci-dessous le terme 'entier' dans le sens (signification) 'entier positif' ou 'entier naturel' ou 'naturel' Propriété : ~~~~~~~~~~~ Tout entier (positif) s'écrit de manière unique sous la forme d'une somme de nombres de Fibonacci différents et non consécutifs à partir des termes 1 2 3 5 8 13 21 34 55 89 ... Algorithme : ~~~~~~~~~~~~ soustraire le plus grand Fibonacci possible puis recommencer avec le reste obtenu. Montrer en utilisant les propriétés de la suite de Fibonacci que l'on n'obtient jamais de cette façon deux fois le même terme, ni même deux termes consécutifs de la suite de Fibonacci. En effet la relation de récurrence F(k-1)+F(k) = F(k+1) définissant cette suite 1 2 3 5 8 ... permet de l'expliquer Exemple : ~~~~~~~~~ voir "Numération de Zeckendorf" à la page http://perso.wanadoo.fr/jean-paul.davalan/divers/fibonacci/fibonacci.html#zeckendorf où se trouve une petite application qui calcule l'écriture de Zeckendorf d'un entier : dans la numération de Zeckendorf l'écriture 1000010010 correspond à 1*89 + 0*55 + 0*34 + 0*21 + 0*13 + 1*8 + 0*5 +0*3 +1*2 +0*1 = 89 + 8 + 2 = 99 d'où 1000010010_Zeckendorf = 99_décimal Dans l'écriture 1000010010_Z et en partant de la droite les chiffres 1 ou 0 correspondent à la présence ou non dans la somme des termes ... 89 55 34 21 13 8 5 3 2 1 de la suite de Fibonacci (écrite aussi de droite à gauche pour mieux apprécier la correspondance avec les chiffres) - remarquer que les chiffres 1 sont séparés par un 0 au moins dans l'écriture de Zeckendorf. Noyau gagnant et Zeckendorf ? ----------------------------- un exemple : ------------ 1. a. - Prenons le 99 ci-dessus écrit 1000010010_Z vous avez le droit de retirer au moins 2 pions = 10_Z faîtes le, on obtient 1000010000_Z on a juste remplacé un chiffre 1 par un 0 1. b. - l'adversaire qui peut retirer au plus 4 = 111_Z pions ne pourra retirer le 1 de droite de 1000010000_Z car 10000_Z > 111_Z supposons qu'il retire le maximum autorisé de 4 pions, le total passe alors de 97 à 93=1000000101_Z 2. a. - jouer 1000000101_Z --> 1000000100_Z (on aurait pu choisir aussi 1000000000_Z, le faire en exercice !) 2. b. - l'adversaire sera obligé de 'casser' le 100_Z de droite de 1000000100_Z. Il a le droit de prendre un ou deux pions, supposons que c'est un donc, par exemple 1000000100_Z --> 1000000010_Z en soustrayant 1 3. a. - jouer 1000000010_Z --> 1000000000_Z (valeur retirée 10_Z = 2 3. b. - votre adversaire peut retirer jusqu'à 4 pions etc. Démo ------- Je n'ai pas envie de rédiger ici une démonstration rigoureuse et complète mais juste donner l'idée sous-jacente et suffisamment d'indications pour pouvoir reconstituer la démo. Le 'gagnant' de la partie est celui qui peut toujours soustraire (effacer) le 1 de droite de l'écriture de Zeckendorf, (ou effacer tous les 1 de droite à partir d'un certain rang, sans en remettre) le 'perdant', son adversaire, ne pourra pas en faire autant, - certes il doit retirer le chiffre 1 de droite mais la 'valeur' de ce dernier est trop grande et il doit remettre des 1 à sa droite. - car des chiffres 0 s'intercalent entre les 1 de l'écriture de Zeckendorf. Alors finalement, ce qui devait arriver, arrive ... il advient un moment où il ne reste qu'un seul chiffre 1 dans l'écriture que le joueur 'gagnant' peut enlever et donc gagner. Et que cette situation n'arrive jamais pour l'autre joueur, le 'perdant', car il n'a JAMAIS le droit de retirer purement et simplement le 1 de droite : il DOIT retirer un 1 et un seul à la fois, le plus à droite possible de l'écriture, MAIS IL DOIT REMETTRE DES 1 à droite de celui qu'il retire. une remarque ~~~~~~~~~~~~ pour qu'on ne croie pas qu'on ne puisse retirer que le 1 de droite. En effet si on en a le droit, on peut retirer, à partir d'un certain rang, tous les 1 de droite, mais alors les retirer absolument tous, sans en oublier. Le principal c'est que l'adversaire ne puisse en faire autant ! avec 17 = 100101_Z si vous en avez la possibilité vous laissez 16 = 100100_Z ou 13 = 100000_Z ou évidemment 0 = 0_Z mais ne surtout pas retirer, par exemple, uniquement le 1 central : 14 = 100001_Z sera perdant car votre adversaire passera évidemment à 13 = 100000_Z Résumé ~~~~~~ La solution est basée sur la suite de Fibonacci, d'où le nom du jeu. 1. - version Zeckendorf: Utilisez la numération de Zeckendorf (basée sur la suite de Fibonacci) Dès que vous en avez la possibilité, effacez le(s) 1 le plus à droite (sans en remettre) Si ça arrive, ça arrivera à tous les coups qui suivront et vous gagnerez. 2. - version Fibonacci : Connaissant par coeur la suite 1 2 3 5 8 13 21 34 55 89 (ça devrait suffire) voici sur le même exemple, la solution sous une version moins Zeckendorf (mais en apparence seulement) vous recevez 17 pions si vous pouvez retirer la totalité de ces 17 pions, faîtes le, sinon : le plus grand F(n) retirable est F(?) = 13, on calcule 17-13 = 4 retirez 4 pions si vous ne pouvez retirer autant, calculez 4 - F(?) = 4-3 = 1 retirez 1 pion -1 /--->-- (16) --->--- ? / -4 17 --->--- (13) \ \-->-- (0) Utilisation des cartes ---------------------- Il s'agit des cartes http://perso.wanadoo.fr/jean-paul.davalan/jeux/cartes/add/index.html les deux premières sont ______________________ | Fibonacci | | 1 4 5 9 12 14 17 | | 19 22 25 27 30 33 35 | | 38 40 43 46 48 51 53 | | 56 59 61 64 67 69 72 | | 74 77 80 82 85 88 90 | | 93 95 98 | --------------------- ______________________ | Fibonacci | | 2 7 10 15 20 23 28 | | 31 36 41 44 49 54 57 | | 62 65 70 75 78 83 86 | | 91 96 99 | | | | | ---------------------- L'écriture de Zeckendorf d'un entier se lit dans ces cartes. Exemples : ~~~~~~~~~~ 99 La décomposition 99 = 2 + 8 + 89 = 1000010010_Z fait que 99 se lit sur les trois cartes dont les plus petits éléments sont 2, 8 et 89 Si le tas contient 99 jetons, retirez 2 ou 2+8=10 ou encore 99 jetons 23 = 2 + 21 Si le tas contient 23 jetons retirez 2 jetons (ou 23 jetons si vous le pouvez) Le plus simple est de chercher la plus petite carte(*) sur laquelle on retrouve le nombre n de jetons du tas. Retirer du tas le nombre de Fibonacci indiqué en haut à gauche de la carte. (*) Les cartes sont ordonnées comme leur plus petit nombre (en haut et à gauche) qui est d'ailleurs le seul nombre de Fibonacci de la carte D - Le GRAPHIQUE ================ Les graphiques de la page http://perso.wanadoo.fr/jean-paul.davalan/jeux/nim/fibonacci/fibpos.html sont maintenant simples à comprendre on écrit l'abscisse x dans la numération de Zeckendorff en éliminant successivement les 1 à partir de la droite on obtient les ordonnées des points rouges de la figure (mais les points d'ordonnée 0 n'ont pas été dessinés, car trop évidents sans doute !) Comme un peu plus haut, si en abscisse on prend x = 17 = 100101_Z, les ordonnées y correspondantes seront 16, 13 (et 0 non dessiné) d'où les points des figures. E - PLUSIEURS TAS ================= En retirant k pions d'un tas, au coup suivant l'adversaire peut retirer 2*k jetons d'un tas. Étude à réaliser ? F - PROGRAMMES ============== Remarque finale à l'intention des internautes qui seraient tentés de comprendre les programmes utilisés : Le noyau du graphe pour le jeu de Fibonacci-Nim a été calculé directement par programme à partir du graphe du jeu, sans utiliser la numération de Zeckendorf ou la suite de Fibonacci. C'était au moins aussi simple de programmer la recherche du noyau en Awk ou en JavaScript, et même de calculer la fonction de Grundy (dont je n'ai pas parlé ci-dessus car elle n'est pas utile). C'était encore plus simple de placer dans un tableau les valeurs de la fonction qui à n fait correspondre le plus petit Fibonacci dans sa décomposition de Zeckendorf (c.-à-d. la plus petite carte ci-dessus) dans 'prog.sh' le noyau est calculé à partir de la fonction de Grundy http://perso.wanadoo.fr/jean-paul.davalan/jeux/nim/fibonacci/prog.sh -----------------------------------------------------------------------