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 - 19-10-2012 18:58:46

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

exhecs 18

En ce moment j'ai un peu tendance à délaisser mes gâteaux pour mes grilles smile

Deux joueurs s'affrontent sur un échiquier 11X11 . Ils placent tour à tour un jeton blanc sur une des cases . Le premier qui arrive à former un rectangle parallèle au quadrillage avec les jetons posés gagne la partie .

Ici le joueur qui a joué en deuxième a gagné .

http://imageshack.us/a/img521/6554/echecs18.jpg

Mais quelle est la stratégie gagnante ?

Vasimolo

  • |
  • Répondre

#0 Pub

 #2 - 20-10-2012 19:37:45

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1494
Lieu: Coutiches

Echecs 8

Bon, allez, je vais oser m'attaquer à un de tes problèmes Vasimolo...

Je vais chercher, je te poste mes résultats dès que j'en ai (si j'en ai) roll

 #3 - 20-10-2012 20:20:23

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Echhecs 18

Vas-y sans complexe , la solution ne nécessite rien d'autre qu'un peu de logique et beaucoup d'astuce .

Pour tous , la solution est très abordable smile

Vasimolo

 #4 - 20-10-2012 23:10:15

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

echevs 18

Le premier joueur J1 possède une stratégie gagnante en procédant de la sorte :

Il joue son premier coup n'importe où, puis après un coup de J2 :

Stratégie gagnante de J1 :

-si J2 joue sur une case perdante (j'appelle case perdante une case qui donne immédiatement la victoire à l'autre joueur au coup suivant) : conclure.

-si J2 joue sur une case dont la ligne et la colonne sont vides (coup de type 1) : Jouer sur une case similaire.

-si J2 joue sur une case dont la ligne(resp. colonne) a déjà été jouée (coup de type 2): Jouer sur la même ligne(resp. colonne) que J2, dans une colonne(resp. ligne) vierge.

Un exemple de début de partie sur un échiquier 7x7 :

*00**00
*00**00
**7****
**6****
**3****
*2***00
1**4500

Les cases perdantes sont en *, les non perdantes en 0

Pour expliquer pourquoi ça marche :

Quitte à réarranger les lignes/colonnes lors des coups de type 1, on peut former une diagonale avec les coups de type 1. Ceci définit le carré interdit (sur l'exemple, le carré 3x3 des coups 1,2,3). A l'opposé de ce carré, il y a le carré vierge (sur l'exemple le carré 4x4 où aucun coup n'a été joué), là où seront joués les prochains coups de type 1. Sur les côtés, il y a 2 rectangles où seront joués les coups de type 2 : Le rectangle des lignes (sur l'exemple le rectangle 4x3 des coups 4,5) où J1 joue sur la même ligne que J2, et le rectangle des colonnes (sur l'exemple le rectangle 3x4 des coups 6,7) où J1 joue sur la même colonne que J2.

Toutes les cases du carré interdit sont perdantes. Dans le rectangle des lignes(resp colonnes), les cases jouées définissent des colonnes(resp lignes) entières de cases perdantes, y compris en dehors du rectangle. Par exemple le coup 4 définit deux colonnes de cases perdantes : celle du coup 4 et celle du coup 1. Toutes les autres cases sont non perdantes.

On vérifie par récurrence que :

*Après un coup de J1 :

le carré interdit est de côté impair, le rectangle des lignes a un nombre pair de colonnes vierges, le rectangle des colonnes a un nombre pair de lignes vierges.

*Après un coup de J2 :

-si c'est un coup de type 1 : le carré interdit est de côté pair, le rectangle des lignes a un nombre impair de colonnes vierges, le rectangle des colonnes a un nombre impair de lignes vierges. Ceci assure que J1 pourra rétorquer un coup de type 1, car il reste au moins une case non perdante dans le carré vierge.

-si c'est un coup de type 2 : le carré interdit est de côté impair. Si J2 a joué dans le rectangle des lignes, celui-ci a un nombre impair de colonnes vierges. Ceci assure qu'il reste au moins 1 colonne vierge dans le rectangle des lignes, et donc que J1 pourra rétorquer un coup non perdant dans le rectangle des lignes. Idem pour le rectangle des colonnes.

 #5 - 21-10-2012 09:22:37

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

Echecss 18

Je pars du principe que j'ai deux cases voisines de ma couleur et que les autres dans le carré de 3x3 sont vides au moment où c'est à moi de jouer...
(ce sont les cases marquées 0 )

http://www.prise2tete.fr/upload/gwen27-echecs18.JPG
Mon coup 1 amène au coup 1 des jaunes, idem pour le coup 2 et le coup 3 est gagnant.

Bon, il me faut donc 2 coups d'avance.


Au début du jeu, si le second joueur me "bloque" ce réseau, il suffit de reporter la stratégie sur un pavage de maille double en vertical et j'ai donc bien les deux cases 0
Si au second coup, il me bloque encore, je recommence à chercher un pavage plus large pour le coup 1 en horizontal. et là c'est imparable.

 #6 - 21-10-2012 09:41:10

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

cEhecs 18

Oui c'est assez facile.
Si on fait le décompte de l'occupation des lignes et des colonnes à chaque pose de jeton, donc à (11,11) au départ, le 1er qui joue s'arrangera pour renvoyer toujours un couple de pairs à l'adversaire.
(11,11) --->(10,10) après jeton de A.
Si B joue (10,9), donc son jeton aligné avec le 1er,  on répondra (10,8) donc aligné aussi.
Si B joue (9,9) A répondra par (8,8)
Etc...

 #7 - 21-10-2012 11:47:16

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Eches 18

Que des bonnes réponses smile

Il y a une façon très simple d'expliquer la stratégie gagnante avec un argument de parité , ce qu'a bien vu Nodgim .

Vasimolo

 #8 - 21-10-2012 12:59:37

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1494
Lieu: Coutiches

Eches 18

J'ai du mal à expliquer, mais je dirais qu'il faut jouer "comme l'adversaire" :

Si il se place sur une ligne et colonne vierge, alors il faut faire pareil, et de même si il ne se met que sur une ligne vierge mais une colonne occupé, ou inversement.

 #9 - 12-11-2012 03:47:56

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

Echecs 1

J'ai un peu de mal avec la stratégie de nodgim : "le premier s'arrange pour renvoyer un (pair, pair)". Déjà telle qu'énoncée, la stratégie n'est pas suffisante, si on se contente de faire ça on peut perdre. Il faut rajouter qu'à la première occasion de gagner, il faut conclure. Et puis,

1) Est-ce si évident qu'on peut toujours renvoyer un (pair, pair) ?

