jeu des allumettes

[invite6f044255]

Salut,

dans ce jeu, je rappelle qu'on a 5 colonnes d'allumettes

_ _ _ _ _
_ _ _ _
_ _ _
_ _
_

comme ceci.
2 joueurs s'affrontent, chacun, à son tour, prenant autant d'allumettes qu'il veut mais dans une seule colonne à chaque fois.
Celui qui prend la dernière a perdu.

J'ai cherché si le premier coup était gagnant ou perdant...j'ai trouvé (il est gagnant!!), mais cela a soulevé un problème, qui est le suivant:
comment calculer le nombre de situations de jeu?
(en les écrivant toutes, j'en ai trouvé 131, si je me souviens bien....)
Quelle formule permettrait de déterminer ce nombre?
-----

[invite5df0385c]

C'est un graphe, il te suffit de partir d'une solution gagnante, ex (une ou n allumettes sur un même colonne) pour arriver à la composition initiale en ne retenant que les coups gagnants:
ex :
1) - OU -- OU --- OU ---- OU -----
2) - => - => 1) gagné
- -
-
3) - => - => 1) gagné
-- -
4) - => 3) gagné
--
--
...
k) jusqu'à l'état initial

[invite6f044255]

Oui, ça je l'ai fait ep31, j'ai pas de problème là-dessus!!
ce n'est pas ma question, relis bien mon post!!

[DonPanic]

Slu
Le jeu des allumettes s'appelle le Marienbad, parce que c'est le film "L'année dernière à Marienbad" qui l'a popularisé.
Je connais toutes les combinaisons gagnantes, alors ça lasse.
j'avoue n'avoir jamais cherché à en faire un graphe ou une équation
2 suites égales sont gagnantes, deux fois deux suites égales sont gagantes, 123 est gagnant

[A voir en vidéo sur Futura]

[invite6f044255]

oui mais 11145 est gagnant, de même que 12335 ou 02345!! Au total il y en a 21 qui sont gagnantes!!

Mais c'est pas ma question!!

[DonPanic]

Je crois qu'auparavant c'était un jeu de rue baisegogo,
on laissait gagner le quidam, et on lui faisait les poches en paris
VAZY IXI,
ça fait plaisir de voir faire le boulot qu'on a toujours eu la flemme de faire soi-même
toutes les sommes paires sont gagnantes, non ?

[DonPanic]

Non pas 2x+2x+n, somme paire valable pour nombre impair de colonnes
Xkuzz quand je joue, mes yeux et ma main font mieux que mon cerveau

[invite6f044255]

salut,

oui 1111 ou 1122 ou 1133 ou 1144
2222 ou 2233 ou 2244
tout ça c'est gagnant, mais....
c'est pas ma question!!!!

Si je la pose, c'est que je n'ai pas réussi à déterminer ce nombre tout seul....pourtant j'ai cherché!!!

[pi-r2]

et oui, ixi, c'est le combinatoire, et ça a toujours été pénible. Je suppose que quand tu parles de dénombrer les situations tu veux dire:
on compte la situation où il n'y a plus d'allumette ?
où que soit la dernière allumette, cela compte pour une seule situation ?
sur la rangée à 5 allumettes, quand il y en reste 3 par exemple, leur position ne compte pas non plus comme une solution différente ?
Au départ 15 allumettes et une seule position.
1 situation à 1 allumette
2 situations à 2 allumettes
3 situations à trois allumettes.
5 situations à 4 allumettes.
7 situations à 5 allumettes.
... ca doit pas être la bonne méthode. Chui fatigué ce soir...

[DonPanic]

Tiens, la version que je connaissais

[invite070c425f]

Oui, moi aussi, y compris le nom "Jeu de Nim".
Je ne me souvenais plus si on avait 4 rangées (1-3-5-7) ou 5 (1-3-5-7-9).
Sur un jeu parfait celui qui commence perd.
J'avais établi l'arbre il y a quelque temps. On en déduit une stratégie simple, et qu'il y a quelques positions de base à retenir, donc il est facile de gagner à coup sûr pour toute personne normale.
Ne m'en demandez pas plus, il y a très longtemps que j'ai oublié les détails.
Amitiés.
Félix

[invite15029802]

Bonsoir tout le monde, moi j'aimerais savoir comment gagner à ce jeu, avec au départ 16 allumettes disposées comme ceci :
I
I I I
I I I I I
I I I I I I I

svp, merci.

EDIT : je ne m'aperçois qu'après avoir posté que le dernier message date du 27/8/2004, désolé pour le nécropostage mais je suis obligé, j'en ai besoin maintenant

[invite35452583]

Ca tombe bien, je l'avais déjà étudié ce jeu.
Une position perdante est caractérisée ainsi :
on écrit le nombre d'allumettes en base 2 pour chaque colonne.
Exemple avec la disposition initiale :
1=1 ; 2=10 ; 3=11 ; 4=100 ; 5=101
On peut les mettre dans un tableau ainsi :

