Jeu des "petits traits"

[Imod]

Regarde un départ sur toutes autres cases que celles que j'ai choisi :triste:

Imod

[beagle]

c'est issu de la théorie des graphes ces degrés de liberté ?

[nodjim]

Pour le roi sur l'échiquier:
S'il existe des zones de déplacement limité, alors on peut se déplacer totalement à l'extérieur de cette zone. Selon que ces zones vont d'un coté à l'autre ou pas, on en déduit effectivement la possibilité de traverser, soit à l'intérieur de l'une de ces zones, soit à l'extérieur.

[nodjim]

Pour le 2), c'est au fond la même chose que le problème de Ben: On remplace les diagonales par des murs. Si, en partant d'un coté, on n'arrive pas à celui d'en face, en ayant essayé toutes les possiblités,c'est qu'il existe un mur continu qui nous en empêche. En revanche, si on parvient à atteindre l'autre coté, c'est qu'on a longé un mur en continu.

[Ben314]

J'ai pas la soluce, mais il me semble qu'il y a un fort lien entre les deux :
Si on part d'un damier colorié en noir/blanc et que, dans la case de coordonnées (x,y) on met un trait en diagonale / ou \ selon la valeur de x+y+c modulo 2 {où c=0 ou 1 selon la couleur de la case}, on obtient un dessin du type du 2°) et une solution à ce "dessin" donne un trajet monochrome de haut en bas ou bien de droite à gauche.

Edit : sauf que l'énoncé du 1) demande du noir de haut en bas OU du blanc de droite à gauche donc... ce n'est pas tout à fait exactement pareil...

Il n'empèche que, dans le cas du 2, si on peut passer, en suivant des traits, d'une case (x,y,t) à une autre (x',y',t') {où t,t' valent 0 ou 1 selon que la case contient / ou \) alors x+y+t = x'+y'+t' modulo 2... (mais est-ce utile ?)

[Imod]

Pour les deux exercices que j'ai proposé je n'ai pas trouvé de solution simple , j'en ai trouvé une quand même avec des trucs "un peu" lourds du genre Borsuk-Ulam ou Sperner .

Imod

Edit : Le problème avec les diagonales est quasiment équivalent à celui de Ben , mais la forme du terrain et l'objectif ne sont pas tout à fait les mêmes .

[Ben314]

Pour le problème sur l'échiquier,
Je colorie en vert les cases en dehors de l'échiquier "au dessus" puis je colorie (récursivement) en vert toute case noire dont une des voisine (au sens des déplacement d'un roi) est verte.
Une fois ce coloriage fini, si une des case du bas de l'échiquier est verte et il y a un trajet vert (donc noir !!!) de haut en bas
Si aucune des cases du bas de l'échiquier n'est verte et il me semble qu'en partant du coin haut gauche et en suivant la frontière verte j'obtient mécaniquement un trajet blanc de gauche à droite (bon, c'est là qu'il peut y avoir des objections "pas assez formel ton truc"...)

[Imod]

Si aucune des cases du bas de l'échiquier n'est verte et il me semble qu'en partant du coin haut gauche et en suivant la frontière verte j'obtiens mécaniquement un trajet blanc de gauche à droite (bon, c'est là qu'il peut y avoir des objections "pas assez formel ton truc"...)

Tout est dit :lol3:

Imod

[Ben314]

A la limite, pour que ce soit plus "carré-carré", je colorie en blanc les cases en dehors de l'échiquier "a gauche" y compris la case à gauche de la ligne de vertes déjà ajoutée au dessus.
Cela permet de partir (en direction du bas) de l'arrète située à droite de cette case blanche. On démare donc avec du blanc à sa droite et du vert à gauche. On suit les arrête en respectant "droit=blanc ; gauche=vert" et, à chaque étape, on a une ou deux possibilités. S'il y en a deux, on en prend une au pif, mais, si on revient au même sommet, on prendra la deuxième. Comme le procédé est forcé de s'arrêter, on conclue.

[Ben314]

On "injecte" du rouge par en haut et, si le rouge n'atteint pas le bas, on rentre dans le "labyrinte" (en bleu sur le dessin) par la gauche juste en dessous du trait rouge le plus bas (il y en a forcément un et il ne peut pas être tout en bas) : on obtient un tracé bleu qui, à sa gauche suit une ligne rouge et qui, à sa droite suit une ligne qui va de gauche à droite (en faisant quelques aller-retours...).

Edit : et d'ailleurs, la ligne rouge "à sa gauche" fait aussi un trajet de gauche à droite...

[Imod]

Pour le problème des diagonales je suis convaincu , j'ai un peu plus de mal avec le roi sur l'échiquier , mais bon , la fatigue ...

Imod