2) Et même si on le fait, l'adversaire ne peut-il pas gagner ?

 #10 - 12-11-2012 12:39:49

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

zchecs 18

Les coups possibles pour le joueur 2 .

1°) Il joue sur une ligne et une colonne jamais utilisée .
2°) Il joue sur une ligne déjà utilisée mais pas la colonne
3°) Il joue sur une colonne déjà utilisée mais pas la ligne .
4°) Il joue sur une ligne et une colonne déjà utilisée .

Réponses du joueur 1 :

1°) Il fait exactement pareil .
2°) Il joue sur la même ligne sur une colonne jamais utilisée .
3°) Il joue sur la même colonne et sur une ligne jamais utilisée .
4°) Il fait exactement pareil et gagne .

On voit bien comment fonctionne la parité sur les lignes et les colonnes .

Vasimolo

 #11 - 12-11-2012 13:24:57

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

Echhecs 18

Ok, mais quand il fait un coup de type 4°), ne peut-il pas remporter la victoire avec ce coup ?

Comment prouve-t-on que cette stratégie mène à la victoire ?

 #12 - 12-11-2012 15:43:02

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

ecgecs 18

Tu remarqueras que le joueur 1 ne prend jamais l'initiative de jouer sur une ligne et une colonne déjà jouées or pour gagner il faut que deux joueurs exactement l'aient fait .

Vasimolo

 #13 - 12-11-2012 16:31:02

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

ecjecs 18

Je ne suis pas d'accord avec ta phrase.

Un rectangle peut se faire comme ça :

12
34

Ici le premier coup du type 4°) remporte la victoire.

 #14 - 12-11-2012 17:32:43

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Ecchecs 18

Tu ne respectes pas la stratégie du joueur 1 , il ne doit pas jouer le coup 3 .

Vasimolo

 #15 - 12-11-2012 17:48:02

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

Ececs 18

123
56
4

Je sais bien que J1 aurait pu jouer 5 ailleurs pour gagner, mais je dis que ta phrase "pour gagner il faut que deux joueurs exactement aient joué un coup de type 4°)" n'est pas vraie en général. Et d'ailleurs, ce n'est pas à moi de prouver que J2 peut gagner, mais à toi de prouver que J1 va gagner. Pour l'instant, je ne comprends sincèrement pas pourquoi.

 #16 - 12-11-2012 23:01:10

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Echecs 188

