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
[+]

 #26 - 04-10-2012 16:54:29

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

Ehecs 2

Cela veut dire que l'on est dans les deux cas suivants :

-le joueur qui commence à jouer va gagner à tous les coups s'il joue bien.
-le deuxième à jouer va gagner à tous les coups s'il joue bien.

#0 Pub

 #27 - 04-10-2012 17:00:33

racine
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1224

Echec s2

Mon interrogation est plus générale. La phrase sous-entend que si un jeu n'admet pas de nullité alors il y a une stratégie gagnante pour l'un des deux joueurs. Ce n'est pas du tout trivial pour moi.

 #28 - 04-10-2012 17:59:01

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3762
Lieu: hébesphénorotonde triangulaire

Echecs

Pour appuyer Racine :
Par exemple si on joue à pile ou face :
Sur un seul coup, il n'y a pas de nullité, et pourtant aucun des deux joueurs n'a de stratégie gagnante, ni le premier qui choisit "pile" ou "face, ni le deuxième qui subit le choix du premier.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #29 - 04-10-2012 18:52:53

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

ecgecs 2

Il s'agît ici d'un jeu très particulier ou rien n'est caché et chacun joue à tour de rôle avec un nombre total de possibilités fini . Donc pas de hasard comme avec une pièce , un dé ou un tirage au sort ni de coups simultanés comme à pair-impair ou feuille-ciseaux-puits .

Les jeux d'échecs de dames , de go sont du même type avec la différence que le nul est possible .

Une fois qu'on a déterminé la nature du jeu , gain pour A , gain pour B ou nul et si chacun joue au mieux le résultat sera toujours le même .

Une façon simple de voir les choses . Supposons qu'il n'y a pas de partie nulle et on écrit toutes les parties possibles que l'on range en deux tas , celles qui font gagner A et celles qui font gagner B . Ensuite A pioche une partie dans son tas et joue le premier coup de cette partie . B prend une partie de son son tas commençant par le premier coup de A , et ainsi de suite . Le premier qui ne peut plus choisir de partie au rang n enlève de son tas toutes les parties commençant par les n-2 premiers coups joués . On recommence aussi longtemps qu'il le faut et à un moment donné l'un des joueurs n'aura plus rien à retirer . L'autre joueur gagnera en jouant une partie quelconque de son tas .

Vasimolo

 #30 - 04-10-2012 19:51:24

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

Ehcecs 2

Ici le hasard n'intervient pas dans le jeu. On suppose que l'on étudie un jeu qui se finit forcément et sans match nul possible.

Imaginons un graphe orienté où chaque point représente une position (une situation) du jeu, et où les flèches du graphe représentent les coups possibles. La racine du graphe représente le jeu avant le premier coup. Le graphe est ordonné par le nombre de coups joués depuis le début de la partie, il ne contient pas de circuit. Les feuilles du graphe (sommets de niveau inverse 0) représentent les situations où l'on ne peut plus jouer, donc des positions finales du jeu. Ce peut être soit une victoire pour celui qui vient de jouer (position perdante pour celui à qui c'est le tour de jouer, et dont on peut marquer le sommet correspondant d'un P), soit une défaite (position gagnante pour celui à qui c'est le tour de jouer, sommet marqué d'un G). Puis l'on remonte d'un niveau et l'on s'intéresse aux sommets du graphe dont tous les successeurs sont des feuilles (sommets de niveau inverse 1) : Si un sommet mène à un sommet P, alors c'est un sommet G. Sinon (s'il ne mène qu'à des sommets G), c'est un sommet P. Puis l'on remonte encore d'un niveau (sommets de niveau inverse 2 : leurs successeurs sont de niveau inverses 1 ou 0). On peut ainsi étiqueter tous les sommets du graphe en remontant les niveaux. Ainsi la racine du graphe peut s'étiqueter P ou G.

