Devenez le maître d’une variante du jeu de Nim

Vous êtes nul aux échecs ? Vous êtes incapable de gagner une partie de Dames ? Vous vous êtes déjà ruiné en jouant au poker ? STOP. Arrêtez la casse. Si vous suivez à la lettre ce que je vais vous apprendre, vous briserez cette spirale de la « lose » aux jeux.

Avant de continuer à lire, je vous informe que cet article est assez long et dense. Vous pouvez sauter les paragraphes 4., 6. et 7. en première lecture. Je ne vous en voudrai pas. Ou peu.

1. Le jeu de Nim Fibonacci

Voici le jeu auquel vous allez jouer. Ce jeu, qui s’appelle le jeu de Nim Fibonacci, se joue à deux, l’un contre l’autre.

On dispose N=25 pièces de monnaie sur une table (ça marche aussi avec des allumettes, ou bien avec des pierres pour les plus pauvres d’entre vous. Je vous rappelle que si vous n’avez pas de Rolex à 50 ans, vous avez raté votre vie). Les règles du jeu (qui sont très simples) sont les suivantes:

  1. Le joueur numéro 1 commence par prendre un nombre quelconque de pièces sur la table. Ce nombre est au maximum N-1=24.
  2. Les deux joueurs jouent à tour de rôle.
  3. Chaque joueur ne peut prendre au maximum que le double des pièces prises par l’autre joueur au tour précédent.
  4. Celui qui prend la dernière pièce remporte la partie.

Voici un exemple de partie. Je voulais appeler les deux protagonistes Jean-Eude et Cunégonde, mais finalement nous allons les nommer joueur 1 et joueur 2 (comme l’ordre dans lequel ils jouent).

  • Sur la table sont disposées 25 pièces
  • Le joueur 1 prend 6 pièces. Il en reste 19.
  • Le joueur 2 peut en prendre au plus 2×6=12. Il en choisit 5. Il en reste donc 14.
  • Le joueur 1 peut prendre jusqu’à 2×5=10 pièces. Il en choisit 4. Il en reste donc 10.
  • Le joueur 2 peut en prendre au plus 2×4=8. Il en prend 3. Il en reste 7.
  • Le joueur 1 peut en prendre au maximum 6. Il en prend 2. Il en reste 5.
  • Le joueur 2 peut prendre au plus 4 pièces. Il en choisit 1. Il en reste 4.
  • Le joueur 1 comprend que s’il prend deux pièces, il perdra. Il en prend une seule. Il en reste 3.
  • Le joueur 2 comprend que s’il prend une ou deux pièces, il perd. Il n’en prend qu’une. Il en reste 2 et le joueur 1 prend les deux restantes et gagne.

La question est la suivante: existe-il une stratégie gagnante à ce jeu ? La réponse est oui. Je vais vous apprendre comment remporter ce jeu à chaque fois. La seule chose que cela vous demandera est de mémoriser une petite suite de nombres. Et encore, cette suite se calcule facilement de tête pour les premières valeurs. Vous l’aurez peut-être deviné, il s’agit de la suite de Fibonacci.

2. Des nombres, des nombres, oui mais Fibonacci

A toutes fins utiles, rappelons ce qu’est la célèbre suite de Fibonacci. Il s’agit de la suite (F_n)_n de nombres entiers telle que chaque terme est la somme des deux termes précédents. Autrement dit,

F_{n+2}=F_{n+1}+F_n

Traditionnellement, on pose F_0=0 et F_1=1, de sorte que le début de cette suite est: 0, 1, 1, 2, 3, 5, 8, 13, 21…. Je ne reviendrai pas sur l’importance de cette suite (d’une part car mes connaissances historiques sur le sujet sont limitées, d’autre part car cet article est déjà très, très long….) mais pour ceux qui aiment la nature, les lapinous, et les nombres dorés, je vous invite à lire ce très beau fascicule.

Pour les besoins de cet article (et des théorèmes qui suivront… oui, il y a aura un théorème après !), nous poserons donc F_0=1 et F_1=2. Les premiers termes de la suite de Fibonacci sont donc:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

