Bonjour,
La technique est voisine de celle  du jeu de Marienbad.

Oui, il va falloir faire un peu "d'arithmétique" sur le nombre N.
Mais ce n'est pas du binaire a priori. C'est plus "romantique".

Bonjour

J'avais étudié ce jeu il y a un petit moment . Je ne dévoile pas la solution mais je donne un indice :

 Cliquez pour afficher

Suite de Fibonacci

exact

Bonjour,
la stratégie "de tête" n'est pas claire du tout

j'ai tracé le graphe complet du jeu avec 10 allumettes au départ
dans un repère avec le nombre d'allumettes restantes et le nombre d'allumettes prises au dernier coup pour y arriver

c'est là la difficulté : à cause du "k" l'état d'une position dépend non seulement du nombre d'allumettes restantes, mais aussi du nombre d'allumettes prises par le joueur précédent !



toutes les positions où il reste 0 allumettes sont perdantes (et même perdues) en rouge. sur l'axe des abscisses.

Si depuis une position P il existe un arc (rouge) descendant menant à une position perdante rouge (au moins) la position P est gagnante (points verts) : en jouant l'arc rouge je donne une position perdante à l'adversaire.

si depuis la position P il n'existe que des arcs menant à une position gagnante, alors P est perdante (points rouges) :
je suis obligé de donner une position gagnante à l'adversaire.

