Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 25-04-2014 12:14:36

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

solitaire en lignr

Vous connaissez tous le jeu du solitaire, où le but du jeu est de ne laisser qu'une seule bille à la fin. Je vous en propose une version où toutes les billes sont alignées.

Parmi les 10 configurations suivantes, lesquelles permettent de ne laisser qu'une seule bille à la fin en jouant bien (configurations gagnantes) et lesquelles ne le permettent pas, quelle que soit la stratégie employée (configurations perdantes) ?

Une bille est représentée par un O et un emplacement vide entre deux billes par un X. Il y a autant d'emplacements vides que voulus à gauche et à droite des billes extrémales.

1) OOOOOOXXXOOOOOO

2) OOOOOOOOOOOXXO

3) OOOOOOOOOOOO

4) OXOOOOOOOOOOXO

5) OOOOOOOOOOXXOO

6) OOOOXXOOOOXXOOOO

7) OOOXOOOXOOOXOOO

8) OOOOOOXOOOOXOO

9) OOOOXOOXOOOOOO

10) OOOOXOOOOOOXOO

Pour les configurations perdantes, il faudrait trouver un argument démontrant que c'est impossible de ne laisser qu'une seule bille à la fin, quelle que soit la stratégie employée.

De façon générale, sauriez-vous trouver un critère simple permettant de savoir très rapidement si une configuration est gagnante ou perdante ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 25-04-2014 18:22:04

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2955

Soliitaire en ligne

Je voudrais bien comprendre de problème, mais je ne sais pas quelles règles il faut appliquer pour ôter les billes...
Peux tu préciser ?

 #3 - 25-04-2014 19:14:47

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Soliaire en ligne

Ce sont les règles classiques du solitaire : une bille saute par dessus une autre pour l'éliminer du jeu.

Par exemple, de OOXO, on peut passer à XXOO (la bille à gauche passe par-dessus sa voisine, que l'on retire du jeu), puis à XOXX et on a gagné.

On notera plus simplement OOXO => OO => O

 #4 - 25-04-2014 19:18:49

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Soliaire en ligne

J'avais lu les règles du jeu un peu vite , il n'aurait pas été plus judicieux de noter les billes "O" et les vides "X" ?

J'ai déjà plein de critères gagnant perdant mais rien de simple smile

Vasimolo

 #5 - 25-04-2014 19:40:18

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

solitaore en ligne

Oui, Vasimolo, je me suis dit ça pour les notations après avoir posté.

Donne donc tes conditions nécessaires et tes conditions suffisantes, pour voir sur quoi tu es parti.

 #6 - 26-04-2014 11:42:06

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

solitaore en ligne

Disons que c'est un peu le bazar , il faudra que j'y réfléchisse un peu plus . L'idée principale : il ne faut pas de trous de plus de 2 cases sinon on obtient des jeux indépendants perdants .

La position gagnante type est 1=OOXO...XOXOX ou 1'=XOXO...XOXOO le pion finissant sa course sur le dernier X .

Les positions OXP ou OOOOXI sont gagnantes si P et I sont des nombres pairs et impairs de pions conjoints . Après les choses se compliquent car on peut très bien remplacer O à gauche par 1 , I par P+1' ou P par I+1' , ...

Vasimolo

PS : désolé , mes O sont des X et réciproquement sad

 #7 - 26-04-2014 13:26:06

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

olitaire en ligne

Aurais-tu une démonstration Vasimolo ?

Allez, j'adopte ta notation. big_smile

 #8 - 26-04-2014 15:24:27

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

somitaire en ligne

Déjà, si deux groupes de pions sont éloignés de 3 cases ou plus, ils ne peuvent pas se rejoindre. Par ailleurs, si l'un des deux groupes ne contient qu'un seul pion, si ils sont éloignés par 2 cases ou plus, ils ne peuvent pas se rejoindre.

 #9 - 26-04-2014 15:34:09

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Solitaire en lignne

Oui, Nombrilist, cela donne des conditions nécessaires pour les configurations gagnantes. Du coup, lesquelles des configurations 1 à 10 sont perdantes à coup sûr ? Et pour les autres, que peux-tu dire ?

 #10 - 26-04-2014 18:25:40

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Solitaire een ligne

Je n'ai pas vraiment de démonstration et avant de suivre plus loin dans cette voie , il semblerait que seules les positions 5 et 10 soit gagnantes , vrai ?

Vasimolo

 #11 - 26-04-2014 18:47:45

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Solitaire een ligne

@nodgim : par configs possibles, tu entends gagnantes ? Peux-tu présenter tes solutions pour les configs annoncées gagnantes ?

@Vasimolo : Il faudrait une démonstration pour être sûr...

 #12 - 26-04-2014 19:18:19

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

olitaire en ligne

Je n'ai aucune démonstration , ce ne sont que des spéculations après quelques essais à la main .

Il n'y aurait que 3 positions gagnantes :

A=OOXOXOX...OX
B=OXP
C=OOOOXI=4XI

et leurs symétriques A' , B' et C' .

Avec l'enchaînement C->B->A->O ( O<-A'<-B'<-C' ) .