Nous verrons que pour gagner au jeu décrit dans le préambule de cet article (où on joue avec N=25 pièces), il vous suffira de retenir la suite 1, 2, 3, 5, 8, 13, 21. Mais n’anticipons pas trop et gardons un peu de suspense…

J’en profite pour faire deux petites remarques à propos des nombres de Fibonacci consécutifs. Nous dirons que deux nombres de Fibonacci F_m \leq F_n sont consécutifs si F_n = F_{m+1}. Par exemple, 8 et 13 sont deux nombres de Fibonacci consécutifs, mais 8 et 21 ne le sont pas. Je vous laisse prouver les deux propriétés suivantes (faciles à partir de la relation de récurrence):

  • Si F_m < F_n sont deux nombres de Fibonacci consécutifs, alors F_n < 2 F_m.
  • Si ce ne sont pas deux nombres de Fibonacci consécutifs, alors 2F_m < F_n.

Par exemple, 13 \leq 2 \times 8 mais 2 \times 8 \leq 21.

3. Le théorème de Zeckendorf

Comme vous le savez probablement depuis le CP, tout nombre entier naturel peut s’écrire de manière unique comme une somme de puissance de 10. On parle de numération en base 10. Par exemple, 46 = 4 \times 10^1 + 6 \times 10^0. Ou encore, 209=2 \times 10^2 + 0 \times 10^1 + 9 \times 10^0. Il existe d’autres bases de numération, les plus connues (et utiles) étant la base 2 (le binaire) et la base 16 (base hexadécimale). Jusque là, rien de bien nouveau. Mais si je vous disais qu’on peut compter en base Fibonacci ? Vous me diriez « Calme-toi jeune fou ! » et vous auriez tort… C’est ce qu’a prouvé un mathématicien amateur belge du nom de Zeckendorf. Plus précisément, voici l’énoncé de son théorème:


Tout entier naturel N>0 peut s’écrire de manière unique comme la somme de nombres de Fibonacci non consécutifs.

Par exemple, 38 = 34 + 3 + 1. Autre exemple trivial: 56432 =46368 + 6765 + 2584 + 610 + 89  + 13 + 3. Si on n’impose pas que les nombres de Fibonacci ne soient pas consécutifs, on n’a plus unicité de l’écriture, comme on peut le voir pour le nombre 100= 89 + 8 + 2 + 1 = 55 + 34 + 8 + 3.

Bon, c’est pas tout, mais on fait des maths, et on ne croit que ce qu’on prouve… Démontrons ce théorème. Cela se fait en deux temps: d’abord l’existence, puis l’unicité.

4. Existence

On prouve l’existence d’une décomposition par récurrence (forte) sur N.

  • Si N=1 alors N=1. Super !
  • Soit N>0 un entier naturel. On suppose que pour tout entier k \leq N, k peut s’écrire comme la somme de nombres de Fibonacci non consécutifs. Il s’agit de montrer que c’est encore le cas pour N+1.
    Si N+1 est un nombre de Fibonacci, il n’y a rien à prouver. Sinon, puisque la suite de Fibonacci est strictement croissante et non majorée, il existe un indice r pour lequel F_r < N+1 < F_{r+1}. Dit autrement, F_r est le plus grand nombre de Fibonacci inférieur à N+1 et F_{r+1} est le plus petit nombre de Fibonacci supérieur à N+1. On pose k = (N+1) - F_r >0. Par hypothèse de récurrence, k peut s’écrire comme une somme F_{r_1} + \cdots + F_{r_p} de nombres de Fibonacci non consécutifs. On a donc N+1 = F_{r_1} + \cdots + F_{r_p} + F_r et il reste à montrer que F_r n’est consécutif à aucun autre nombre F_{r_i}.
    Or, F_r + k = N+1 < F_{r+1}, donc F_r + k < F_{r-1} + F_r (relation de récurrence de la suite de Fibonacci). On en déduit donc k < F_{r-1} . Puisque tous les F_{r_i} sont a fortiori inférieurs à k, ils sont inférieurs à F_{r-1}, et donc ne peuvent être les prédécesseurs de F_r. Ouf !

