Tactique gagnante

[Evil.Saien]

Salut,

Par hasard j'ai trouve un jeu original (je connaissais pas).

http://www.transience.com.au/pearl.html

Existe-t-il une tactique gagnante pour ce jeu ?

++
-----

[Shiho]

Je sais pas mais ça m'intéresserai j'ai perdu à tous les coups... :s

[invite6de5f0ac]

Bonsoir,

Pareil que Shiho...

En examinant d'un peu plus près le cas où il n'y a que deux rangées, j'ai la furieuse impression que c'est celui qui commence qui est b...é.

Et on dirait bien que ça reste valable avec 3 rangées, ou peut-être même un nombre quelconque, les diagrammes en 4D c'est pas mon fort.

Pas de vraie preuve pour l'instant, mais je m'y attelle...

-- françois

[invite30b80147]

Bon j'ai trouvé une technique qui marche a tout les coups...

Au debut, prendre 2 perles de la rangé de 3 perles, puis prendre 3 perles de la rangé de 5perles, puis faire en sorte quil ne reste que 2 rangés de 2 boules, et voila c gagnééé...

[A voir en vidéo sur Futura]

[matthias]

Il y a toujours une stratégie gagnante pour l'un des deux joueurs. Ca peut être pour celui qui commence ou pour l'autre en fonction de la configuration initiale des billes.
Et on sait déterminer la stratégie gagnante quelle que soit la configuration initiale, comme pour à peu près toutes les versions du jeu de Nim (ou jeu de Marienbad).

[invite6de5f0ac]

Bon j'ai trouvé une technique qui marche a tout les coups...

Au debut, prendre 2 perles de la rangé de 3 perles, puis prendre 3 perles de la rangé de 5perles, puis faire en sorte quil ne reste que 2 rangés de 2 boules, et voila c gagnééé...

OK, ça marche... Donc je retire ce que j'ai dit. Et au passage, merci à matthias, c'est exactement ce que j'essaye de déterminer. Je crois en fait que ça dépend surtout du nombre de rangées de perles (pair ou impair peut-être).

Voilà mon ébauche de raisonnement. Je fais un diagramme (pour deux rangées) avec les axes comme en maths (nombre de perles dans la première rangée en abscisse, da,ns la deuxcième en ordonnée). Et je mets G , resp. P, dans la case (x,y) si cette situation est gagnante, resp. perdante.
Donc G en (0,0) ; P en (1,0) et (0,1). Maintenant, toutes les cases à droite ou au-dessus d'une case P sont G (puisqu'on peut atteindre une case P en se déplaçant parallèlement à un axe). Une case qui n'a à sa gauche et en-dessous que des cases G est forcément P. Et ainsi de proche en proche. Avec seulement deux rangées, on voit immédiatement que les cases P sont les (x,x) pour x >=2, toutes les autres sont G. Donc avec deux rangées celui qui commence peut toujours laisser une case P à son adversaire... Donc il gagne à tous les coups.
Avec trois rangées ou plus, le dessin est plus dur à faire, mais le principe est le même. Je mets ça au propre et je vous tiens au courant...

Salut,

-- françois

[invite04fcd5a3]

salut

rho theta point t'es un dieu!

[invite35452583]

Indice pour la tactique gagnante dans le cas général : écrire le nombre de perles en base 2.

[invite6de5f0ac]

Indice pour la tactique gagnante dans le cas général : écrire le nombre de perles en base 2.

Aaaaaah! Enfin!

Bonsoir,

Je me doutais bien que notre homotopie préféré nous sortirait un théorème de point fixe plus ou moins sophistiqué...

Bin oui, en base 2, c'est bien ce que je pensais: suivant la parité du nombre de rangées et du nombre de perles, on peut ou non arriver à forcer une configuration perdante (pour l'adversaire).

Rassuré de voir que mon intuition n'était pas trop idiote.