ainsi on voit que à partir de au départ 10 allumettes
le premier joueur gagne en prenant 2 allumettes.
(faux si c'est en cours de jeu : ça dépend du coup précédent !!)

En effet une position est parfaitement décrite par le nombre d'allumettes restant et le nombre d'allumettes enlevées lors du dernier retrait ( R,E) .  Les couples (R,E) sont gagnants ou  perdants , il reste à les caractériser .

Imod

En effet, il faut analyser les situations gagnantes/perdantes de manière récursive. Par exemple :

N = 1 gagne en prenant 1
N = 2 gagne en prenant 2
N = 3 gagne en prenant 3 sinon perd !
N = 4 gagne en prenant 1
N = 5 gagne en prenant 5 sinon perd !
N = 6 gagne en prenant 1
N = 7 gagne en prenant 2
etc.

Vous alle remarquer quelque chose. C'est la première étape.

Bonjour,

En observant les fins de partie on arrive à  ces cas.
A joue avant B
Les deux derniers coups sont décisifs:
Soit R  le reste. si  R =0 après A  --.>B   a perdu
                                        R=1  --->B gagne
                                        R=2---> B gagne  
                                        R=3--->B gagne  si  A >1   donc A retirera 1
                                        R=4--->B gagne si  A>1      donc A retirera 1
                                        R=5---> B gagne si  A>2     donc A retirera  1 ou 2
Ma tactique de jeu consistera à aller très vite vers ces R
en doublant systématiquement .
Ensuite on voit que la défensive est souvent -1
                                          
    

il faut continuer avec de R un peu plus grand pour voir apparaître certains nombres décisifs.  Ce sera la première étape.

certes, les nombres d"allumettes laissées à l'adversaire
= 0, 3, 5, 8, 13, 21 ... sont"inéluctables" si on veut gagner
mais d'autres aussi sont nécessaires pour ce faire !
(on ne peut pas forcer l'adversaire à nous laisser atteindre ces nombres là sans être obligé de passer par des restes intermédiaires)
et c'est ces restes intermédiaires qui ne sont pas du tout évidents !

exemple N = 20 graphe de toutes les positions possibles (reste, prise) sans l'intégralité de tous les arcs possibles de ce graphe (bien trop fouillis)

comme précédemment
en vert les positions gagnantes d'où l'on peut toujours atteindre une position rouge
en rouge les positions perdantes que l'on doit laisser à l'adversaire pour gagner
seuls sont indiques les arcs gagnant depuis la première position verte de la ligne, toutes les autres de cette ligne pouvant entre autres aboutir au même point rouge.

Comme disait Leon1789 , c'est une première étape

D'un autre côté tout entier naturel se décompose de façon "unique" en une somme de termes de la suite de Fibonacci .

Imod

Ah, le temps que j'écrive ma réponse, Imod m'a grillé de 3 minutes !  hahaha !
Et comme par enchantement, on donne le même indice.

Bonsoir

en ayant fait tourner un algorithme , les chances de gagner de A et B sont les memes

"les chances" pour un jeu à issue certaine... hum.

Si je peux me permettre une petite parenthèse . On m'a soumis ce petit problème il y a très longtemps et je n'ai jamais trouvé de solution "officielle" . Comme à l'accoutumée , j'ai peiné à trouver une solution  en ramant comme un malade pendant des semaines . Même si celle-ci est relativement simple , j'ai hâte de voir si la solution de Leon1789 ou de quelqu'un d'autre diffère de la mienne .

Imod

pour valider une conjecture de stratégie il va falloir aller jusqu'à des nombres très grands
rien ne dit que la régularité conjecturée jusqu'à une trentaine de valeurs de départ puisse se poursuivre au delà
à moins d'en trouver une démonstration
pas gagné ... face à un adversaire réputé vicieux !

_{j'ai bien dans un autre problème une suite 1,2,3,5,8,13,21, ...
dont le terme suivant est 30 et pas 34 ! (A011185)
c'est comme le célèbre 1, 2, 4, 8, 16, 31 ! A000127}

les points intermédiaires semblent être le dernier Fn < N plus les sommes de Fn >= 3
exemple N = 30, Fn = 21, points intermédiaires entre 21 et 30 : 21 + 3, 21+5, 21+8

(et il faudra de plus faire attention à ne pas arriver n'importe comment sur un reste intermédiaire ! ni même sur un Fn d'ailleurs)

Il y a une façon très simple de caractériser les couples (x,y) gagnants avec x le nombre d'allumettes restantes et y le nombre d'allumettes retirées au dernier coup , il suffit de regarder le plus petit terme dans la décomposition en somme de termes Fibonacci . Après il faut justifier et c'est un peu plus compliqué .

Imod

Bonsoir,
(pour ma part, ça fait 15 ou 20 ans que je connais ce jeu d'allumettes)

En effet, la stratégie gagnante est de décomposer le nombre d'allumettes restantes R en "somme de Fibonacci" comme expliqué ci-dessus par Imod : on peut forcer le gain si (et seulement si) on peut prendre le plus petit terme de la décomposition.

Remarque : parfois, il y a plusieurs coups gagnants. Exemple :
Au cours d'une partie, le jouer A vient de prendre 2 allumettes et il en reste 17 sur la table.
On décompose 17 = 13 + 3 + 1
Alors prendre 1 ou 4 (=3+1)  allumettes sont deux  coups gagnants.

Je pense que la preuve par récurrence forte n'est pas si compliquée.

J'ai perdu mes brouillons de l'époque mais je me souviens que j'avais pas mal peiné à justifier qu'en retirant le plus petit terme de la décomposition en Fibonacci  , on donnait  forcément une position perdante à l'adversaire . J'avais sans doute raté une étape importante

Imod

hum, si l'adversaire fait pareil il me donne une position perdante ?

il faut la condition si ma position est gagnante, alors en retirant ...

et ça je ne le sais que en considérant le dernier coup :
les nombres restant ne suffisent pas, il faut aussi tenir compte du nombre retiré précédemment pour savoir si je peux effectivement en retirer autant que ça.

et pour que la récurrence à deux joueurs fonctionne il faut prouver que quel que soit ensuite le coup de l'adversaire, il me donnera une position gagnante.
c'est là la difficulté.

Il me semble que tu as mis le doigt sur ce qui m'avait titillé à l'époque .
J'avais trouvé une solution mais il faudrait que je la retrouve

Imod

Quelques coquilles typo dans mon message précédent :

Si le joueur retire allumettes, alors il laisse une position perdante à son adversaire (car ).

Reste à Prouver (pour terminer l'hérédité de la preuve par récurrence) :
Si le joueur ne peut pas retirer allumettes, alors alors il laissera forcément une position gagnante à son adversaire.

Bonjour,
Je pense qu'il faut anticiper le reste et éviter au maximum les doublements à partir de R=8 .
Celui  qui à la main est fortement avantagé car il peut laisser le reste
qui fera perdre son adversaire puisqu'il connait la fourchette qu'il
pourra jouer  .
Donc il faut favoriser les petits retraits de 1 et exceptionnellement de 2.

on n'a pas le choix de 1 ou 2, la stratégie expliquée au dessus impose ce qu'on doit retirer pour gagner.

alors c'est vrai que si on a une position perdante, on peut faire des petits retraits pour faire durer la partie plus longtemps et espérer que au long cours l'adversaire fera une erreur de calcul ...

Bonsoir , comment ca se passe dans ce scenario ?
n=20

a = 2  , reste  18
b choisis entre 1 et 4 et choisit 4  , reste  14
  a  choisis entre 1 et 8 et choisit 8  , reste  6
  b choisis entre 1 et 16 et choisit 9  ,que ce passe t il apres?

En partant de N=20
20 = 13 + 5 + 2
A prend donc 2 (pour gagner)
reste 18
B choisit de prendre 4
reste 14 = 13 + 1
A prend donc 1 (pour gagner)
reste 13
B choisit de prendre 2
reste 11 = 8 + 3
A prend donc 3 (pour gagner)
reste 8
B sent la fin arriver et choisit de prendre 1
reste 7 = 5 + 2
A prend donc 2 (pour gagner)
reste 5
B sent la fin arriver et choisit de prendre 1
reste 4 = 3 +1
A prend donc 1 (pour gagner)
reste 3
B abandonne...

ma question était basé sur un choix purement aléatoire pour nos joueurs , c'est à dire sans  strategie de la part de B ou de A .

Mais ce qui est intéressant dans ce problème c'est la/les stratégies justement.

Si les joueurs prennent au hasard les allumettes (avec équiprobabilité entre les choix possibles) alors autant jouer à pile ou face.

def play(n):
    k = 1
    while n > 0:
        r = randint(1, min(k * 2, n))
        yield r
        n -= r
        k = r


def main(n=20, t=10000):
    count = 0
    for _ in range(t):
        if len(list(play(n))) % 2 == 0:
            count += 1
    print(count/t)

Je vais regarder en détails la démonstration de Leon1789 car il faut faire extrêmement attention à "l'unicité" de la décomposition . Il y a bien unicité si on retire progressivement les termes en commençant par le plus gros mais comme   , on peut souvent trouver plusieurs décompositions . Par contre il y a bien unicité si on exige que les indices ne soient  jamais des entiers consécutifs .

Imod

J'ai écrit la démo sur plusieurs messages, ce qui la rend peut-être peu lisible. En plus, je n'ai pas formulé clairement l'hypothèse de récurrence...

Oui , reprendre l'ensemble de la démo sur un message et être clair quand on fait référence à "l'unicité" de la décomposition . Je peux paraître pénible mais l'exercice est sans doute plus subtil qu'il en a l'air

Imod

Je résume la preuve.
Quand on dit "situation perdante/gagnante", on suppose évidemment que les joueurs jouent parfaitement.


Préliminaire :
La décomposition de Zeckendorf (en somme de termes non consécutifs (*) de la suite de Fibonacci ) d'un entier N s'écrit

où désigne le i-ème nombre de Fibonacci ()
et les sont égaux à 0 ou 1, et tels que deux consécutifs ne peuvent pas être égaux à 1 tous les deux (*).
Cette décomposition est unique.

R désigne le nombre d'allumettes restantes sur la table.
La main est au "joueur", l'autre étant son "adversaire".

Citation :
Pour un entier , soit l'assertion :
Soit le plus petit nombre de Fibonacci figurant dans la décomposition de Zeckendorf de R.
(1) Si le joueur peut prendre allumettes alors la situation est gagnante (en prenant allumettes) ;
(2) Si le joueur prend m allumettes, avec , alors cela amène une situation perdante pour ce joueur.

Des coquilles que je vois toujours après avoir posté...

[...] pour tout [...]

[...]   [...]

[...] contraire à l'unicité de la décomposition de Zeckendorf de R [...]

[...] [...]

[...]   [...]



Pourtant, j'ai essayé de faire bien

Je retrouve certaines questions des que je m'étais posées . On est tout de même assez loin d'une "simple" récurrence
Imod

oui loin d'une "simple" récurrence : récurrence "forte", avec deux assertions croisées (normal car on est en situation de jeu alternatif) et contenant un petit raisonnement par l'absurde.