5. Calcul en pratique de la décomposition de Zeckendorf d’un entier

De cette démonstration de l’existence, nous pouvons en tirer un programme pour calculer la décomposition de Zeckendorf d’un nombre donné. C’est comme cela que j’ai trouvé la décomposition de 56432 plus haut (non je ne l’ai pas faite à la main…). Preuve:

Le programme en C++ est le suivant (moins toutes les fioritures de présentation…):

int main()
{
int n, a, b, intermediaire;
cin>> n ;
cout<<« [ « ;

while(n>0)
{    a=1;    b=1;
while(b<=n)
{ intermediaire = a;   a = b;   b = intermediaire + b;}
cout<< a << ends;    n= n-a; }
cout<<« ] »;
return 0;

}

ATTENTION: le programme que j’ai écrit est sous-optimal car il recalcule à chaque fois la suite de Fibonacci au lieu de conserver astucieusement les termes déjà calculés dans une liste, mais on s’en fiche, le but est d’illustrer la preuve par récurrence ci-dessus. Le principe est donc de trouver le plus grand nombre de Fibonacci inférieur ou égal à l’entier dont on veut la décomposition, puis de faire la différence et de recommencer.

Par exemple pour  décomposer de tête le nombre 18, on se souvient de la liste des premiers nombres de Fibonacci, et le plus grand inférieur à 18 est 13. On écrit 13, puis on recommence avec 18-13=5. Le plus grand nombre de Fibonacci inférieur ou égal à 5 est 5 lui-même, donc au final, 13 +5 est la décomposition de Zeckendorf de 18 !

6. Unicité

Je n’invente pas ces démonstrations bien entendu (rendons à Zeckendorf ce qui appartient à Zeckendorf), mais la façon peu claire dont elles sont présentées sur le Wikipédia Français, m’a poussé à les réécrire. J’ai décidé d’utiliser des indices et des sous-indices pour cette réécriture, ce qui la rend encore moins claire. Je m’en fous, c’est mon blog, je fais ce que je veux avec mes indices !

Commençons par donner un lemme (j’en profite pour m’interroger sur l’expression répandue de « petit lemme »…) :

Si F_{r_1} < \cdots < F_{r_p} sont p nombres de Fibonacci non consécutifs, alors leur somme est inférieure strictement à F_{r_{p} + 1}.

En Français, ce lemme signifie que la somme de nombres de Fibonacci non consécutifs est strictement inférieure au successeur du plus grand terme de la somme. Par exemple, la somme des nombres 5, 13 et 34 (qui ne sont pas consécutifs) est strictement inférieure au successeur de 34 dans la suite de Fibonacci, qui est 55. (5+13+34=52).

La démonstration de ce lemme se fait par récurrence sur p.

  • Si p=1 et si F_{r_1} est un nombre de Fibonacci, il est clairement inférieur strictement à son successeur F_{r_1 +1}.
  • Soit p>1 un entier naturel. On suppose que la propriété est vraie au rang p-1 et on va prouver qu’elle est encore vraie au rang p. On considère pour cela F_{r_1} < \cdots < F_{r_p} nombres de Fibonacci non consécutifs. L’hypothèse de récurrence nous informe que F_{r_1} + \cdots + F_{r_{p-1}} < F_{r_{p-1}+1}. Puisque, F_{r_{p-1}} et F_{r_p} ne sont pas consécutifs, on a les inégalités suivantes:
    F_{r_{p-1}} < F_{r_{p-1}+1} \leq F_{r_p -1} < F_{r_p }
    On en déduit (en utilisant l’hypothèse de récurrence) que:
    F_{r_1} + \cdots + F_{r_{p-1}} + F_{r_p} < F_{r_{p-1}+1} + F_{r_p}
    donc
    F_{r_1} + \cdots + F_{r_{p-1}} + F_{r_p} < F_{r_p -1} + F_{r_p} = F_{r_p + 1}. CQFD.

