|
#1 - 03-04-2016 16:19:35
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Paperron
Voici un petit jeu papier crayon qui se joue sur un quadrillage rectangulaire de taille mxn. Chaque joueur contrôle une moto, le joueur 1 commence en bas à gauche, et le joueur 2, en haut à droite. Par ailleurs :
* Les joueurs jouent chacun leur tour, celui qui ne peut plus jouer a perdu. * À chaque coup, le joueur avance en ligne droite d'autant de cases qu'il le souhaite (au moins une, il ne peut pas rester au même endroit), en coloriant les cases sur lesquelles il passe (y compris les cases initiale et finale). * Il est interdit de passer sur une case déjà coloriée, que ce soit par son adversaire ou par soi-même. * Après chaque coup, le joueur doit obligatoirement tourner de 90° (à droite ou à gauche, comme il veut). * Les joueurs commencent dans la direction qu'ils souhaitent (ils ont le choix entre 2 directions).
Mais un dessin vaut mieux qu'un long discours :
La première partie est remportée par le joueur 1 après qu'il a joué 5 coups, et son adversaire 4.
Il remporte également la deuxième partie, mais après seulement 2 coups de sa part contre 1 de son adversaire.
Le but de l'énigme est de résoudre le jeu sur les plateaux 5x5, 6x6 et 7x7. Par "résoudre", on entend déterminer quel joueur est sûr de gagner s'il joue parfaitement, et avec quelle stratégie.
Amusez-vous bien !
#2 - 03-04-2016 16:42:14
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
papertrin
désolé, mais la première partie n'est pas finie :
Le joueur 2 joue en bas à droite, le joueur 1 devant tourner, il part à gauche et en jouant maximum à gauche, c'est le joueur 2 qui gagne...
Ou alors, je n'ai rien compris aux règles.
#3 - 03-04-2016 18:21:55
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Ppaertron
@gwen27 : le joueur 2 va dans l'autre sens : il commence en haut à droite (2e phrase de l'énoncé), sur la case avec un petit "2". Sinon tu as bien compris les règles
#4 - 03-04-2016 19:27:07
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
paperyron
Hello, Pour le plateau 6x6 le joueur 2 gagne, il lui suffit de jouer la même chose que le joueur 1 en symétrique: si le joueur 1 l'a fait il pourra le faire.
#5 - 03-04-2016 20:27:53
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
Papertrno
Pour 5x5 et 7x7 et par extension les plateaux de (2p+1)x(2p+1) pour tou entier p>0, il me suffit de jouer en premier et me déplacer de p cases à ce 1er coup pour être certain de gagner. En effet, quel que soit le coup de l'adversaire, je joue mon 2è coup en me déplaçant sur (2p-1) ou 2p coups ==> je divise à ce moment le tableau en 2 parties en étant sûr d'avoir la main sur la partie la plus vaste.
Pour le tableau 6x6 et par extension les tableaux (2p)x(2p), je cherche encore un peu.
#6 - 03-04-2016 20:46:50
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
apertron
@Clydevil : bien vu ! 33% du problème est résolu
@kossi_tg : il y a une faille dans ton raisonnement. Teste-le en détail pour le cas 5x5, joue la partie jusqu'au bout.
#7 - 04-04-2016 11:42:26
- Klimrod
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 4050
- Lieu: hébesphénorotonde triangulaire
aPpertron
Salut,
Avec une grille 6x6, le joueur nº2 est sûr de gagner en jouant systématiquement le coup symétrique du joueur nº1.
Du coup avec une grille 5x5 ou 7x7, on a envie de dire que le joueur nº1 peut gagner en occupant le centre, mais ce n'est pas si simple...
En fait, si, c'est simple. Sur une grille 5x5, si le joueur nº1 joue A5, le joueur nº2 réplique B5 et le joueur nº1 a perdu. Si le joueur nº1 commence par A4 ou A2, le joueur nº2 réplique par E3 et le joueur nº1 va perdre. Et si le joueur nº1 commence par A3, le joueur nº2 réplique par E4 et va gagner. Dans tous les cas, le joueur nº2 gagne, ce qui était contre-intuitif...
Mais pour une grille 7x7, c'est le joueur nº1 qui gagne, en commençant par A4.
Klim.
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.
#8 - 04-04-2016 20:05:11
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Paertron
@Klimrod : bravo ! Je suis d'accord avec tes 3 analyses.
#9 - 05-04-2016 06:27:09
- dbab3000
- Professionnel de Prise2Tete
- Enigmes résolues : 48
- Messages : 111
Papretron
Je vais considérer le cas généralement on a un carré n×n Si n est pair: Le 2ème joueur doit juste répéter les mêmes actions que le premier et il va gagner. Si n est impair et (n-1)÷2 est pair Si les 2 joueurs jouent parfaitement c'est le 2ème qui va gagner. Voici la stratégie: Le premier avance de P₁ cases (la direction n'est pas importante) 1er cas: Si P₁<(n-1)÷2 Le deuxième doit avancer D₁ cases tel que D₁=n-2-P₁ (leurs trajets doivent être parallèles) Après peu importe l'action du 1er joueur le deuxième va se déplacer de D₂ cases tel que D₂=n-1 On peut remarquer que peu importe les actions du 1er joueur le 2ème va gagner. 2ème cas Si P₁=n-1 Alors D₁=n-2 (leurs trajets sont orthogonaux) Fin de la partie le 2ème joueur a gagné 3ème cas Si (P₁>(n-1)÷2) et (P₁≠n-1) Alors D₁=n-P₁ (leurs trajets doivent être parallèles) Après peu importe l'action du 1er joueur le deuxième va se déplacer de D₂ cases tel que D₂=n-2 On peut remarquer que peu importe les actions du 1er joueur le 2ème va gagner. 4ème cas P₁=(n-1)÷2 Alors D₁=(n-3)÷2 (leurs trajets doivent être parallèles) Le premier joueur va avancer de P₂ cases. Si P₂<n-2 Alors D₂=n-2-P₂ Peu importe les actions du 1er joueur le 2ème va gagner s'il tourne vers les endroits ou il y a plus de cases. Si P₂=n-2 ou P₂=n-1 Alors D₂=1 Le deuxième joueur devrait gagner s'il prend le plus long chemin possible avant d’être bloqué cependant il va gagner seulement si (n-1)÷2 est pair Si n est impair et (n-1)÷2 est impair C'est le 1er joueur qui va gagner s'il joue selon le 4ème cas avec P₂=n-2
Bonne journée.
#10 - 05-04-2016 20:13:31
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Papertorn
@dbab3000 : impressionnant. OK 6x6. Ton analyse fonctionne pour 5x5 et 7x7 ; pour de plus grandes valeurs de n, je ne suis pas capable de détailler l'analyse au point d'être certain que ça fonctionne (les longueurs optimales des chemins sont difficiles à démontrer, je trouve), mais je pense que c'est bon.
#11 - 06-04-2016 08:02:40
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
papertrpn
Pour moi le 1er qui joue est tjs gagnant.
Au départ pion blanc Bl au Sud Ouest SO pion noir No au Nord Est NE.
Bl joue en 1er, toujours N.
Grille 5*5 Bl joue milieu N: Si N joue O, Bl avance 4 cases E et gagne. Si N joue 1 case S, Bl joue 4 cases E et gagne. Si N joue 3 ou 4 cases S, Bl joue 3 cases E et gagne.
Bl gagne.
Pour les autres grilles impaires, c'est pareil. Bl qui joue prépare la séparation en 2 parts égales de l'échiquier. Il attend que No joue pour décider de la longueur de la séparation centrale. En effet, dans certains cas, Bl devra, et pourra tjs le faire, empiéter de qq cases dans le territoire No, de sorte qu'il attaquera son propre territoire avec un temps de retard, ce qui lui assurera la victoire à tous coups.
#12 - 06-04-2016 12:58:27
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Papertorn
@nodgim : "Si N joue 1 case S, Bl joue 4 cases E et gagne." : en es-tu sûr ?
Et pour les grilles paires ?
#13 - 07-04-2016 16:11:07
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Paperrton
Merci aux participants, et félicitations à Klimrod et dbab3000 qui ont réussi à mener l'étude à bien.
On pourrait chercher à raffiner, soit en généralisant à tous les plateaux, soit en étudiant non pas seulement qui est le vainqueur, mais combien de coups d'avance il peut s'assurer (par exemple, sur le plateau 3x3, le premier joueur est sûr de gagner au moins par 4 coups à 2).
Mais je me permets juste de revenir sur le cas du plateau 7x7. Le premier joueur peut gagner en se déplaçant initialement de 3 cases. Je vous ai représenté une solution ci-dessous :
À gauche, si le 2e joueur commence par une des 3 cases en haut à gauche, le premier joueur monte ensuite de 5 cases, puis il n'a plus qu'à jouer les symétriques des coups du 2e joueur pour être assuré de ne pas être bloqué le premier.
Au milieu, le coup du 2e joueur est suicidaire, et il perd immédiatement.
À droite, si le 2e joueur joue n'importe quel autre coup, le premier joueur peut gagner en jouant le 2e coup présenté, puis, en faisant traîner le plus possible dans la moitié de plateau à gauche. Cependant, tous les participants ont passé sous silence l'argument qui permet de prouver que le premier joueur peut effectivement gagner dans ce cas. Voyez-vous pourquoi ?
Attention, il ne suffit pas de compter les cases libres : que ce soit pour le 1er ou le 2e joueur, dans ce cas, le nombre maximal de coups jouables est strictement inférieur au nombre de cases libres.
#14 - 08-04-2016 09:36:43
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
paprrtron
@nodgim : "Si N joue 1 case S, Bl joue 4 cases E et gagne." : en es-tu sûr ?
il faut lire: Bl joue 3 cases E et gagne.
Et pour les grilles paires ?
Je sais pas, je regarde. Comme ça ne faisait pas partie de l'énigme, j'ai supposé que tu n'avais pas vraiment la réponse. ça me parait de toute façon bien plus délicat....
#15 - 08-04-2016 09:44:51
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Paperron
Pour les carrés pairs, il me semble qu'il suffit au 2ème joueur de jouer le symétrique du 1er joueur pour gagner : 2 joue S si 1 joue N, et O si 1 joue E. C'est comme ci on avançait les 2 pions en même temps.
|
|