Nim de Fibonacci
La mise en forme de cet article est à améliorer ().
La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».
Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » ().
Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.
Le Nim de Fibonacci est un jeu mathématique de soustraction, une variante du jeu de nim. Les joueurs jouent a tour de rôle en retirant des pièces d'une pile, à chaque coup en prenant au plus deux fois plus de pièces que le coup précédent, et en gagnant en prenant la dernière pièce. Les nombres de Fibonacci sont largement utilisés dans son analyse; en particulier, le premier joueur peut gagner si et seulement si le nombre initial de pièces n'est pas un nombre de Fibonacci. Une stratégie complète est connue pour le meilleur jeu dans les parties avec une seule pile de jetons, mais elle n'est pas encore établie pour les variantes du jeu avec plusieurs piles.
Règles et historique[modifier | modifier le code]
Le jeu de Nim de Fibonacci se joue à deux joueurs, qui alternent en retirant des pièces ou d'autres jetons d'une pile. Au premier coup, un joueur n'est pas autorisé à prendre toutes les pièces, et à chaque coup suivant, le nombre de pièces retirées peut être n'importe quel nombre qui est au plus le double du coup précédent. Conformément à la convention de jeu normale, le joueur qui prend la dernière pièce remporte la partie.
Le jeu a été décrit pour la première fois par Michael J. Whinihan en 1963, créditant son invention au mathématicien Robert E. Gaskell de l'Université d'État de l'Oregon. Il est appelé Fibonacci nim car les nombres de Fibonacci sont largement utilisés dans son analyse[1].
Ce jeu doit être distingué d'une autre variante, également appelée Fibonacci nim, où les joueurs peuvent retirer n'importe quel nombre de pièces correspondant à un nombre de Fibonacci à chaque coup.
Stratégie[modifier | modifier le code]
La stratégie optimale pour jouer à Fibonacci nim consiste à considérer le nombre actuel de pièces comme une somme de nombres de Fibonacci[1]. Il existe plusieurs façons de représenter les nombres sous forme de sommes de nombres de Fibonacci, mais une seule représentation utilise chaque nombre de Fibonacci au plus une fois et évite les paires consé+-cutives de nombres de Fibonacci; cette représentation unique est connue sous le nom de représentation de Zeckendorf.Par exemple, la représentation de Zeckendorf de 10 est 8 + 2. Bien que 10 puisse également être représenté de différentes manières, telles que 5 + 5 ou 5 + 3 + 2, ces autres méthodes ne respectent pas la condition d'utiliser chaque nombre de Fibonacci une seule fois et d'éviter les paires consécutives de nombres de Fibonacci, telles que les paires 2, 3 et 3, 5. On peut trouver la représentation de Zeckendorf de n'importe quel nombre en utilisant un algorithme glouton qui soustrait de manière répétée le plus grand nombre de Fibonacci possible jusqu'à atteindre zéro.
La stratégie du jeu implique également un nombre appelé "quota", qui peut être noté q. Il s'agit du nombre maximal de pièces pouvant actuellement être retirées. Au premier coup, toutes les pièces sauf une peuvent être retirées, donc si le nombre de pièces est n, le quota est q = n − 1. Aux coups suivants, le quota est deux fois le coup précédent[1].
Selon ces définitions, le joueur qui s'apprête à jouer peut remporter la partie à chaque fois que q est supérieur ou égal au plus petit nombre de Fibonacci dans la représentation de Zeckendorf. En revanche, il subira une défaite (en suivant la meilleure stratégie de l'adversaire) dans le cas contraire. En position favorable, il est toujours avantageux de retirer toutes les pièces (si cela est autorisé) ou, à défaut, de retirer un nombre de pièces égal au plus petit nombre de Fibonacci dans la représentation de Zeckendorf. Lorsque cela est possible, l'adversaire se retrouvera inévitablement dans une position perdante, car le nouveau quota sera inférieur au plus petit nombre de Fibonacci dans la représentation de Zeckendorf du nombre restant de pièces. D'autres coups gagnants peuvent également être envisageables. Cependant, à partir d'une position défavorable, tous les coups mèneront à des positions gagnantes[1].
La représentation de Zeckendorf d'un nombre de Fibonacci se compose de ce seul nombre. Ainsi, lorsque la pile initiale a un nombre de pièces égal à un nombre de Fibonacci n, le plus petit nombre de Fibonacci dans la représentation de Zeckendorf est simplement n, ce qui est supérieur au quota initial n − 1. Par conséquent, un nombre de Fibonacci en tant que pile initiale est perdant pour le premier joueur et gagnant pour le deuxième joueur. Cependant, tout nombre non Fibonacci en tant que nombre initial de pièces a des nombres de Fibonacci plus petits dans sa représentation de Zeckendorf. Ces nombres ne sont pas plus grands que le quota initial, donc chaque fois que le nombre initial de pièces n'est pas un nombre de Fibonacci, le premier joueur peut toujours gagner.
Exemple[modifier | modifier le code]
Par exemple, imaginons qu'au départ, il y ait 10 pièces[2].
La représentation de Zeckendorf de 10 est 10 = 8 + 2, et le quota initial est de 9, supérieur au plus petit nombre de Fibonacci 2 dans la représentation de Zeckendorf, donc le premier joueur peut gagner. Un coup gagnant pour le premier joueur serait de retirer le plus petit nombre de Fibonacci dans cette représentation, soit 2, laissant 8 pièces.
Après ce coup, il reste 8 pièces, avec une représentation de Zeckendorf de 8, et le nouveau quota est de 4, ce qui signifie que le deuxième joueur peut retirer au plus 4 pièces, ce qui n'est pas suffisant pour atteindre le plus petit nombre dans la représentation de Zeckendorf. Retirer 3 ou 4 pièces permettrait au premier joueur de gagner immédiatement; supposons plutôt que le deuxième joueur prend 2 pièces.
Cela laisse 6 = 5 + 1 pièces, avec un quota de 4, supérieur au 1 dans la représentation de Zeckendorf. Le premier joueur peut à nouveau prendre le plus petit nombre de Fibonacci dans cette représentation, soit 1, laissant 5 pièces.
Avec une pile de 5 pièces, la représentation de Zeckendorf est 5, mais le quota est de 2, un nombre plus petit. Le deuxième joueur pourrait prendre deux pièces, mais cela perdrait à nouveau immédiatement, supposons donc que le deuxième joueur ne prenne qu'une seule pièce.
Après ce coup, le nombre de pièces est de 4 = 3 + 1, et le quota est de 2. Le premier joueur prend à nouveau le plus petit nombre de Fibonacci dans la représentation de Zeckendorf, soit 1, laissant 3 pièces.
Maintenant, peu importe si le deuxième joueur prend une ou deux pièces, le premier joueur remportera la partie au coup suivant.
Pieux multiples[modifier | modifier le code]
Nim de Fibonacci est jeu impartial dans le sens où les coups disponibles à partir de n'importe quelle position ne dépendent pas de l'identité du joueur qui s'apprête à jouer. Par conséquent, le théorème de Sprague-Grundy peut être utilisé pour analyser une extension du jeu dans laquelle il y a plusieurs piles de pièces, et chaque coup retire des pièces d'une seule pile (au plus le double du coup précédent de la même pile)). Pour cette extension, il est nécessaire de calculer valeur nim de chaque pile; la valeur du jeu multi-pile est la somme nim exclusive de ces valeurs de Grundy. Cependant, une description complète de ces valeurs n'est pas connue.
Une autre variante du jeu avec plusieurs piles a également été étudiée, limitant le nombre de pièces à retirer à deux fois le nombre du coup précédent, indépendamment de savoir si ce coup précédent a été effectué sur la même pile.
Références[modifier | modifier le code]
- (en) Michael J. Whinihan, « Fibonacci Nim », Fibonacci Quarterly, vol. 1, no 4, , p. 9–13 (lire en ligne [PDF]).
- Le fait que 2 soit le seul coup gagnant à partir de cette position de départ, ainsi que les représentations de Zeckendorf de toutes les tailles de piles issues de cet exemple, peuvent être consultés dans Allen & Ponomarenko (2014), Tableau 1, p. 818.
- Steven Vajda, Mathematical games and how to play them, Dover Publ, coll. « Dover books on mathematics », (ISBN 978-0-486-46277-6)
- Michael Drmota, « On Generalized Fibonacci Numbers of Graphs », dans Applications of Fibonacci Numbers, Springer Netherlands, (ISBN 978-94-010-7352-3, lire en ligne), p. 63–76
- Ronald Lewis Graham, Donald Ervin Knuth et Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley, (ISBN 978-0-201-55802-9)
- (en) Cody Allen et Vadim Ponomarenko, « Fibonacci Nim and a full characterization of winning moves », Involve, a Journal of Mathematics, vol. 7, no 6, , p. 807–822 (ISSN 1944-4184 et 1944-4176, DOI 10.2140/involve.2014.7.807, lire en ligne, consulté le )
- (en) Urban Larsson et Simon Rubinstein-Salzedo, « Grundy values of Fibonacci nim », International Journal of Game Theory, vol. 45, no 3, , p. 617–625 (ISSN 0020-7276 et 1432-1270, DOI 10.1007/s00182-015-0473-y, lire en ligne, consulté le )
- (en) Urban Larsson et Simon Rubinstein-Salzedo, « Global Fibonacci nim », International Journal of Game Theory, vol. 47, no 2, , p. 595–611 (ISSN 0020-7276 et 1432-1270, DOI 10.1007/s00182-017-0574-x, lire en ligne, consulté le )