Nous pouvons passer à présent à la preuve de l’unicité de l’écriture d’un entier comme somme de nombres de Fibonacci consécutifs. On considère un entier naturel N et on suppose qu’il peut s’écrire de deux façons différentes comme somme de nombres de Fibonacci non consécutifs (on suppose que les nombres sont rangés dans l’ordre croissant dans chacune des sommes suivantes):

N= F_{r_1} + \cdots + F_{r_p} = F_{s_1} + \cdots + F_{s_q}

Quitte à simplifier des deux côtés de l’égalité, on peut toujours supposer que les plus grands termes dans chaque membres sont différents. Par exemple, F_{r_p} < F_{s_q}. Ce qui donne donc F_{r_p+1} \leq F_{s_q}.

D’après le lemme précédent, N < F_{r_p+1}. D’autre part, il est clair que F_{s_q} \leq N. On a donc: F_{s_q} < F_{r_p +1} \leq F_{s_q}, ce qui est absurde.

7. La stratégie gagnante

En 1963, Whinihan donna une démonstration mathématique d’une stratégie gagnante au jeu de Nim Fibonacci. J’ai tenté de lire son article avant d’écrire cet article. J’avoue ne pas avoir tout compris. J’ai donc décidé de reprouver (ou d’écrire différemment) les propositions qu’il a donné. Cela veut simplement dire que le reste de l’article risque de contenir des inexactitudes, ou des preuves fausses (puisqu’elles sont de mon cru). Pour lire l’article original de Whinihan pour gagner au jeu de Nim Fibonacci, cliquez ici.

Je sais que vous êtes impatients de savoir comment gagner, mais nous y sommes presque. Dans la suite, il faut se souvenir que N représente le nombre de pièces sur la table à un certain moment de la partie. La variable r représentera les pièces prises par votre adversaire. La stratégie gagnante consiste d’abord à faire en sorte que, chaque fois que c’est à notre tour de jouer, le nombre de pièces sur la table ne soit pas un nombre de Fibonacci. Je donnerai l’interprétation des trois propositions suivantes dans le prochain paragraphe.

Proposition 1: Si N=F_{r_1} + \cdots + F_{r_p} (écriture de Zeckendorf de N) n’est pas un nombre de Fibonacci (c’est-à-dire si p est supérieur ou égal à 2), alors N-F_{r_1} > 2F_{r_1}.

Preuve: N-F_{r_1} = F_{r_2} + \cdots + F_{r_p} \geq F_{r_2}. Donc N-F_{r_1} \geq F_{r_2} > 2 F_{r_1} (car F_{r_1} et F_{r_2} sont deux nombres de Fibonacci non consécutifs. Voir la remarque faite plus haut dans l’article !) #

Proposition 2: Si N=F_{r_1} + \cdots + F_{r_p} avec p \geq 3 alors pour tout 0 < r \leq 2 F_{r_1} , le nombre N-F_{r_1} - r n’est pas un nombre de Fibonacci.

Preuve: On  a r \leq 2 F_{r_1} < F_{r_2} donc F_{r_2} - r > 0. Par suite, N - F_{r_1}-r = (F_{r_2}-r) + F_{r_3} + \cdots + F_{r_p} > F_{r_p}. D’autre part, d’après le lemme du paragraphe précédent, N - F_{r_1}-r \leq F_{r_2} + F_{r_3} + \cdots + F_{r_p} < F_{r_p +1}. Nous avons donc prouvé les inégalités:

F_{r_p} < N - F_{r_1}-r < F_{r_p +1}

Le nombre N - F_{r_1}-r est donc compris strictement entre deux nombres de Fibonacci consécutifs, il ne peut ainsi pas être un nombre de Fibonacci.#

Proposition 2 bis: Si N=F_{r_1}+F_{r_2} (écriture de Zeckendorf) et si 0 < r \leq 2F_{r_1} alors: soit N - F_{r_1}-r n’est pas un nombre de Fibonacci, soit N - F_{r_1}-r est un nombre de Fibonacci inférieur (strictement) à 2 r.