Si la racine est G, le premier joueur possède une stratégie gagnante.
En effet, il peut envoyer son adversaire sur un P. Celui-ci sera obligé de le renvoyer sur un G. Donc lui pourra le renvoyer sur un P, etc...

Si la racine est P, c'est le deuxième joueur qui possède une stratégie gagnante.

Ce raisonnement se généralise aux jeux avec match nul, où l'un des deux joueurs possède forcément une stratégie non-perdante (comme les échecs). Une personne (ou ordinateur qui aurait assez de mémoire) qui a l'arbre sous les yeux peut à coup sûr jouer de façon optimale.

 #31 - 05-10-2012 16:22:19

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

Echec s2

Au fait Vasimolo, y a-t-il une autre grille que celle que j'ai trouvée pour que le premier joueur n'ait qu'une seule première case qui lui assure la victoire ?

 #32 - 05-10-2012 17:52:32

racine
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1224

echecq 2

Ok, merci pour les explications.

 #33 - 05-10-2012 18:25:30

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

Eches 2

titoufred a écrit:

Y a-t-il une autre grille que celle que j'ai trouvée pour que le premier joueur n'ait qu'une seule première case qui lui assure la victoire ?

Je n'ai pas d'autre exemple ni de preuve qu'il n'en existe pas d'autre , avis aux amateurs smile

Vasimolo

 #34 - 05-10-2012 18:35:18

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

echecq 2

C'était bien retors comme énoncé...
Petit coquin va ! big_smile

 #35 - 09-10-2012 22:24:50

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

zchecs 2

titoufred a écrit:

Au fait Vasimolo, y a-t-il une autre grille que celle que j'ai trouvée pour que le premier joueur n'ait qu'une seule première case qui lui assure la victoire ?

A la réflexion , la question était un peu ridicule . Un parcours gagnant pour le joueur 1 se fini par une case gagnante pour le joueur 1 ( le chemin est parfaitement inversible ) et comme la case de départ ne peut pas être celle d'arrivée ...

Vasimolo

 #36 - 09-10-2012 23:14:49

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

 #37 - 09-10-2012 23:22:35

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

evhecs 2

Je ne vois pas bien pourquoi.

Sur cette grille : XXXXX
En partant de la case du milieu, on obtient le chemin XX123 par exemple mais le chemin ne s'inverse pas vraiment.

 #38 - 09-10-2012 23:27:57

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

Echcs 2

Si , il y a une parfaite symétrie , si joueur A gagne partant de X vers Y il gagnera aussi partant de Y vers X .

Vasimolo

 #39 - 10-10-2012 05:46:06

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

Echesc 2

Mais je te crois. Je ne vois juste pas pourquoi. Pourrais-tu expliquer ?

 #40 - 10-10-2012 19:03:24

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

Ehcecs 2

C'est facile à voir mais un peu compliqué à expliquer smile

Les cases du domaine peuvent être rangées en deux catégories , celles qui sont gagnantes pour 1 et celles qui sont gagnantes pour 2 . Sur un échiquier chacune des catégories a sa couleur propre . Un parcours de plus d'une case possède des cases de deux couleurs , il reste à conclure .

Vasimolo

 #41 - 10-10-2012 21:41:47

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

Eches 2

J'ai passé pas mal de temps dessus. Je ne comprends toujours pas pourquoi.

 #42 - 10-10-2012 22:47:07

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

Echecs 22

Je comprends tes doutes , j'essaierai de trouver un moment pour m'expliquer plus en détail smile

Vasimolo

 #43 - 11-10-2012 18:00:28

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

Ecchecs 2

Bon en fait ça ne marche pas sad

Si on accepte un terrain de jeu non connexe , tout jeu dont les composantes connexes sont une case et des parties pavables avec des dominos offre un unique coup gagnant pour le premier joueur . Pour un jeu connexe je ne vois toujours pas comment montrer qu'un jeu à unique case gagnante pour le premier joueur doit être constitué d'une seule case .

Vasimolo

 #44 - 11-10-2012 18:16:55

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