s'il y a au moins une colonne ayant strictement plus d'une allumette alors la situation est perdante si et seulement si le total de chaque ligne est pair (que le jeu soit "celui qui prend la dernière perd" ou que ce soit "celui qui prend la dernière gagne").
Je vous laisse deviner la CNS pour que la situation soit gagnante ou perdante si toutes les colonnes ont au plus une allumette.
Ici, la situation est donc gagnante et pour envoyer une situation perdante à l'adversaire il faut retirer une allumette à la 1ère, 3ème ou 5ème colonne.
Preuve :
Soit une situation "déséquilibrée" (le total d'une ligne est impaire) alors
soit il n'y a qu'une colonne avec 2 allumettes ou plus, et il suffit de retirer toutes les allumettes sauf éventuellement une selon la parité du nombre de colonnes non vides.
soit il y a plus d'une colonne avec 2 allumettes et on peut alors renvoyer une situation équilibrée. En effet, soit la ligne la plus haute dont le total est impaire, puisque ce nombre est impaire il y a au moins une colonne pour lequel c'est un "1", à partir de cette colonne, pour chaque ligne de rang inférieur on change la valeur "0" ou "1" selon que le total de la ligne est pair ou impair.
Exemple : situation déséquilibrée (les nombres sur les bords haut et gauche sont les numéros de ligne et de colonne) :

Il faut donc jouer sur la 3ème colonne en laissant le "0" de la 5ème,
on change 1er changement est toujours en "1" en "0") le "1" de la 4ème ligne en "0" : retrait de 16 allumettes
on change le "1" de la 3ème ligne en "0" : retrait de 8 allumettes
on laisse le "0" de la 2ème ligne
on change le "1" de la 1ère ligne : ajout de 2 allumettes
on laisse le "1" de la 0ème ligne
Bilan retrait de 11000 allumettes en binaire (24=16+8 allumettes) des 11001=25 allumettes et ajout de 00010 allumettes en binaire (2 allumettes). On en retire donc au total 22 des 25 allumettes. On a alors la situation des colonnes :

On retire donc un certaine somme de puissances de 2 allumettes (changement de certains 1 en 0), d'une part, et on en ajoute une autre somme (changement de 0 en 1) d'autre part.
La somme retirée au total est inférieure à la 1ère somme qui est elle-même inférieure au nombre d'allumettes au départ puisque ces "1" sont dans la somme de puissances de 2 =nombre total d'allumettes. On ne retire pas plus d'allumettes à cette colonne qu'elle en avait.
La somme ajoutée est inférieure à 1+2+4+8+...+2^i-1 si la 1ère ligne modifiée est de rang i. Mais cette somme est égale à 2ⁱ-1 donc <2ⁱ, on retire donc bien au moins une allumette de cette colonne et on respecte donc bien la règle.

Maintenant à partir d'une situation équilibrée, en retirant sur une colonne on modifie l'écriture et le total d'une ou plusieurs (mais dans tous les cas au moins une) lignes d'une unité et donc la parité de ces lignes. La situation n'est donc plus équilibrée. D'autre part, le nombre de colonnes avec au moins 2 allumettes n'est pas 1, en effet le nombre écrit en binaire serait alors la seule à avoir autre chose que "0" sur une des lignes de plus haut degré que 0 et le total de cette ligne serait impaire contredisant le caractère équilibré de cette colonne.

Conclusion : en renvoyant toujours une situation équilibrée (tant qu'il y a au moins deux tas avec strictement plus d'une allumette) à son adversaire on s'assure que l'on sera celui (ou celle) qui gagnera la parité au moment d'arriver à une situation où il n'y a plus que des tas de 0 ou 1 allumette.

Ainsi, dans la disposition 1-3-5-7, on a :

qui est une situation équilibrée donc perdante si l'adversaire joue bien.

[invite15029802]

Ainsi, dans la disposition 1-3-5-7, on a :

qui est une situation équilibrée donc perdante si l'adversaire joue bien.

et comment on fait pour gagner ?

[invite9300be19]

Homotopie a parfaitement raison. Il y a 30 ans que je connais cette solution, qui fait que l'adversdaire peut choisir un nombre quelconque de tas et dans chaque tas un nombre quelconque d'allumettes. Il choisit aussi de commencer le premier ou non. Chacun doit choisir un tas à son tour de jouer et y prendre au moins 1 allumette, jusqu'à la totalité du tas s'il le désire. Celui qui prend la dernière allumette a gagné.
En convertissant en binaire le nombre d'allumettes de chaque tas et en faisant en sorte que le total de "1" de chaque colonne soit pair à la fin du coup, celui qui commence est certain de gagner à 100%. S'il commence en second, à la première erreur de l'adversaire (qui ne la voit même pas s'il ne connait pas le truc) il reprend la main et sera sûr de gagner également à 100%.
En continuant ainsi jusqu'à la fin, on prend automatiquement la dernière allumette et on gagne. Toutes les autres solutions positionnelles sont inutilisables avec ce procédé.