Preuve: Si N - F_{r_1}-r = F_{r_2} -r est un nombre de Fibonacci F_j > 0 alors F_{r_2}=r+F_j, donc F_{r_2} >F_j.

On souhaite prouver l’inégalité 2r > F_{r_2}-r. Mais puisque r = F_{r_2} - F_j, l’inégalité à prouver est équivalente à 2F_{r_2} > 3 F_j.

Il y a deux cas de figure:

  • Si F_{r_2} et F_j ne sont pas des nombres de Fibonacci consécutifs, alors 2 F_j < F_{r_2}. En ajoutant l’inégalité F_j < F_{r_2}, on obtient bien 3 F_j < 2 F_{r_2}.
  • Si ce sont deux nombres de Fibonacci consécutifs, alors F_{r_2}=F_{j+1}. Donc
    2F_{r_2} - 3F_j = 2F_{j+1}-3F_j = 2(F_{j+1}-F_j)-F_j = 2F_{j-1} - F_j. Mais F_{j-1} et F_j sont deux nombres de Fibonacci consécutifs, donc 2F_{j-1} > F_j. Ce qui prouve que 2F_{r_2} - 3F_j > 0.

8. Explication de la stratégie gagnante

La proposition 1 nous dit que si N n’est pas un nombre de Fibonacci, alors en prenant F_{r_1} pièces, je suis sûr que mon adversaire ne peut pas gagner au tour suivant.

Les propositions 2 et 2bis nous disent que lorsque je prends F_{r_1} pièces, quelque soit le nombre de pièces prises par mon adversaire ensuite, ou bien le nombre de pièces restantes ne sera pas un nombre de Fibonacci (et dans ce cas, on recommence avec la proposition 1 avec un nombre de pièces qui est à présent inférieur) ou bien si le nombre de pièces est un nombre de Fibonacci, je suis sûr de gagner au tour suivant car le nombre de pièces est alors forcément inférieur au double de ce qu’aura pris mon adversaire (proposition 2 bis).

Aller, voilà le moment tant attendu de la description de la stratégie gagnante pour le joueur jouant en premier:

  1. On suppose que le nombre de pièces N au départ n’est pas un nombre de Fibonacci.
  2. Je décompose dans ma tête N en somme de nombres de Fibonacci non consécutifs. Si F_{r_1} est le plus petit nombre de la décomposition, je prends F_{r_1} pièces sur la table.
  3. Mon adversaire joue ce qu’il veut.
  4. Puis à mon tour de jouer. Soit je peux prendre le reste des pièces et je gagne. Sinon, je recommence à l’étape 2.

Dans l’exemple de départ, N=25. Je décompose 25 de tête comme une somme de nombres de Fibonacci non consécutifs. Pour cela, j’ai appris la suite 1, 2, 3, 5, 8, 13, 21. On a 25= 21 + 3 + 1. Donc, en tant que premier joueur, je vais prendre 1 seule pièce sur la table. Mon adversaire ne peut en prendre que 2 au maximum. S’il en prend une seule (par exemple), il en restera 23 sur la table. Et je recommence, en décomposant 23 comme une somme de nombres de Fibonacci non consécutifs: 23 = 21 + 2. Je vais donc prendre 2 pièces sur la table. Etc. jusqu’à la victoire.

Si vous souhaitez vous entraîner, vous pouvez vous rendre sur ce site, qui vous propose un petit applet pour jouer à ce jeu.

Avant de finir, vous devriez me demander: et si le nombre de départ est un nombre de Fibonacci ? Dans ce cas, passez votre tour et demandez à jouer en deuxième. En effet, quelque soit le choix de votre adversaire, le nombre de pièces restantes après la première pioche, vous pourrez soit gagner immédiatement, soit faire en sorte que votre adversaire ait à choisir parmi un nombre de pièces qui n’est pas un nombre de Fibonacci. Et on recommence comme précédemment.

Par exemple, si le nombre de pièces au départ est de 21 (nombre de Fibonacci) et que vous jouez en second. Si, après la première pioche, votre adversaire vous laisse avec un nombre de pièces qui n’est pas un nombre de Fibonacci, alors faites comme auparavant (choisir F_{r_1} pièces…). Sinon, la proposition 2 bis nous assure qu’on peut gagner au tour suivant. Si par exemple, il vous laisse avec 13 pièces sur la table, c’est qu’il en avait pris 8, et 2×8 est plus grand que 13. S’il vous laisse avec 8 pièces sur la table, c’est qu’il en avait pris 13, et 2×13  est plus grand que 8. Etc. Vous voyez le truc.

A voir: pour des variantes plus « simples » du jeu de Nim (dont le jeu des allumettes, appelé aussi jeu des « bâtonnets » dans Fort Boyard, dans lequel il ne faut pas prendre le dernier bâtonnet sur la table), vous pouvez consulter cet article du site Interstices ainsi que cet article du blog d’eljjdx.

Publicités
Cet article, publié dans Arithmétique, est tagué , , . Ajoutez ce permalien à vos favoris.

5 commentaires pour Devenez le maître d’une variante du jeu de Nim

  1. Ping : Un tour de magie mathématique… | Blogdemaths

  2. Ping : Un tour de magie mathématique… | Actumaths

  3. Ping : Un tour de magie mathématique… | Actumaths

  4. Thibaud REGNIER dit :

    Bonjour,

    Il me semble qu’il manque dans votre démonstration un morceau. Je reprends votre stratégie gagnante pour m’expliquer:

    1 On suppose que le nombre de pièces N au départ n’est pas un nombre de Fibonacci.
    2 Je décompose dans ma tête N en somme de nombres de Fibonacci non consécutifs. Si F_{r_1} est le plus petit nombre de la décomposition, je prends F_{r_1} pièces sur la table.
    3 Mon adversaire joue ce qu’il veut.
    4 Puis à mon tour de jouer. Soit je peux prendre le reste des pièces et je gagne. Sinon, je recommence à l’étape 2.

    Le problème est sur le « retour à l’étape 2 » à la fin de l’algorithme. En effet, comment sais-je que je vais pouvoir jouer F_{r_1}? (j’utilise les notations latex bien qu’elles ne compilent pas là dessus)
    Si on reprends à l’étape 2, j’ai un nombre N=F_{r_1}+…+F_{r_p}. Au moins au début j’ai tout le loisir de jouer F_{r_1} qui est la stratégie optimale. Le nombre à l’étape d’après est donc N_1=F_{r_2}+…+F_{r_p}.
    Comme démontré, l’adversaire joue r<=2F_{r_1}.

    On se retrouve donc dans une nouvelle situation où N'=N-r=F_{s_1}+…+F_{s_q} (qui n'est pas un nombre de Fibonnaci a priori). Puis-je maintenant jouer F_{s_1}?
    Il faut donc démontrer que F_{s_1}<=2r.
    On a N'=F_{r_p}+…+F_{r_3}+F_{r_2}-r.
    Or F_{r_2}-r<F_{r_2}<F_{r_3-1}.
    Donc le plus petit élément de la décomposition de Zeckendorf de N' est aussi celui de la décomposition de F_{r_2}-r.
    Donc F_{r_2}-r=F_{s_1}+…+F_{s_k} (pour un certain k<=q, et de plus k<r_2) et donc r=F_{r_2}-F_{s_k}-…-F_{s_1}.

    Calculons alors r-F_{s_1-1}=F_{r_2}-F_{s_k}-…-F_{s_1}-F_{s_1-1}.
    Or F_{s_k}+…+F_{s_1}+F_{s_1-1}=F_{s_k}+…+F_{s_2}<F_{s_k}+…+F_{s_3}+F_{s_3-1}<…F_{s_k+1}=0.
    Donc r-F_{s_1-1}>=0, r>=F_{s_1-1}

    De plus F_{s_1}<=2F_{s_1-1}<=2r.

    J'espère que cela permettra de compléter la démonstration.

    Cordialement

    Thibaud REGNIER

  5. Poursuivez dans cette direction, c’est un bonheur de vous suivre.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s