Bon j'ai voulu aller trop vite mais il est clair que l'argument de parité suffit pour conclure , je vais essayer de détailler un peu plus .

J1 joue n'importe où puis :

1°) J2 joue sur la même ligne ou la même colonne que J1 alors toute case de ces colonnes ou lignes ( attention à l'inversion ) deviennent inutilisables sous peine de défaite immédiate on peut donc retirer ces colonnes ou lignes du jeu .

2°) J2 joue sur une nouvelle ligne et une nouvelle colonne alors J1 fait de même .

Il est clair que J1 ne peut pas perdre avec cette stratégie alors J2 va devoir jouer sur une case interdite .

Vasimolo

 #17 - 12-11-2012 23:10:34

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

Echec s18

Vasimolo a écrit:

1°) J2 joue sur la même ligne ou la même colonne que J1 alors toute case de cette colonne ou ligne ( attention à l'inversion ) devient inutilisable sous peine de défaite immédiate on peut donc les retirer du jeu .

"cette colonne" se réfère à la colonne du coup où vient de jouer J2 ?

 #18 - 12-11-2012 23:14:16

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

Echhecs 18

En fait c'est les deux , je corrige !

Vasimolo

 #19 - 13-11-2012 00:18:45

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

echecq 18

Bon finalement, ce n'était pas si simple que ça, on en revient un peu à mon message non ?

 #20 - 13-11-2012 17:51:10

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,373E+3

echevs 18

En effet smile

L'idée est assez intuitive mais la justification un peu laborieuse !

Vasimolo

 #21 - 13-11-2012 18:30:33

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

Ehcecs 18

Je ne comprends pas trop le problème de Titoufred, l'argument de parité que j'avais avancé serait il mis en défaut ?

 #22 - 13-11-2012 21:17:00

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

Echecs 1

Quel argument de parité ?

Qu'est-ce que tu affirmes au juste ?

La question initiale est "Quelle est la stratégie gagnante ?". Quelle stratégie proposes-tu, clairement et de façon complète ?

 #23 - 14-11-2012 18:26:27

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

Eches 18

nodgim a écrit:

Oui c'est assez facile.
Si on fait le décompte de l'occupation des lignes et des colonnes à chaque pose de jeton, donc à (11,11) au départ, le 1er qui joue s'arrangera pour renvoyer toujours un couple de pairs à l'adversaire.
(11,11) --->(10,10) après jeton de A.
Si B joue (10,9), donc son jeton aligné avec le 1er,  on répondra (10,8) donc aligné aussi.
Si B joue (9,9) A répondra par (8,8)
Etc...

ça me semble clair pourtant.
Peut être aurais je dû ajouter la conclusion: si B joue sans faire tourner le compteur, il perd car il joue sur 1 ligne et 1 colonne occupée, A n'a plus qu'à jouer pour terminer le rectangle.

 #24 - 14-11-2012 18:34:44

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

checs 18

Oui, tu aurais dû ajouter ça.
Mais pas que.
Là tu donnes le deuxième coup de A.
Mais qu'en est-il de suivants ?
Quelle stratégie proposes-tu, clairement et de façon complète ?

 #25 - 14-11-2012 19:04:49

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

echevs 18

La réponse de A est toujours de renvoyer un couple de pairs: Si B propose un couple de pairs, A joue derrière une case à colonne et ligne vide. Si B renvoie un couple à une ligne ou une colonne impaire, A joue dans une ligne ou une colonne déja occupée pour rétablir la parité.

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
30-03-2010 Enigmes Mathématiques
P2T
Echecs 15 par Vasimolo
30-09-2012 Enigmes Mathématiques
P2T
Echecs 7 par Vasimolo
18-09-2010 Enigmes Mathématiques
P2T
Echecs 6 par Vasimolo
11-09-2010 Enigmes Mathématiques
P2T
Echecs 21 par Vasimolo
14-11-2012 Enigmes Mathématiques
P2T
Echecs 11 par Vasimolo
29-05-2012 Enigmes Mathématiques
P2T
Echecs 20 par Vasimolo
11-11-2012 Enigmes Mathématiques
P2T
Echecs 22 par Vasimolo
20-08-2013 Enigmes Mathématiques
P2T
Echecs 16 par titoufred
05-10-2012 Enigmes Mathématiques
P2T
Echecs 3 par Vasimolo
16-08-2010 Enigmes Mathématiques

Mots clés des moteurs de recherche

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