Enigme Un jeu avec des pièces de monnaie 1/2 @ Prise2Tete

titoufred · #1

Vous connaissez ce jeu ?

On place plusieurs pièces de monnaie sur une rangée de cases.
Un coup consiste à bouger une seule pièce vers la gauche, d'une ou plusieurs cases, pour l'amener sur une case libre.
On n'a pas le droit de sauter par-dessus une autre pièce.
Le premier joueur qui ne peut plus jouer a perdu.

Sur cet exemple, les seuls coups possibles sont d'amener la pièce 4 en 3, 2, 1 ou 0, la pièce 7 en 6 ou 5, ou la pièce 12 en 11 ou 10.

Alors, voilà, je gagne toutes mes parties en ne réfléchissant qu'une seconde ou deux à chaque coup. Mais comment fais-je ?

Sur cet exemple, quel est le coup gagnant ?

Grizix · #2

Le premier coup gagnant me parait simple, c'est d'amener la pièce en 4 en 0. Seulement, pour le deuxième coup, je ne vois pas.
Ma réflexion est simple, pour gagner, je dois amener la dernière pièce en 4. Comme il y a 5 pièces, je dois amener la première en 0, mon adversaire la deuxième en 1, moi la troisième en 2, lui la quatrième en 3 et voilà.
Seulement, je ne vois pas comment le forcer à amener cette pièce en 1.
Alors, est-ce que je suis dans le vrai et que je peux continuer à chercher par là ou est-ce qu'en jouant ce coup je laisse une ouverture qui causera ma perte ?

titoufred · #3

Ton coup est perdant.
Si tu joues ça, je joue 10 et je gagne.

clems86 · #4

Salut,

Sympa le jeu, je ne connaissais pas.
Dans cette situation on doit pouvoir s'en sortir en jouant le pion sur 4 en 2. Ensuite on garde les pions sur 7 et 8 collés, et deux cases d'écart entre ceux sur 9 et 12, si l'adversaire les resserre on déplace le premier pion sur la case 1 ou 0 selon si il les colle ou si il garde un case d'écart. A la fin on est gagnant si je ne me trompe pas.

titoufred · #5

Oui, clems, bravo, je pense que tu as trouvé la bonne stratégie sur cet exemple, même si ta formulation est un peu imprécise. Peux-tu la formuler simplement, de façon précise et concise ?

La stratégie gagnante est tellement simple à énoncer ici !

Pourrais-tu expliquer ton raisonnement ?

clems86 · #6

ça devrais être possible.
( j'appelle les pions de gauche à droite a,b,c,d,e )

Je commence par jouer a2;

Plusieurs possibilités s'offrent à l'adversaire dans les coups suivants:
-Si il joue a je déplace e d'autant de cases et réciproquement
-Si il joue b je joue c pour que ces pions restent collés
-Si il joue d je déplace e d'autant de cases
-Il ne pourras pas jouer c.

De cette manière je pourrais toujours jouer après lui mais il arrivera un moment où lui ne pourras plus jouer.
Et j'ai gagné!

titoufred · #7

Oui, c'est ça, bravo !

Et maintenant, sur cet exemple :

Quel est le coup gagnant ?

clems86 · #8

Je crois avoir compris le truc.

Sur l'exemple deux tu joue d'abord le pion situé en douze sur 8:
Après, (je reprend a,b,c,d,e):
-Si il joue a en 1 je joue e sur 7 et je me retrouve dans une situation analogue à la précédente
-Si il joue a en 0... Je suis mort on réessaye.

Bon je joue e en 9:
-Si il joue a en 1 je joue e en 7
-Si il joue a en 0 je joue e en 8 et cette fois je gagne
-Si il joue e je fais la réciproque
-Si il joue b je joue c d'autant
-Si il joue d je joue e d'autant

Et je gagne

Mais ton jeu ne serais pas légèrement avantageux pour celui qui commence?
Sauf si le jeu possède déjà une disposition perdante, mais je pense que ces situations sont moins fréquentes non?

titoufred · #9

Et s'il répond 4 ?

clems86 · #10

Pardon j'ai oublié ce cas là.

On reprend alors depuis le début mais on commence à jouer en 10.
Et là normalement on devrais pouvoir s'en sortir. en gardant les mêmes instructions. Et si il joue en 4 on joue e d'un rang et si il joue en 9 on joue en 4.

dhrm77 · #11

Pour le premier exemple le premier coup a jouer est 2,
Pour le 2eme exemple, jouer 10.

Vasimolo · #12

Je vais me faire taper sur les doigts mais bon

Que doit-on retenir de ces deux cas particuliers ? Il est clair que le jeu peut se généraliser à un nombre quelconque de cases et de pièces . Plutôt que détailler les solutions de ces deux cas , y-a-t-il un moyen simple de savoir si la position initiale est gagnante ou perdante ?

Vasimolo

dhrm77 · #13

Ma strategie:
- Ecrire un petit programme (ca m'a pris 2 heures en fesant des pauses)
- le faire tourner (ca prend 5ms)
Ensuite:
Chercher dans la liste des configurations perdantes laquelle il est possible de jouer a partir de ce qui m'est présenté quand mon tour de jouer vient... (grep est utile)
Voici la liste des 231 configurations perdantes (parmi 1287 possibles) pour celui qui va jouer:
31: 1111100000000
55: 1110110000000
61: 1011110000000
91: 1101101000000
94: 0111101000000
103: 1110011000000
109: 1011011000000
171: 1101010100000
118: 0110111000000
174: 0111010100000
121: 1001111000000
181: 1010110100000
186: 0101110100000
199: 1110001100000
205: 1011001100000
307: 1100110010000
214: 0110101100000
217: 1001101100000
316: 0011110010000
331: 1101001010000
334: 0111001010000
341: 1010101010000
234: 0101011100000
346: 0101101010000
241: 1000111100000
361: 1001011010000
370: 0100111010000
391: 1110000110000
397: 1011000110000
595: 1100101001000
406: 0110100110000
409: 1001100110000
604: 0011101001000
613: 1010011001000
426: 0101010110000
433: 1000110110000
628: 0010111001000
651: 1101000101000
654: 0111000101000
661: 1010100101000
666: 0101100101000
681: 1001010101000
460: 0011001110000
466: 0100101110000
690: 0100110101000
481: 1000011110000
721: 1000101101000
738: 0100011101000
1123: 1100011000100
1126: 0110011000100
1132: 0011011000100
1144: 0001111000100
775: 1110000011000
781: 1011000011000
1171: 1100100100100
790: 0110100011000
793: 1001100011000
1180: 0011100100100
1189: 1010010100100
810: 0101010011000
817: 1000110011000
1204: 0010110100100
1222: 0110001100100
1225: 1001001100100
844: 0011001011000
850: 0100101011000
1240: 0001101100100
865: 1000011011000
1252: 0010011100100
1291: 1101000010100
1294: 0111000010100
1301: 1010100010100
1306: 0101100010100
1321: 1001010010100
1330: 0100110010100
1361: 1000101010100
916: 0010100111000
930: 0100010111000
1378: 0100011010100
1420: 0011000110100
1432: 0001100110100
961: 1000001111000
1441: 1000010110100
1474: 0100001110100
2211: 1100010100010
2214: 0110010100010
2220: 0011010100010
2232: 0001110100010
2245: 1010001100010
2250: 0101001100010
2260: 0010101100010
2280: 0001011100010
1543: 1110000001100
1549: 1011000001100
2323: 1100100010010
1558: 0110100001100
1561: 1001100001100
2332: 0011100010010
2341: 1010010010010
1578: 0101010001100
1585: 1000110001100
2356: 0010110010010
2374: 0110001010010
2377: 1001001010010
1612: 0011001001100
1618: 0100101001100
2392: 0001101010010
1633: 1000011001100
2404: 0010011010010
2442: 0101000110010
2449: 1000100110010
1684: 0010100101100
1698: 0100010101100
2472: 0001010110010
1729: 1000001101100
2500: 0010001110010
2571: 1101000001010
2574: 0111000001010
2581: 1010100001010
2586: 0101100001010
2601: 1001010001010
2610: 0100110001010
2641: 1000101001010
2658: 0100011001010
2700: 0011000101010
1816: 0001100011100
2712: 0001100101010
2721: 1000010101010
1828: 0010010011100
1858: 0100001011100
2754: 0100001101010
2836: 0010100011010
2856: 0001010011010
1921: 1000000111100
2881: 1000001011010
2946: 0100000111010
4291: 1100001100001
4336: 0000111100001
4387: 1100010010001
4390: 0110010010001
4396: 0011010010001
4408: 0001110010001
4421: 1010001010001
4426: 0101001010001
4436: 0010101010001
4456: 0001011010001
4489: 1001000110001
4498: 0100100110001
4516: 0010010110001
4552: 0001001110001
3079: 1110000000110
3085: 1011000000110
4627: 1100100001001
3094: 0110100000110
3097: 1001100000110
4636: 0011100001001
4645: 1010010001001
3114: 0101010000110
3121: 1000110000110
4660: 0010110001001
4678: 0110001001001
4681: 1001001001001
3148: 0011001000110
3154: 0100101000110
4696: 0001101001001
3169: 1000011000110
4708: 0010011001001
4746: 0101000101001
4753: 1000100101001
3220: 0010100100110
3234: 0100010100110
4776: 0001010101001
3265: 1000001100110
4804: 0010001101001
4882: 0100100011001
3352: 0001100010110
4897: 1000010011001
3364: 0010010010110
3394: 0100001010110
4936: 0001001011001
3457: 1000000110110
4996: 0010000111001
5131: 1101000000101
5134: 0111000000101
5141: 1010100000101
5146: 0101100000101
5161: 1001010000101
5170: 0100110000101
5201: 1000101000101
5218: 0100011000101
5260: 0011000100101
5272: 0001100100101
5281: 1000010100101
5314: 0100001100101
5396: 0010100010101
3624: 0001010001110
5416: 0001010010101
5441: 1000001010101
3652: 0010001001110
3714: 0100000101110
5506: 0100000110101
5668: 0010010001101
5704: 0001001001101
3841: 1000000011110
5761: 1000000101101
5890: 0100000011101
6151: 1110000000011
6157: 1011000000011
6166: 0110100000011
6169: 1001100000011
6186: 0101010000011
6193: 1000110000011
6220: 0011001000011
6226: 0100101000011
6241: 1000011000011
6292: 0010100100011
6306: 0100010100011
6337: 1000001100011
6424: 0001100010011
6436: 0010010010011
6466: 0100001010011
6529: 1000000110011
6696: 0001010001011
6724: 0010001001011
6786: 0100000101011
6913: 1000000011011
7216: 0000110000111
7240: 0001001000111
7300: 0010000100111
7426: 0100000010111
7681: 1000000001111
Si ces configurations ont un point commun, je ne l'ai pas trouvé.

titoufred · #14

Effectivement, les coups à jouer sont 2 pour le premier exemple et 10 pour le 2ème.

clems86 a détaillé la stratégie gagnante sur le premier exemple, même si cela aurait pu être résumé de façon plus concise. Il faudrait essayer de caractériser simplement les configurations gagnantes pour celui qui vient de jouer.

Pour le 2ème exemple, il reste à finaliser la stratégie gagnante donnée par clems86.

Après, on peut comparer ce qu'il y a en commun entre ces 2 exemples...
Cela devrait aider à deviner la stratégie universelle, valable pour n'importe quelle configuration, quel que soit le nombre de pièces.

dhrm77 · #15

Pour 2 pieces les configurations perdantes sont au nombre de 12 (parmi 78, soit 15.38%):
3: 1100000000000
6: 0110000000000
12: 0011000000000
24: 0001100000000
48: 0000110000000
96: 0000011000000
192: 0000001100000
384: 0000000110000
768: 0000000011000
1536: 0000000001100
3072: 0000000000110
6144: 0000000000011
Pour 2 pieces, il suffit de garder les 2 pieces cote a cote..

Pour 3 pieces, 36 parmi 286, soit 12.5%:
7: 1110000000000
13: 1011000000000
22: 0110100000000
25: 1001100000000
42: 0101010000000
49: 1000110000000
76: 0011001000000
82: 0100101000000
97: 1000011000000
148: 0010100100000
162: 0100010100000
280: 0001100010000
193: 1000001100000
292: 0010010010000
322: 0100001010000
552: 0001010001000
385: 1000000110000
580: 0010001001000
642: 0100000101000
1072: 0000110000100
1096: 0001001000100
769: 1000000011000
1156: 0010000100100
1282: 0100000010100
2128: 0000101000010
2184: 0001000100010
1537: 1000000001100
2308: 0010000010010
2562: 0100000001010
4192: 0000011000001
4240: 0000100100001
4360: 0001000010001
3073: 1000000000110
4612: 0010000001001
5122: 0100000000101
6145: 1000000000011
Pour 3 pieces, je ne vois pas de modele.

Pour 4 pieces, 125 parmi 715, soit 17.4%:
15: 1111000000000
27: 1101100000000
30: 0111100000000
45: 1011010000000
51: 1100110000000
54: 0110110000000
85: 1010101000000
60: 0011110000000
90: 0101101000000
99: 1100011000000
102: 0110011000000
153: 1001100100000
108: 0011011000000
165: 1010010100000
170: 0101010100000
120: 0001111000000
180: 0010110100000
195: 1100001100000
198: 0110001100000
297: 1001010010000
204: 0011001100000
306: 0100110010000
216: 0001101100000
325: 1010001010000
330: 0101001010000
340: 0010101010000
240: 0000111100000
360: 0001011010000
561: 1000110001000
387: 1100000110000
390: 0110000110000
585: 1001001001000
396: 0011000110000
594: 0100101001000
408: 0001100110000
612: 0010011001000
432: 0000110110000
645: 1010000101000
650: 0101000101000
660: 0010100101000
680: 0001010101000
480: 0000011110000
720: 0000101101000
1105: 1000101000100
1122: 0100011000100
771: 1100000011000
774: 0110000011000
1161: 1001000100100
780: 0011000011000
1170: 0100100100100
792: 0001100011000
1188: 0010010100100
816: 0000110011000
1224: 0001001100100
864: 0000011011000
1285: 1010000010100
1290: 0101000010100
1300: 0010100010100
1320: 0001010010100
1360: 0000101010100
960: 0000001111000
1440: 0000010110100
2145: 1000011000010
2193: 1000100100010
2210: 0100010100010
2244: 0010001100010
1539: 1100000001100
1542: 0110000001100
2313: 1001000010010
1548: 0011000001100
2322: 0100100010010
1560: 0001100001100
2340: 0010010010010
1584: 0000110001100
2376: 0001001010010
1632: 0000011001100
2448: 0000100110010
1728: 0000001101100
2565: 1010000001010
2570: 0101000001010
2580: 0010100001010
2600: 0001010001010
2640: 0000101001010
2720: 0000010101010
1920: 0000000111100
2880: 0000001011010
4257: 1000010100001
4290: 0100001100001
4369: 1000100010001
4386: 0100010010001
4420: 0010001010001
4488: 0001000110001
3075: 1100000000110
3078: 0110000000110
4617: 1001000001001
3084: 0011000000110
4626: 0100100001001
3096: 0001100000110
4644: 0010010001001
3120: 0000110000110
4680: 0001001001001
3168: 0000011000110
4752: 0000100101001
3264: 0000001100110
4896: 0000010011001
3456: 0000000110110
5125: 1010000000101
5130: 0101000000101
5140: 0010100000101
5160: 0001010000101
5200: 0000101000101
5280: 0000010100101
5440: 0000001010101
3840: 0000000011110
5760: 0000000101101
6147: 1100000000011
6150: 0110000000011
6156: 0011000000011
6168: 0001100000011
6192: 0000110000011
6240: 0000011000011
6336: 0000001100011
6528: 0000000110011
6912: 0000000011011
7680: 0000000001111
Pour 4 pieces, il semblerait qu'il faille faire une configuration de pieces symmetrique.
ou encore 2 paires de pieces [11], placées n'importe ou, ou 2 paires de [101] ou 2 paires de [1001], etc...

Pour 6 pieces, il faut former 3 couples de [11] ou un nombre pair de [101] et un couple de [11]. Il y a 384 combinaisons perdantes parmi 1716 possibles, soit 22.37%

Pour 7 pieces, 400 combinaisons perdantes parmi 1716 possibles, soit 23.31%.

Mais pour un nombre impair de pieces (3, 5 ou 7), je ne vois toujours pas de strategie faisable de tete.

nodgim · #16

La parité du nombre total de déplacements des pions semble avoir une influence sur le résultat. En effet, si pair au départ, il est facile pour l'adversaire de conserver la parité. Cependant, il y a tout de même des pairs gagnants, comme par exemple 2 pions séparés.

Dans la liste de dhrm77, je n'ai vu, par sondage, que des config avec un nombre pair de déplacements.

Vasimolo · #17

Il y a une façon de prendre le problème qui le rend presque arithmétique . On peut représenter la situation par le nombre de cases qu'il reste à parcourir à chacune des pièces en partant de la gauche .

Exemple 1 : 46668
Exemple 2 : 22338

Là on est en base 9 mais en choisissant une écriture en base "nombre de case - nombres de pièces +1" on peut représenter toutes les situations possibles . Les chiffres des nombres représentant la situation sont nécessairement en ordre croissant et un mouvement de pièce consiste à réduire la valeur d'un chiffre tout en respectant cet ordre . Je ne sais pas si cet angle d'attaque peut déboucher sur quelque chose d'intéressant !

Vasimolo

nodgim · #18

ça m'a l'air une remarque très intéressante en effet.

Vasimolo · #19

En fait ce jeu est connu sous le nom de "Silver dollar game" ou "Bogus Nim" , c'est une variante du jeu de Nim .

J'ai trouvé plusieurs liens dans la langue de Shakespeare mais je n'ai pas trop compris comment la position était codée .

Vasimolo

nodgim · #20

Pour faire avancer un peu:
avec 3 pièces à faire bouger (toutes au moins de 1 case) si a et b sont les nombres de déplacements des 2 pions les plus proches du but, alors les configurations perdantes suivent cette règle simple:
(a, b, a+b).

Vasimolo · #21

Je ne suis pas sûr que tu aboutisses ainsi , le codage de la position est à la "Nim" c'est à dire en binaire avec renvoie systématique d'une position "paire" à l'adversaire .

Vasimolo

nodgim · #22

J'ai regardé un peu les combis de la liste, ça confirme. L'astuce est, tant qu'on reste sur 3 pièces, de renvoyer à l'adversaire cette config (a, b, a+b). ça marche.
Si l'adversaire passe à 2 pièces, il perd aussi.

nodgim · #23

Pour 4 pièces dont la distance en nombre de cases du but est a, b, c ,d:
Si b+c-a-d=0 alors cette combi est perdante, il faut l'offrir à l'adversaire pour gagner.

Clydevil · #24

Hello,
Comme il a été évoqué il s'agit d'une variante du jeu de nim.

Jeu de nim:
Il y a N tas de pierres, les tas étant constitués de Ki pierres (pas forcément le même nombre de pierres dans chaque tas).
A son tour, on peut prendre autant de pierres qu'on veut du même tas.
Celui qui ne peut plus jouer perd.

Solution du jeu de nim:
Spoiler : [Afficher le message]

Rapport avec ici:
Spoiler : [Afficher le message] On peut se ramener à un jeu de Nim.
Spoiler : [Afficher le message]

Vasimolo · #25

C'est bien ce que j'avais compris mais une subtilité du codage m'avait échappé

Déjà le jeu de Nim , c'est plutôt malin mais codé un intervalle sur deux en partant de la droite , et en rectifiant les tas qui grossissent , c'est diabolique !!!

Je suis fan de ces problèmes très simples en apparence dont la solution est aussi très simple si on y pense ( là c'est une autre paire de manches ) .

Merci à Titoufred pour ce très joli jeu

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 11-01-2012 23:54:39

Un eu avec des pièces de monnaie

#0 Pub

#2 - 12-01-2012 01:30:09

Un jeu avec des pièes de monnaie

#3 - 12-01-2012 12:00:37

Un jeu avec eds pièces de monnaie

#4 - 12-01-2012 14:28:17

Un jeu avec des piècse de monnaie

#5 - 12-01-2012 16:24:44

un jeu avec des pièces de monnaiz

#6 - 12-01-2012 18:19:22

ub jeu avec des pièces de monnaie

#7 - 13-01-2012 00:59:02

un jeu avec drs pièces de monnaie

#8 - 13-01-2012 20:49:50

Un jeu avec des pièces de mnnaie

#9 - 14-01-2012 01:14:24

Un jeu avec des piècse de monnaie

#10 - 14-01-2012 11:13:32

Un jeu avec des pièces dee monnaie

#11 - 14-01-2012 18:52:07

Un jeu avec des pièces de monaie

#12 - 15-01-2012 00:21:19

Un jeu avec des pièces d emonnaie

#13 - 15-01-2012 01:07:35

un jeu acec des pièces de monnaie

#14 - 15-01-2012 01:20:33

un jeu avec des pièczs de monnaie

#15 - 15-01-2012 03:20:31

Un jeu avc des pièces de monnaie

#16 - 15-01-2012 09:16:34

Un jeu avec des pièces de monnnaie

#17 - 15-01-2012 11:41:51

Un jeu avec de pièces de monnaie

#18 - 15-01-2012 14:06:36

Un jeu avec des pièces de monaie

#19 - 15-01-2012 18:34:33

un jeu avec des pièces dr monnaie

#20 - 15-01-2012 18:51:30

un jeu avec fes pièces de monnaie

#21 - 15-01-2012 19:39:45

Un jeu avec des pièce de monnaie

#22 - 15-01-2012 19:53:41

Unn jeu avec des pièces de monnaie

#23 - 16-01-2012 18:30:56

Un jeu avec des pèices de monnaie

#24 - 16-01-2012 19:38:47

un jeu avec drs pièces de monnaie

#25 - 16-01-2012 22:25:39

Un jeu avce des pièces de monnaie

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums