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 : 1749

soliraire en ligne

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 ?

  • |
  • Répondre

#0 Pub

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

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

Sollitaire 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 : 1749

solitaire en lignz

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 : 5,382E+3

solitaore 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 : 1749

sokitaire 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 : 5,382E+3

solitaire en kigne

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 : 1749

solitaire en lihne

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 : 568

SSolitaire 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 : 1749

Solitiare en ligne

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 : 5,382E+3

qolitaire en 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 : 1749

solitaire en ligbe

@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 : 5,382E+3

Solitairre 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 : 3801

qolitaire 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 : 568

solitaite 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 : 1749

solitaiee 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 : 5,382E+3

Solitaire en line

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 : 5,382E+3

Soltaire en ligne

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 : 1749

Solitaier en ligne

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 : 3801

Soitaire en ligne

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 : 1749

Soltiaire 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 : 568

Solitair een 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 : 1749

Solitiare 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 : 5,382E+3

Solitaaire 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 : 3801

solitaire en migne

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 : 5,382E+3

Solitair en 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
19-04-2017 Enigmes Mathématiques
P2T
14-05-2011 Enigmes Mathématiques
P2T
Billard 7 par gabrielduflot
05-03-2010 Enigmes Mathématiques
P2T
Gâteau 76 par Vasimolo
20-04-2014 Enigmes Mathématiques
12-10-2014 Enigmes Mathématiques
P2T
Réarrangements par nodgim
30-06-2019 Enigmes Mathématiques
P2T
13-10-2010 Enigmes Mathématiques
21-07-2020 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