Nim de Fibonacci

Le Nim de Fibonacci est un jeu mathématique de soustraction et une variante du jeu de Nim, qui se joue à deux joueurs. Les joueurs jouent à tour de rôle en retirant des pièces d'une pile ; à chaque coup, on peut prendre au plus deux fois le nombre de pièces retirées au le coup précédent. Celui ou celle qui prend la dernière pièce gagne. 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 pour le meilleur jeu est connue dans les parties avec une seule pile de jetons, mais elle n'est pas encore établie pour les variantes du jeu avec plusieurs piles.

Le Nim de Fibonacci se joue avec une pile de pièces. Le nombre de pièces dans la pile montrée est 21, qui est un nombre de Fibonacci : une partie commençant avec cette pile et jouée de manière optimale sera gagnée par le deuxième joueur.

Règles et historique

Le jeu de Nim de Fibonacci se joue à deux joueurs, qui retirent en alternance des pièces (ou d'autres jetons) d'une pile. Le joueur jouant le premier coup n'est pas autorisé à prendre toutes les pièces. À chacun des coups suivants, le nombre de pièces retirées peut être n'importe quel nombre qui est au plus le double ddu nombre de pièces retirées lors du coup précédent. Conformément à la convention de jeu normale pour les jeux de Nim, 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 ; celui-ci crédite de son invention le mathématicien Robert E. Gaskell de l'université d'État de l'Oregon. Le jeu est appelé Nim de Fibonacci car son analyse repose sur les nombres de Fibonacci.

Ce jeu doit être distingué d'une autre variante, également appelée Nim de Fibonacci, où les joueurs peuvent retirer à chaque coup n'importe quel nombre de pièces à condition que ce soit un nombre de Fibonacci.

Stratégie

Représentation visuelle des représentations de Zeckendorf de chaque nombre. Un nombre est représenté par une ligne de l'image, sa décomposition en nombres de Fibonacci est indiquée par les segments de différentes couleurs sur chaque ligne, chacun correspondant à un nombre de Fibonacci. Dans le jeu de Nim de Fibonacci, une stratégie optimale consiste à retirer le plus petit segement de la ligne correspond au nombre actuel de pièces, en laissant une pile décrite par les segments restants de cette ligne.

La stratégie optimale pour jouer au jeu de Nim de Fibonacci consiste à considérer le nombre actuel de pièces comme une somme de nombres de Fibonacci. Il existe plusieurs façons de représenter les nombres entiers sous forme de sommes de nombres de Fibonacci, mais une seule représentation utilise chaque nombre de Fibonacci au plus une fois et n'inclut pas deux nombres consécutifs 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 comme une somme de nombres de Fibonacci, comme 5 + 5 ou 5 + 3 + 2, ces autres décompositions ne respectent pas la condition d'utiliser chaque nombre de Fibonacci une seule fois ou d'éviter les nombres de Fibonacci consécutifs (les paires 2, 3 ou 3, 5 sont formées de nombres de Fibonacci consécutifs). 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 de Nim de Fibonacci fait aussi appel à un nombre appelé « quota », qui peut être noté $q$. Il s'agit du nombre maximal de pièces pouvant être retirées à chaque coup. Au premier coup, toutes les pièces sauf une peuvent être retirées, donc si le nombre de pièces de départ est $n$, le quota $q$ est $n-1$. Aux coups suivants, le quota est deux fois le nombre de pièces retirées au coup précédent.

Avec ces définitions, le joueur qui s'apprête à jouer avec une pile de $n$ (qu'elle soit initiale ou celle qui reste après les coups précédents) dispose d'une stratégie pour remporter la partie si $q$ est supérieur ou égal au plus petit nombre de Fibonacci dans la représentation de Zeckendorf de $n$. En revanche, il subira une défaite dans le cas contraire (si son adversaire joue sa meilleure stratégie possible). Pour un joueur 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 de $n$. Lorsque cela est possible, l'adversaire se retrouvera inévitablement dans une position perdante, car le nouveau quota sera alors 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 pour l'adversaire.

La représentation de Zeckendorf d'un nombre de Fibonacci se compose de ce seul nombre. Donc, 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$, qui est supérieur au quota initial $n-1$. Par conséquent, si la pile initiale a pour nombre de pièces un nombre de Fibonacci, le premier joueur perd et le deuxième joueur dispose d'une stratégie gagnante. Si le nombre initial de pièces $n$ n'est pas un nombre de Fibonacci, au contraire, il y a des nombres de Fibonacci plus petits que lui dans sa représentation de Zeckendorf. Ces nombres sont inférieurs (ou, pour l'un d'eux au plus égal) au quota initial $n-1$, et dans ce cas, le premier joueur dispose toujours d'une stratégie gagnante.

Exemple

Par exemple, supposons qu'au départ, il y ait 10 pièces.

La représentation de Zeckendorf de 10 est 10 = 8 + 2, et le quota initial est de 9, qui est 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 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.

Piles multiples

Le 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 où, à chaque coup, le joueur retire des pièces d'une seule pile, au plus le double du nombre de pièces du coup précédent de la même pile. Pour cette extension, il est nécessaire de calculer la 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, en limitant le nombre de pièces à retirer à deux fois le nombre de pièces retirées au coup précédent, indépendamment de la pile où ce coup précédent a été effectué.

Notes et références

(en) Cet article est partiellement ou en totalité issu de la page de Wikipédia en anglais intitulée « Fibonacci nim » (voir la liste des auteurs).

Bibliographie

• (en) Steven Vajda, Mathematical games and how to play them, Dover Publ, coll. « Dover books on mathematics », 2008 (ISBN 978-0-486-46277-6).
• (en) Michael Drmota, « On Generalized Fibonacci Numbers of Graphs », dans Applications of Fibonacci Numbers, Springer Netherlands, 1990 (ISBN 978-94-010-7352-3, lire en ligne), p. 63–76.
• (en) Ronald Lewis Graham, Donald Ervin Knuth et Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley, 2017 (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, n^o 6,‎ 20 octobre 2014, p. 807–822 (ISSN 1944-4184 et 1944-4176, DOI 10.2140/involve.2014.7.807, lire en ligne, consulté le 15 novembre 2023).
• (en) Urban Larsson et Simon Rubinstein-Salzedo, « Grundy values of Fibonacci nim », International Journal of Game Theory, vol. 45, n^o 3,‎ août 2016, p. 617–625 (ISSN 0020-7276 et 1432-1270, DOI 10.1007/s00182-015-0473-y, lire en ligne, consulté le 15 novembre 2023).
• (en) Urban Larsson et Simon Rubinstein-Salzedo, « Global Fibonacci nim », International Journal of Game Theory, vol. 47, n^o 2,‎ mai 2018, p. 595–611 (ISSN 0020-7276 et 1432-1270, DOI 10.1007/s00182-017-0574-x, lire en ligne, consulté le 15 novembre 2023).