ou Résultats généraux sur les suites de Fibonacci.

Jeu de Nim-Fibonacci

On dispose d'un "tas" de N pions avec N2 ; note : le jeu de Nim proprement dit comporte plusieurs tas.
Deux joueurs retirent alternativement des pions, et le gagnant est celui qui arrive à vider le tas.
Les contraintes sont les suivantes : Au cours du jeu, un joueur peut être amené à laisser un seul pion (compte-tenu des contraintes précédentes : par exemple, son adversaire vient de retirer un seul pion et il en reste 3) ; auquel cas d'ailleurs il perd le coup suivant.

Soit n1, le nombre de pions à l'issue d'un nombre quelconque de retraits (n peut être égal à N).
Bien sûr le joueur qui hérite de cette situation doit, soit tout retirer s'il le peut, sinon il doit retirer moins de n/3 jetons (sinon il va en retirer rn/3, donc il va en rester n'=n-r2n/3 2r, et son adversaire pourra retirer tous les pions le coup suivant!).
Malheureusement, cette remarque ne suffit pas à mettre au point une statégie gagnante.

Par contre, il est possible d'élaborer une stratégie gagnante en considérant (voir P11) la décomposition de Zeckendorf (notée Z_d) de n :

la Z_d de n s'écrit n=F(ik)+...+F(i2)+F(i1) avec ijij-1+2, i12 : elle comprend k termes, (k1). Le plus petit terme de la Z_d de n, F(i1), sera noté fn. La preuve de cette stratégie gagnante reposera sur le 3) de P11.

On a les propriétés suivantes (si on le souhaite, on peut ne lire que l'aspect n6 ci-dessous : c'est la conclusion, qui donne la stratégie gagnante) :

en effet, pour le cas fn<n : a) F(i2) et F(i1) n'étant pas consécutifs, F(i2)F(i1+2)=F(i1+1)+F(i1)>2F(i1)=2fn : comme le joueur B peut retirer au plus 2fn, c'est que K<F(i2) ; quant à 1K, cela résulte des contraintes.

