|
#1 - 25-04-2014 12:14:36
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Solitaire en lign
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 ?
#2 - 25-04-2014 18:22:04
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Solitaire en lige
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 een 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 : 5,426E+3
solitairz 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
Vasimolo
#5 - 25-04-2014 19:40:18
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
solitaire en lignz
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,426E+3
Solitaire en ilgne
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
#7 - 26-04-2014 13:26:06
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Solitaire en lign
Aurais-tu une démonstration Vasimolo ?
Allez, j'adopte ta notation.
#8 - 26-04-2014 15:24:27
- Nombrilist
- Expert de Prise2Tete
- Enigmes résolues : 10
- Messages : 568
Solitaire en lgne
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
solitaore 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,426E+3
Solitiare 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 lugne
@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,426E+3
Solitaire e nligne
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
Vasimolo
#13 - 26-04-2014 19:28:15
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Solitaire en lignee
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
Solitaire en lige
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
Solitaire en linge
@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,426E+3
Soltaire 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
Vasimolo
#17 - 28-04-2014 19:12:15
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Solitaire en lgine
Une illustration :
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
Solitaire en lign
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 : 3802
solitairz 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
Solitaaire 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
Soltiaire 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 : 1749
Solitaire enn 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,426E+3
dolitaire 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
Vasimolo
#24 - 01-05-2014 08:47:55
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Solitaire en ilgne
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,426E+3
Solitaire een 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
Mots clés des moteurs de recherche
|
|