Jeu des "petits traits"

[Ben314]

Salut,
Une variante du jeu HEX à laquelle j'ai beaucoup jouè avec un copain lorsque j'était étudiant et que je ne connaissait pas l'HEX (de plus, le matériel de jeu est plus "commun")

Sur une feuille de papier quadrillé, on trace deux segments rouges horizontaux (entre des sommets de carreaux) et deux traits verticaux bleus (entre des milieux de carreaux) de longueur n-1 carreaux et distants de n carreaux (c.f. dessin où n=8)
Les joueurs doivent alors à tour de rôle tracer un segment de longueur 1 allant de sommet à sommet pour le joueur "rouge" et de milieu à milieu pour le joueur "bleu". Les segments n'ont évidement pas le droit de se couper.
Le but du jeu pour chaque joueur est de relier les deux segments de départ par un chemin continu de leur couleur.

On peut évidement jouer à ce jeu (j'en ait fait un paquet de partie durant... les cours d'info) mais aussi, (comme à l'HEX) chercher
1) Pourquoi ne peut-il pas y avoir de match nul.
2) Pourquoi il existe une statégie gagnante pour le joueur qui commence.

Bon, évidement, si on connait les preuves concernant l'HEX, il suffit de les "adapter"...

[windows7]

ca se voit que yavait pas l'iPhone a ton epoque ben :ptdr:

[Imod]

Ce problème me rappelle quelque chose et m'en rappelle un autre , mais plus tard , je fais trop de choses à la fois donc plus grand chose de propre .

Imod

[benekire2]

Doublement intéressant :

1. C'est une vraie énigme pour moi , i.e je vais chercher parce que je connais pas HEX
2. C'est intéressant pour la philo ... parce que je connais pas ce jeu ..

[ffpower]

La 2, ca me rappelle une histoire de tablette de chocolat, c'est p-e à ca qu'Imod pensait..Quand à la 1, che pas trop, mais elle a l'air bien dure..

Edit : j'ai l'impression que 1) impliquerait cet exo :
http://www.maths-forum.com/chemins-un-echiquier-54299.php
dont j'ai jamais trouvé de solutions vraiment satisfaisantes. ( Bon Imod a donné un argument à la fin qui pourrait être une bonne piste mais qui telle quelle ne me convainc pas. D'ailleurs je me rend compte que j'ai à l'époque laisser couler sans répondre, pardon Imod, c'était pas très respectueux :jap: )

Edit 2 : 2010eme message :beer:

[nodjim]

Je crois avoir la solution du 1), le 2) est un peu une corollaire, mais pas tout à fait.
Indice: il faut réfléchir quand tous les segments sont posés.

[Imod]

Edit : j'ai l'impression que 1) impliquerait cet exo :
http://www.maths-forum.com/chemins-un-echiquier-54299.php
dont j'ai jamais trouvé de solutions vraiment satisfaisantes. ( Bon Imod a donné un argument à la fin qui pourrait être une bonne piste mais qui telle quelle ne me convainc pas. D'ailleurs je me rend compte que j'ai à l'époque laisser couler sans répondre, pardon Imod, c'était pas très respectueux :jap: )

Non , l'argument que j'évoquais ne marche pas , je ne l'avais pas signaler vu que plus personne ne semblait s'intéresser à la chose . Il y a sûrement un bête argument de continuité ou connexité à faire jouer encore faut-il mettre le doigt dessus ! Je posterai sur ton fil s'il me vient une nouvelle idée , inutile de polluer plus longtemps le sujet de Ben :zen:

Imod

[Ben314]

Ca ne polue absolument pas le sujet : les problèmes sont fortement ressemblant (bien que pas tout à fait identiques du fait que la notion de "case" ici n'est pas trés bien définie) mais, d'un autre coté, remontrer l'autre sujet s'il n'est pas "totalement traité", c'est une bonne idée.

Sinon, je ne suis pas sûr d'avoir une preuve totalement "carrée-carrée" pour le 1).
Par contre, pour le 2), j'ai l'impression que l'on peut "recopier" la preuve de l'HEX.

P.S. Dans le premier post, j'avais mis un lien sur http://fr.wikipedia.org/wiki/Hex mais je sais pas si tout le monde l'a vu du fait que j'ai voulu faire dans l'esthétique...

[ffpower]

je ne l'avais pas signaler vu que plus personne ne semblait s'intéresser à la chose

C'est mon éternel syndrome du "je répondrai plus tard" ( qui pourrait se généraliser en "je le ferai plus tard" :marteau: )

Pour revenir au sujet : pour la 2, on doit pouvoir créer une bijection entre les coups bleus et les coups rouges ( du genre pour un coup bleu donné : faire une rotation d'un quart de tour par rapport au centre du terrain, puis p-e un décalage d'une demi case ) de sorte que si le 2eme joueur avait une stratégie gagnante, le 1er joueur pourrait jouer un 1er coup n'importe ou puis suivre cette stratégie par la bijection ( et s'il doit jouer là ou il a fait son 1er coup, bah c'est pas bien grave, il joue ailleurs : le coup joué en trop ne peut en aucun cas être handicapant ).
Cet argument n'est évidemment valable qu'aprés avoir répondu à la 1ere question, qui assure l'existence d'une stratégie gagnante pour l'un des joueurs..

[Doraki]

Pour le 1, il me semble bien que si on regarde un dessin rempli et qu'on imagine quelqu'un qui rentre par le coin en haut à gauche avec un mur bleu à sa gauche et un mur rouge à sa droite,
on vérifie plus ou moins facilement qu'il va suivre un chemin sans embranchement, avec toujours du bleu à sa gauche et du rouge à sa droite, et qu'il va finir par sortir soit par le coin haut-droite (dans ce cas il y a un chemin bleu de gauche à droite) soit par le coin bas-gauche (dans ce cas il y a un chemin rouge de haut en bas)

[nodjim]

Pour le 1, il me semble bien que si on regarde un dessin rempli et qu'on imagine quelqu'un qui rentre par le coin en haut à gauche avec un mur bleu à sa gauche et un mur rouge à sa droite,
on vérifie plus ou moins facilement qu'il va suivre un chemin sans embranchement, avec toujours du bleu à sa gauche et du rouge à sa droite, et qu'il va finir par sortir soit par le coin haut-droite (dans ce cas il y a un chemin bleu de gauche à droite) soit par le coin bas-gauche (dans ce cas il y a un chemin rouge de haut en bas)

Télépathie ? C'est aussi ma démarche, faire entrer un petit bonhomme par un coin. Il a toujours un mur bleu sur le même coté et en face un mur rouge.

[Ben314]

Télépathie ? C'est aussi ma démarche, faire entrer un petit bonhomme par un coin. Il a toujours un mur bleu sur le même coté et en face un mur rouge.

Pour rien vous cacher, c'est aussi ma méthode... (et je pense qu'on peut le rédiger assez "carré carré")

[Imod]

J'ai retrouvé deux problèmes très proches de celui de Ben , je les poste ici mais si ça gène je déplace :lol3:

1°) On considère un échiquier dont les cases sont coloriées en noir ou blanc ( n'importe comment ) , alors il est possible pour un roi ( déplacements usuels ) de passer du bord supérieur au bord inférieur de l'échiquier en ne traversant que des cases noires ou de passer du bord gauche au bord droit en ne traversant que des cases blanches .

Je n'ai pas le courage d'illustrer :marteau:

2°) On considère un quadrillage rectangulaire à mailles carrées et dans chaque petit carré on trace une des deux diagonales . Montrer qu'il y a un chemin suivant ses diagonales et joignant le bord gauche au bord droit du rectangle ou le bord supérieur au bord inférieur du même rectangle .



Imod

[nodjim]

Le 1) me parait bizarre. Si on concentre les noires ou les blanches...il faut un minimum d'alternance. Et aussi un minimum d'équilibrage N/B.
Et le 2) ressemble furieusement au problème de Ben314...

[Imod]

Le 1) me parait bizarre. Si on concentre les noires ou les blanches...il faut un minimum d'alternance. Et aussi un minimum d'équilibrage N/B.

Je ne vois pas pourquoi ?

le 2) ressemble furieusement au problème de Ben314...

C'est un peu pour ça que je l'ai mis ici :we: il y a quand même des différences .

Imod

[beagle]

les questions d'Imod sont curieuses,
pour le 1) je ne vois qu'un échiquier classique
alors une diagonale descendante arrive à un bord et la diagonale perpendiculaire descend jusqu'en bas

pour le 2) l'alternance de zig et zag, un coup vers le haut, un coup vers le bas traverse de part en part.

il faut justifier cela mathématiquement?

[beagle]

Je ne vois pas pourquoi ?


C'est un peu pour ça que je l'ai mis ici :we: il y a quand même des différences .

Imod

le roi est sur la seule case noire de l'échiquier, toutes les autres sont blanches, ça parait dur d'avancer, je suis comme Nodjim, pas bien compris.

[Imod]

Il n'est pas obligé de se positionner sur cette "mauvaise case" . Je n'ai pas dit qu'il existait un chemin partant de toute case de bord .

Imod

[beagle]

Pour la 2)
on part d'un endroit à gauche,
on descend jusqu'en bas, on remonte jusqu'en haut
rien ne peut arréter cette continuité,
or le nombre de case est limité, donc on peut ressortir de l'autre coté.
Et pour le mème nombre de cases qu'en avançant tout droit.

[beagle]

Il n'est pas obligé de se positionner sur cette "mauvaise case" . Je n'ai pas dit qu'il existait un chemin partant de toute case de bord .

Imod

OK, super merci je viens juste de comprendre le mot OU.
Lu trop vite, ok.
En effet, j'ai 2 couleurs pour bloquer au moins 3 directions, je ne peux pas construire d'échiquier qui interdirait ta condition, OK.

de ce fait je comprends seulement maintenant ta construction des diagonales du 2)
J'ai plongé trop vite.
idem deux diagonales possibles or une seule alternative pour bloquer à droite = la mème alternative pour bloquer en dessous, impossibilité de bloquer le passage.