b) Il s'agit de montrer maintenant que fn'2K.
Il suffit d'appliquer le 3) de P11 en prenant e=n-F(i1), donc fe=F(i2) (rappel : k2), soit fe3 (puisque F(i2) et F(i1) ne sont pas consécutifs).
Comme 1K<F(i2) on a 1K<fe et n' étant n-F(i1)-K, on a n'=e-K, donc le 3) de P11 donne fn'2K.
Ainsi le joueur A peut retirer fn' pions du tas, cela, peu importe si ce fn' est égal ou non à n'.

  • 5) Si le joueur (A) qui hérite d'un tas contenant n(1) pions en retire fn (c'est le plus petit terme de la Z_d de n) pions (cela si les contraintes du jeu le permettent), alors ce joueur est certain de pouvoir gagner la partie (quoique fasse l'autre joueur) : soit il gagne à ce coup, sinon il suffit qu'à chaque fois que ce sera ensuite son tour de jouer, il retire du tas un nombre de pions égal au plus petit terme de la Z_d du nombres de pions constituant alors le tas (il pourra effectivement le faire)
    en effet soit fn=n (cad n est un terme de la suite (F)) et A gagne tout de suite
    soit fn<n, et cf 4), l'autre joueur B ne peut tout retirer, et si n' est le nombre de pions laissés par B, A peut en retirer fn' soit fn'=n' et A gagne
    soit fn'<n' et B ne peut tout retirer et laisse n'' pions dont A peut en retirer fn" etc...
    Comme le nombre de pions restant sur le tas diminue strictement à chaque retrait, le jeu ne peut "éternellement" continuer, donc au bout d'un nombre fini de retraits le nombre de pions restant sera un terme de (F) et A pourra alors les retirer tous et donc gagnera.
  • 6) Conclusion
    N étant le nombre de pions du tas au départ,
    • soit N est différent d'un terme de (F) et le 1er joueur à jouer est certain de pouvoir gagner, en retirant à chaque fois qu'il joue un nombre de pions égal au plus petit terme de la Z_d du nombre de pions constituant alors le tas.
    • soit N est un terme de (F) et le 2ième joueur à jouer est certain de pouvoir gagner, en retirant à chaque fois qu'il joue un nombre de pions égal au plus petit terme de la Z_d du nombre de pions constituant alors le tas.
    Ces deux aspects se résument par
    Un joueur est certain de pouvoir gagner ce jeu de Nim-Fibonacci
    c
    il joue en 1er et N n'est pas un terme de la suite (F)
    ou
    il joue en 2ième et N est un terme de la suite (F)

    en effet

    si N est différent d'un terme de (F) c'est que fN<N, et donc le 1er joueur à jouer peut retirer fN pions et, cf 5), il est donc certain de pouvoir gagner.

    si N est un terme de (F), le 1er joueur ne peut retirer fN=N pions puisqu'il doit en laisser au moins 1 (voir contraintes), donc il va en retirer K<fN et il restera n'=fN-K pions.
    On peut alors encore appliquer le 3) de P11 avec e=fN=N, donc fe=fN=N2. Comme 1K<fN et n'=e-K, ce 3) de P11 donne alors fn'2K.
    Ainsi le 2ième joueur va pouvoir retirer fn' pions et, cf 5), il est certain de pouvoir gagner.

  • 7) Remarque 1 : lorsqu'un joueur hérite d'un tas constitué de n pions (n2) et en retire moins que fn , il est alors certain de perdre si son adversaire retire à chaque fois qu'il joue un nombre de pions égal au plus petit terme de la Z_d du nombre de pions constituant alors le tas (il pourra le faire).
    En effet on applique encore le 3) de P11 avec e=n, donc fe=fn ; comme le joueur retire (effectivement) K pions avec K<fn, c'est que fe=fn2 et ainsi 1K<fe et donc, en posant n'=e-K, le 3) de P11 donne fn'2K. Mais ce n' n'est autre que le nombre de pions restants, et donc son adversaire pourra en retirer fn' pions le coup suivant et ainsi cf le 5) ce dernier est certain de pouvoir gagner.
  • 8) Remarque 2 : lorsqu'un joueur hérite d'un tas constitué de n pions (n2) et peut en retirer fn , il ce peut que ce soit la seule valeur à ôter lui assurant de pouvoir gagner.
    Exemple : dans le cas n=88, la seule valeur à ôter assurant de pouvoir gagner la partie est 1=f88!
    en effet (on appelle A le joueur qui hérite de ce tas, B son adversaire) n=88=55+21+8+3+1=F10+F8+F6+F4+F2, donc f88=F2=1
    si A ôte 1=f88, il est certain de pouvoir gagner, cf le 5)
    si A ôte 2 pions, il reste n'=F10+F8+F6+F4 : B peut en ôter fn'=F4=32×2, et donc cf 5) c'est B qui est certain de pouvoir gagner
    si A ôte 3 pions, il reste n'=F10+F8+F6+F2 : B peut en ôter fn'=F2=12×3, et donc cf 5) c'est B qui est certain de pouvoir gagner
    si A ôte 4 pions, il reste n'=F10+F8+F6 : B peut en ôter fn'=F6=82×4, et donc cf 5) c'est B qui est certain de pouvoir gagner
    si A ôte 5 pions, il reste n'=F10+F8+F5+F3 : B peut en ôter fn'=F3=22×5, et donc cf 5) c'est B qui est certain de pouvoir gagner

    etc...(je laisse le lecteur écrire les cinq cas manquants)

    si A ôte 11 pions, il reste n'=F10+F8+F2 : B peut en ôter fn'=F2=12×11, et donc cf 5) c'est B qui est certain de pouvoir gagner
    si A ôte 12 pions, il reste n'=F10+F8 : B peut en ôter fn'=F8=212×12, et donc cf 5) c'est B qui est certain de pouvoir gagner
    si A ôte x pions avec x{13; 14; .... ; 29}, on ne va pas "toucher " à F10, cad la Z_d de n'=n-x aura un plus petit terme forcément inférieur à F8=212x, et donc cf 5) c'est B qui est certain de pouvoir gagner.
    Enfin, si A ôte plus de 29 pions, c'est que le nombre de pions ôtés est n/3=29,3 et dans ce cas le joueur B gagne le coup suivant puisqu'il pourra tout ôter!
  • Remarque 3 : lorsqu'un joueur hérite d'un tas constitué de n=F(ik)+...+F(i2)+F(i1) pions, et qu'il ne peut tout ôter, mais simplement ôter fn pions (ce qui lui assure d'être certain de pouvoir gagner, cf 5)), il peut "accélérer son processus de victoire", en ôtant s=F(ik-1)+...+F(i2)+F(i1) pions, ceci, à la condition express que s vérifie les deux conditions s2×le nombre de pions ôtés par le joueur précédent et s<n/3.

    En effet, il va rester F(ik) pions que son adversaire ne pourra ôter entièrement ( car s<n/3 F(ik)=n-s>2s), et donc son adversaire va perdre (voir 6) : cas du joueur qui est le 1er à jouer avec N=fN et qui ne peut tout retirer).

    Bien entendu cette possibilité est plus rare que celle d'ôter F(i1) pions, à cause des deux limitations indiquées ci-dessus.
    D'ailleurs, si on revient sur l'exemple précédent n=88=F10+F8+F6+F4+F2, on a s=F8+F6+F4+F2=33n/3 : il n'est donc pas question d'ôter s.

    Enfin, ôter plus que s (toujours lorsque cela est possible) n'assure pas le gain de la partie.
    Par exemple pour n=99=F11+F6+F3 :

    le joueur qui ôte F3=2 pions est certain de pouvoir gagner, cf le 5),
    de même s'il ôte s=F6+F3=10 pions, cf ci-dessus ;
    mais s'il ôte 11 pions, il en reste 88 et c'est son adversaire, pouvant ôter 1 pion, qui est certain de pouvoir gagner : voir exemple du 8).