donc si R désigne le reste de la suite AR->OR , BR->OXR et CR->OXR ( même chose pour les ' que je ne détaille plus ) . Après on réduit en partant des 2 extrémités de la chaîne en respectant les priorités A puis B puis C , si on aboutit à "O" on a gagné .

La méthode est sûrement facile à programmer mais permet-elle de détecter toutes les positions gagnantes ? Rien n'est moins sûr smile

Vasimolo

 #13 - 26-04-2014 19:28:15

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2955

Solittaire en ligne

Ce que j'ai présenté est insuffisant.
Je revois ça.

 #14 - 27-04-2014 22:41:34

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

solutaire en ligne

Les 1, 2 et 7 sont perdantes à coup sur. La 3 est injouable.

 #15 - 28-04-2014 00:14:26

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

soliyaire en ligne

@Nombrilist : Ok pour la 1 et la 2.

Pour la 3, tu as des espaces de part et d'autre des billes, en fait c'est

3) XXXXOOOOOOOOOOOOXXXX

Pour la 7 peux-tu préciser ?

@Vasimolo : Penses-tu qu'il est possible de gagner en enchainant plusieurs configurations B ou C ?

 #16 - 28-04-2014 11:43:32

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

oSlitaire en ligne

Non , on ne peut pas vraiment enchaîner les configurations car il faut bien suivre à chaque réduction où atterrit le pion "rescapé" . J'essaierai de joindre un dessin dans la journée mais je répète que je ne suis pas du tout convaincu d'avoir toutes les solutions smile

Vasimolo

 #17 - 28-04-2014 19:12:15

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Solitaire e nligne

Une illustration :

http://img838.imageshack.us/img838/380/q1kp.jpg

On voit par exemple qu'on peut remplacer le pion gauche de B ou de C par "A=OOXOXOXOX" ou le pion droit par "A'=XOXOXOXOXOO" , il y a pas mal de variantes je n'ai pas réussi à synthétiser tout ça . Ca a l'air un peu compliqué mais je n'ai pas de contre-exemple à la réduction que j'ai donnée .

Vasimolo

 #18 - 28-04-2014 21:05:21

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Solitaire en linge

Du coup, comment reconnaitre assez rapidement une configuration gagnante ?

Et pour dissiper les derniers doutes, je pense qu'une petite démonstration s'impose non ?

 #19 - 29-04-2014 18:10:44

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2955

solitaire en ligbe

La 1ère partie de la question semble peu accessible si au préalable on n'établit pas d'abord les configurations possibles à partir du pion unique, c'est à dire de réaliser l'opération inverse de suppression des pions.

Le mécanisme inverse revient à cette simple opération élémentaire:
100 ----->011.
Un pion en créé 2 voisins tandis que lui disparait.

Créons 4 pions en exemple à partir d'un 1er:
1
011
01011
110011
111101

On est assez vité amené à se rendre compte qu'on peut créer des pions en 4 endroits seulement que l'on nommera 1,2,3,4.
Le 1 à gauche du segment, le 4 à droite du segment.
1: 0011---->1101
4: 1100---->1011
et lorsqu'il existe un espace de 2 vides à l'intérieur d'un segment:
2: 110011---->101111
3: 110011---->111101

On peut avec ces notations recréer un segment simplement par la suite des nombres 1 à 4 écrits dans l'ordre.
Par exemple 11142:
11
1101
110101
11010011
11001111

On ne peut bien sûr pas écrire une suite dans n'importe quel ordre, il y a des contraintes:
-Avant d'écrire un 2 ou un 3, il est obligatoire d'avoir au moins 3 nombres 1 ou 4 , dont au moins 1 de chaque.
-On ne peut écrire une suite de 2 ou 3 supérieure respectivement aux 1 ou 4 moins une unité.
-Quand on a écrit un ou plusieurs 2, on ne peut écrire qu'un seul 3, et vice versa.

Compte tenu de ces contraintes les configurations possibles sont assez limitées, elles sont listées ci après:
Po1               
Ioo2           
Io4               
2oPoo2   
2ooIo2   
1oIo2       
4oPo2       
2o3oIo2