Echeccs 2

Il me semblait implicite que la grille était connexe.

Alors on sait que "grille pavable avec dominos 2x1" => "2eme joueur gagne"

Je me demande si la réciproque est vraie.

 #45 - 11-10-2012 18:37:30

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

zchecs 2

Autre question pour une partie connexe : "pavage avec des dominos <=> nombre identique de cases banches et noires ?"

La condition est clairement nécessaire , est-elle suffisante ?

Vasimolo

 #46 - 11-10-2012 19:18:48

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

Echhecs 2

Non elle n'est pas suffisante sur une grille comme celle-là par exemple :

    N
BNBN
  B

 #47 - 13-10-2012 12:52:03

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

ecjecs 2

Bon j'ai la réponse aux deux questions posées ( sous réserve de vérification ) .

1°) Partie perdue pour le joueur 1 => terrain pavable en dominos .

Montrons la contraposée : non pavable en dominos => gagnant pour le joueur 1 .

Dans une composante connexe bien choisie du domaine on installe un maximum de dominos pour constituer un ensemble connexe ne remplissant pas toute la composante . Le premier joueur va jouer une case voisine de ce terrain de domino et le joueur 2 ne peut que répondre par une case d'un domino sinon il génère un nouveau domino . Le joueur 1 complète le domino et ainsi de suite , ... , le joueur 2 va devoir sortir du circuit de dominos mais alors en décalant les dominos d'une case on crée un ensemble de dominos plus grand .

2°) Les seuls terrains pour lesquels le joueur 1 a une unique case gagnante comportent une case isolée qui est la case gagnante .

On suppose par l'absurde qu'il existe un terrain T de plus d'une case pour lequel le joueur 1 a une seule case gagnante et que cette case X n'est pas isolée . Alors T-X est pavable en dominos et X a comme voisin une case de domino . Il suffit de décaler ce domino vers X pour créer un "trou" qui sera une case gagnante pour 1 ( le complémentaire est pavable en dominos ) .

J'adore ces problèmes à tiroirs smile

Vasimolo

 #48 - 13-10-2012 16:59:55

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

Echeccs 2

Excellent Vasimolo !

Un petit détail : à la place de "le joueur 2 va devoir sortir de l'ensemble de dominos", je dirais "le joueur 2 ne peut pas sortir de l'ensemble de dominos".

 #49 - 13-10-2012 17:03:55

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

Echec 2

Tu me permets d'ouvrir un nouveau tiroir ?

Quelles sont les grilles pavables avec des dominos ?

 #50 - 13-10-2012 18:47:55

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

echecd 2

Là je crains qu'on ne rentre dans des considérations très fines de la théorie des graphes : on cherche un couplage parfait dans un graphe biparti . Il existe des critères caractérisant ces graphes mais je je suis pas sûr qu'ils soient plus faciles à appréhender que "pavable avec des dominos" .

Je peux bien sûr me tromper smile

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 : Riri, Fifi et ?

Sujets similaires

Sujet Date Forum
P2T
Echecs 20 par Vasimolo
11-11-2012 Enigmes Mathématiques
P2T
Echecs 1 par Vasimolo
08-08-2010 Enigmes Mathématiques
P2T
Echecs 13 par Vasimolo
26-08-2012 Enigmes Mathématiques
P2T
Echecs 6 par Vasimolo
11-09-2010 Enigmes Mathématiques
P2T
Echecs 4 par Vasimolo
19-08-2010 Enigmes Mathématiques
P2T
Echecs 19 par Vasimolo
29-10-2012 Enigmes Mathématiques
P2T
Echecs 7 par Vasimolo
18-09-2010 Enigmes Mathématiques
P2T
Echecs 11 par Vasimolo
29-05-2012 Enigmes Mathématiques
P2T
Echecs 14 par Vasimolo
03-09-2012 Enigmes Mathématiques
P2T
Echecs 12 par Vasimolo
01-06-2012 Enigmes Mathématiques

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