Et BTW, c'est vrai que c'est une n-ième variante du jeu de Nim. Problème auxiliaire: si un problème P_n est la n-ième variante du jeu de Nim, caractériser ses tactiques optimales en fonction de l'écriture de n en base 2 ...

-- françois

[invite35452583]

Le premier indice était peut-être un peu faible et facile Une petite démo ?
Commençons par écrire le nombre de chaque pile en base 2

On appelle p-somme (contraction avantageuse de somme des nombres piles en base 2 sans retenue ) la suite (indice i) () les sommes se faisant modulo 2.
On dit que la situation est de type 2) si au moins des piles contient deux perles ou plus, elle est de type 1) sinon.
Une situation de type 1) est gagnante si et seulement si le nombre total de perles est pair (évident)
Une situation de type 2) est perdante si et seulement si la p-somme=(0,0,0,...,0,...)=(0)
Montrons ce dernier point :
1ère remarque, si un joueur peut durant toute la partie envoyer une situation de la forme 2) avec p-somme=(0) est celui qui laissera pour la première fois un "plateau" où toutes les piles ont une ou zéro perle et pourra choisir la parité donc gagne.
Si on retire une ou plusieurs perles d'une seule pile d'une situation de la forme 2), soit la décomposition en base 2 du nombre de perles retirées. On a p-somme de la nouvelle situation= (bienvenue au pays du -1=1) donc est différente de (0).
Soit une situation pour laquelle p-somme= distincte de (0).
Soit la plus grande valeur pour laquelle est distinct de zéro. Par définition il existe une pile k pour laquelle est égal à 1. On retire cela fait apparaître i_m +1 zéros dans les premiers termes de la décomposition de la pile k.
La nouvelle p-somme = ne contient que des zéros à partir de (compris) car il n'y a pas de retenues. On remet dans cette k-ème pile . La nouvelle p-somme=(0).
A remarquer que ce que l'on remet est inférieur à donc inférieur strictement à ce qui est initialement retiré. La véritable quantité retirée est donc bien strictement positive (la règle est respectée).

Il est plus simple de remplacer les piles par des cartes placées en étages (les puissances de 2) il faut toujours renvoyer une situation où chaque étage est pair (c'est possible si et seulement si ce n'était pas déjà le cas) sauf si il n'y a plus que le rdc, situation dans laquelle on renvoie une situation impaire.

Je ne sais décidément pas compter au-delà de 2

[invite6de5f0ac]

(voir son message!)

Bravo.

-- françois

[BABAR]

Ce jeu est assez vieux et s'appelle "le jeu de Marienbad".
A l'origine il y a 4 rangées comportant respectivement :
7 - 5 - 3 - 1 perles (où ce que vous voulez).
On y jouait au lycée avec des allumettes.

[matthias]

Ce jeu est assez vieux et s'appelle "le jeu de Marienbad".

On ne l'appelle jeu de Marienbad que depuis le film "L'année dernière à Marienbad". Cette appellation est donc assez récente ...

[BABAR]

On ne l'appelle jeu de Marienbad que depuis le film "L'année dernière à Marienbad". Cette appellation est donc assez récente ...

C'est exact. Mais le film est sorti en 61, ce qui fait que ça ne date pas d'hier. Ce n'est pas la grèce antique, mais 45 ans c'est déjà pas mal. Je voulais simplement dire que ce n'était pas nouveau .

[Shiho]

Merci rhô têta point carré ^^ Trop bien les yeux qu'il fait quand il perd ^^

[vanos]

Ce jeu est assez vieux et s'appelle "le jeu de Marienbad".

Bonsoir,
Oui c'est assez ancien.
Cela s'est fait connaître en 1968 par le film d'Alain Renais "L'année dernière à Marienbad" avec Delphine Seyrig et Giorgio Albertazzi. Tout cinéphile sait cela, le jeu se jouait alors en 7-5-3-1 avec des allumettes et quand on connaît le truc il n'y a plus de jeu celui qui commence gagne toujours, c'est stupide.
Salut.