P est une suite ininterrompue paire de pion, I une suite impaire, o est un vide, et un chiffre représente le nombre de pions consécutifs.
A cela, un chiffre 2 d'extrémité peut être allongé par une suite alternée de 1
2.....------>2o1o1o1o..... ou ......2----->.....o1o1o1o12.

Toutes les configurations qui n'entrent pas dans cette liste ne sont pas issues d'un pion unique, on ne peut aboutir à un résultat gagnant.

 #20 - 29-04-2014 23:30:58

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

SSolitaire en ligne

@nodgim : Bonne idée au départ, mais la liste des configurations gagnantes que tu donnes n'est pas la bonne. Par ailleurs, il serait intéressant d'apporter des preuves à ce que tu avances.

 #21 - 30-04-2014 08:08:24

Nombrilist
Expert de Prise2Tete
Enigmes résolues : 10
Messages : 562

Solittaire en ligne

Pour la 7, dès que l'on a joué un coup, il se trouve forcément un pion isolé par deux cases d'un autre groupe de pions. Donc, on ne peut pas gagner.

 #22 - 30-04-2014 15:19:03

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Solitair en ligne

@Nombrilist : Oui mais ce n'est pas forcément un pion isolé extérieur comme dans la 2. Il peut encore "recevoir du renfort" de l'autre côté par un 3ème groupe.
Par exemple sur OOXXOXOO, on arrive à gagner.

 #23 - 30-04-2014 18:44:08

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

sokitaire en ligne

@Nodgim : il est clair qu'il y a plein de configurations gagnantes par répétitions des formules à gauche et à droite symétriquement . On doit pouvoir réduire tout ça à quelques formules élémentaires éventuellement répétées mais tout ça ne nous dit pas comment reconnaître facilement une position gagnante .

Je trouve Titou un peu en retrait sur ce coup smile

Vasimolo

 #24 - 01-05-2014 08:47:55

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2955

solitzire en ligne

Oui en fait il y a bien des configs fausses, Titoufred a raison.

On peut se contenter de 2 configs types, qu'on doit pouvoir retrouver facilement  depuis n'importe quelle config présentée: Po1 et Io4.

Pour les exemples de l'énoncé:

1) OOOOOOXXXOOOOOO
6ooo6 : il est impossible de créer un espace de 3 vides consécutifs.


2) OOOOOOOOOOOXXO
Ioo2: l'intervalle a une longueur impaire, c'est impossible.

3) OOOOOOOOOOOO
Pas d'intervalle, c'est impossible

4) OXOOOOOOOOOOXO
1oPo1: impossible d'obtenir Po1, et ne vient pas de Po1. Ou encore il est impossible d'être encadré par 2 jetons isolés.

5) OOOOOOOOOOXXOO
Poo2 vient de Po1 donc OK

6) OOOOXXOOOOXXOOOO
il y a 2 intervalles de 2 vides, impossible, 1 seul max.

7) OOOXOOOXOOOXOOO
3o3o3o3: longueur impaire, impossible.

8) OOOOOOXOOOOXOO
Po4o2 vient de Po5, on ne peut avoir 2 intervalles de jetons >4.

9) OOOOXOOXOOOOOO
4o2oP vient de 5oooP, intervalle 3 vides donc impossible.

10) OOOOXOOOOOOXOO
4oPo2 vient de 4oI donc OK.

Les façons d'éliminer les configs non conformes sont donc assez diverses....

 #25 - 01-05-2014 11:00:09

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Solitaire ne ligne

Je crois que j'ai réussi à lister toutes les configurations gagnantes ( à vérifier ) :

[latex]A ,AA' ,AXIA' ,  AOOOXPA' , APXOOOO , AXP , AOOOXI , OXP[/latex] et [latex]OOOOXI[/latex] ainsi que leur "inverses" ce qui donne 17 configurations possibles .

Je note toujours :

[latex]A=OOXOXOX...OX[/latex] , [latex]A'=XO...XOXOXOO[/latex] , [latex]P[/latex] et  [latex]I[/latex] une succession paire ou impaire de pions .

Vasimolo

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
15-10-2009 Enigmes Mathématiques
P2T
La fontaine Romaine par Sergent-Bonbon
21-03-2014 Enigmes Mathématiques
P2T
Puissant cryptarithme par franck9525
21-01-2011 Enigmes Mathématiques
P2T
Pas de jaloux ! par LeSingeMalicieux
17-11-2008 Enigmes Mathématiques
22-04-2015 Enigmes Mathématiques
P2T
Center Parc par SaintPierre
10-03-2011 Enigmes Mathématiques
P2T
03-01-2010 Enigmes Mathématiques
P2T
Alido et blido par yoyo25
28-09-2010 Enigmes Mathématiques
05-08-2009 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete