Nim de Fibonacci : de quoi s’agit-il ?
Le Nim de Fibonacci se joue avec une seule pile. Le premier joueur peut prendre n’importe quel nombre d’objets, sauf la pile entière. Ensuite, chaque coup prend au moins un objet et au plus le double de ce que l’adversaire vient de prendre. Le joueur qui prend le dernier objet gagne : le jeu se joue toujours dans le sens normal, l’option misère et l’option des piles de départ du jeu classique ne s’appliquent donc pas.
La pile contient 10 (petit), 15 (moyen, par défaut) ou 20 (grand) objets, choisis comme taille dans la configuration de la table. La limite grandit et rétrécit au fil du jeu : une grosse prise permet à l’adversaire de prendre encore plus, tandis qu’une petite le tient en laisse, et la partie est donc autant une lutte pour la taille de la prochaine limite que pour la pile.
Changements de règles
| Règle | Nim standard | Nim de Fibonacci |
|---|---|---|
| Piles | Nim standardPlusieurs piles : 1, 3, 5 et 7 objets par défaut, ou un autre ensemble choisi dans la configuration de la table. | Nim de FibonacciUne pile de 10, 15 (par défaut) ou 20 objets, choisie comme taille dans la configuration de la table. |
| Premier coup | Nim standardPrenez autant d’objets que vous voulez dans une pile, pile entière comprise. | Nim de FibonacciPrenez autant d’objets que vous voulez, sauf la pile entière. |
| Coups suivants | Nim standardPrenez autant d’objets que vous voulez dans une pile, à chaque tour. | Nim de FibonacciPrenez au moins 1 et au plus le double de ce que l’adversaire a pris au coup précédent, sans dépasser ce qui reste. |
| Objectif | Nim standardJeu misère par défaut : celui qui prend le dernier objet perd. La configuration permet de passer au jeu normal, où prendre le dernier objet fait gagner. | Nim de FibonacciToujours en jeu normal : celui qui prend le dernier objet gagne. |
| Jeu gagnant | Nim standardLaissez les piles avec une somme de Nim (le XOR bit à bit de leurs tailles) nulle, avec une subtilité en fin de partie misère. | Nim de FibonacciÉcrivez la pile comme une somme de nombres de Fibonacci, sans deux termes voisins dans la suite, et prenez le plus petit d’entre eux quand la limite le permet. Le premier joueur perd avec le meilleur jeu exactement quand la pile de départ est un nombre de Fibonacci ; 10, 15 et 20 n’en sont pas, le premier joueur peut donc gagner. |
Histoire
Michael J. Whinihan a décrit le Nim de Fibonacci en 1963 dans The Fibonacci Quarterly et a attribué le jeu à Robert E. Gaskell, mathématicien à l’université d’État de l’Oregon. Son nom vient du rôle que jouent dans la solution les nombres de Fibonacci 1, 2, 3, 5, 8, 13, 21 et ainsi de suite.
La méthode gagnante repose sur ce qu’on appelle aujourd’hui le théorème de Zeckendorf : tout entier positif s’écrit d’une seule façon comme somme de nombres de Fibonacci dont aucun n’est consécutif à un autre. Le théorème porte le nom d’Édouard Zeckendorf, bien que Gerrit Lekkerkerker l’ait déjà publié en 1952.