Démonstration : colorer une grille en X mouvements minimum

[Obwil]

Bonjour,

Voici une version simplifiée de mon précédent défi inspiré de la série Squid game.

Soit la grille suivante :


En démarrant de la case avec un carré noir, on se déplace sur la grille horizontalement ou verticalement.

Quand on va sur une case on inverse sa couleur (blanc devient bleu et bleu devient blanc).
On peut retourner sur une case déjà parcourue et sa couleur est inversée à nouveau.

Est-il possible de faire la démonstration que notre tracé doit obligatoirement passer au minimum sur 4 cases bleues pour que toutes les cases soient bleues?

[Obwil]

J'ai conscience de la complexité de ce défi, sauriez-vous de quelle branche des mathématiques il se rapproche le plus?

[GaBuZoMeu]

Bonsoir,

Ton énoncé n'est pas très clair : que veut dire "passer au minimum sur 4 cases bleues" ? On prend en compte la couleur de la configuration de départ ? ou la couleur de la case quand on y arrive ?

[lyceen95]

Je pense que la solution ne se trouvera pas dans un cours de maths, aussi élevé soit-il. Ou alors, ce sera un truc si compliqué que ni toi ni moi ni ... ne sauront l'exploiter.
On est dans le domaine de l'informatique.
On recense tous les chemins ... en essayant d'éviter les chemins qui passent trop de fois par les mêmes cases, pour éviter les chemins de longueur trop longue, et on devrait constater qu'aucun de ces chemins ne peut colorier toute la grille en bleu, sans passer par au moins 4 cases bleues.

[GaBuZoMeu]

Pas d'accord. On est dans le domaine de la combinatoire, et on ne peut pas exclure un argument mathématique.

[Obwil]

Bonsoir,

Ton énoncé n'est pas très clair : que veut dire "passer au minimum sur 4 cases bleues" ? On prend en compte la couleur de la configuration de départ ? ou la couleur de la case quand on y arrive ?

N'importe quel tracé qui permettrait de remplir la grille en bleu doit à un moment passer sur au minimum 4 cases bleues, qui du coup deviendront blanches et il faudra repasser dessus pour qu'elles deviennent bleues à nouveau.
On part de la configuration telle que sur la photo et on se déplace, et dès qu'on arrive sur une case elle change de couleur.

J'ai codé une petite simulation qui vous permettra peut-être d'y voir plus clair : http://simili-le-jeu.com/jeu3.html

Etant donné qu'il y a une règle établie, comme quoi on doit obligatoirement avoir 4 cases bleues à passer dessus pour n'importe quel tracé, je me dis qu'il doit y avoir une règle mathématique derrière.

[Obwil]

Je pense que la solution ne se trouvera pas dans un cours de maths, aussi élevé soit-il. Ou alors, ce sera un truc si compliqué que ni toi ni moi ni ... ne sauront l'exploiter.
On est dans le domaine de l'informatique.
On recense tous les chemins ... en essayant d'éviter les chemins qui passent trop de fois par les mêmes cases, pour éviter les chemins de longueur trop longue, et on devrait constater qu'aucun de ces chemins ne peut colorier toute la grille en bleu, sans passer par au moins 4 cases bleues.

Je suis d'accord avec toi pour l'obligation de créer un algorithme.

J'ai commencé par faire l'hypothèse que l'on a besoin d'un nombre de déplacements égal au nombre de cases blanches + n = 0 cases bleues. Ayant posé cette condition je procède à créer tous les tracés possibles pour x déplacements, pour x+1 déplacements, pour x+2 déplacement etc. Et chaque fois que je crée un nouveau déplacement j'analyse la grille pour savoir si le tracé correspondant est bon ou pas.

Si je n'aboutis à aucun tracé au bout d'un moment alors je fais une nouvelle hypothèse qui est que le nombre de déplacements est égal au nombre de cases blanches + n+1 cases bleues, etc.

J'ai trouvé quelques façons de filtrer mais elles sont trop peu efficaces, et l'algorithme que je recherche permettrait à lui seul de filtrer tous les tracés générés.

[lyceen95]

Tu dois prendre en compte en plus des déplacements où on passerait 3 fois sur une case blanche...
Il y a beaucoup des questions de parités derrière ce challenge.

On va numéroter les cases ... pour la suite de la discussion, comme sur un échiquier.
Les colonnes sont ABCD , de gauche à droite, et les lignes sont 1,2,3,4, de bas en haut.
Les cases blanches sont donc A1 B2 D2 C3 B4 C4 D4
Pour chaque case blanche, on regarde combien de ses voisines sont blanches.
Si chaque case blanche avait 2 voisines blanches ... ce serait super, on aurait un beau chemin , passant une fois et une seule par chaque case blanche.
Quand une case blanche a une seule voisine de couleur blanche, ou 3 voisines de couleur blanche, c'est le début des ennuis.
Si cette case est la 1ère du trajet, ou la dernière, ça va. Sinon, ça va mal.
Voilà quelques considérations qui permettent d'attaquer le problème.

[GaBuZoMeu]

Obwil, tu n'as pas répondu à ma question. Alors je la répète :
Quand tu dis "le tracé doit obligatoirement passer au minimum sur 4 cases bleues", tu parles de la couleur des cases dans la configuration de départ ou de la couleur des cases quad on y arrive en cours de trajet ?
Précisément s'il s'agit de la couleur des cases dans la configuration de départ, on peut faire en ne visitant que 3 des cases bleues de la configuration de départ.

[Obwil]

Obwil, tu n'as pas répondu à ma question. Alors je la répète :
Quand tu dis "le tracé doit obligatoirement passer au minimum sur 4 cases bleues", tu parles de la couleur des cases dans la configuration de départ ou de la couleur des cases quad on y arrive en cours de trajet ?
Précisément s'il s'agit de la couleur des cases dans la configuration de départ, on peut faire en ne visitant que 3 des cases bleues de la configuration de départ.

Ah d'accord je n'avais pas bien compris. Il s'agit de la couleur des cases quand on y arrive en cours de trajet, donc ce peuvent être soit des cases bleues à la base soit des cases blanches à la base que l'on a changées en bleu.

[Obwil]

Tu dois prendre en compte en plus des déplacements où on passerait 3 fois sur une case blanche...
Il y a beaucoup des questions de parités derrière ce challenge.

On va numéroter les cases ... pour la suite de la discussion, comme sur un échiquier.
Les colonnes sont ABCD , de gauche à droite, et les lignes sont 1,2,3,4, de bas en haut.
Les cases blanches sont donc A1 B2 D2 C3 B4 C4 D4
Pour chaque case blanche, on regarde combien de ses voisines sont blanches.
Si chaque case blanche avait 2 voisines blanches ... ce serait super, on aurait un beau chemin , passant une fois et une seule par chaque case blanche.
Quand une case blanche a une seule voisine de couleur blanche, ou 3 voisines de couleur blanche, c'est le début des ennuis.
Si cette case est la 1ère du trajet, ou la dernière, ça va. Sinon, ça va mal.
Voilà quelques considérations qui permettent d'attaquer le problème.

Alors c'est intéressant, je vais tester cette théorie, si un groupe de cases blanches est composé de cases blanches qui ont chacune au moins deux voisines blanches. Je pourrais alors pour chaque groupe de blanches déterminer le nombre de cases bleues qui doivent devenir blanches pour avoir ce scénario. C'est une piste encourageante.

[lyceen95]

Attention, je disais : si chaque case blanche a exactement 2 cases voisines blanches...et pas au moins.

Ce n'est pas de la théorie, c'est du bon sens. Si chaque case blanche a 2 voisines blanches, il y en a une qu'on va appeler la précédente, et une autre qu'on va appeler la suivante... et on se retrouve avec un trajet qui passe une fois et une seule par ces cases blanches.

Enfin presque. On peut avoir un premier trajet qui passe par quelques cases blanches, et, à un autre endroit, un autre trajet qui passe par un autre groupe de cases blanches.

On a d'autres cas, qui compliquent encore tout ça.
Si la case P a 3 voisines blanches, et Q a aussi 3 voisines blanches, et P et Q sont voisines, on peut faire comme si il y avait un mur entre P et Q, pour se ramener au cas où P et Q ont chacune 2 voisines blanches.

[phyelec]

Bonjour,

Je viens de lire ce poste, quel est le but du jeu ; toutes les cases blanches ou bleues?

[GaBuZoMeu]

Relis attentivement les dernières lignes du premier message.

[phyelec]

Ok, sorry, merci GaBuZoMeu

[Obwil]

Attention, je disais : si chaque case blanche a exactement 2 cases voisines blanches...et pas au moins.

Ce n'est pas de la théorie, c'est du bon sens. Si chaque case blanche a 2 voisines blanches, il y en a une qu'on va appeler la précédente, et une autre qu'on va appeler la suivante... et on se retrouve avec un trajet qui passe une fois et une seule par ces cases blanches.

Enfin presque. On peut avoir un premier trajet qui passe par quelques cases blanches, et, à un autre endroit, un autre trajet qui passe par un autre groupe de cases blanches.

On a d'autres cas, qui compliquent encore tout ça.
Si la case P a 3 voisines blanches, et Q a aussi 3 voisines blanches, et P et Q sont voisines, on peut faire comme si il y avait un mur entre P et Q, pour se ramener au cas où P et Q ont chacune 2 voisines blanches.

Je ne saisis pas bien ton dernier exemple avec les cases P et Q.
J'avais commencé à créer un filtre qui analysait le nombre de cases "isolées" c'est à dire qui n'ont qu'une voisine dans un groupe de cases blanches. Mais au final j'ai laissé tomber car je ne peux pas faire de généralités à cause de la variable de la case par laquelle on rentre dans un groupe de cases blanches.

[Ben314]

Salut,
Si tu rajoute dans ta grille des symboles O et X comme un damier :
OXOX
XOXO
OXOX
XOXO
Alors, sur les 7 cases blanches, il y en a 6 qui portent un X.
Or, vu la règle, à chaque mouvement, on passe d'une case X à une case O et réciproquement.
Donc une suite de mouvement passant au moins une fois par chacune de ces 6 cases avec un X doit, au minimum, passer par 5 cases avec un O : XOXOXOXOXOX (mais, bien sûr, certains O de cette série peuvent représenter la même case)
Et comme au départ, des cases blanches avec un O, il n'y en a qu'une seule, soit on passe sur au moins 4 cases O bleues au départ, soit on passe plusieurs fois sur la case O blanche au départ (un nombre impair de fois évidement)

[Obwil]

Salut,
Si tu rajoute dans ta grille des symboles O et X comme un damier :
OXOX
XOXO
OXOX
XOXO
Alors, sur les 7 cases blanches, il y en a 6 qui portent un X.
Or, vu la règle, à chaque mouvement, on passe d'une case X à une case O et réciproquement.
Donc une suite de mouvement passant au moins une fois par chacune de ces 6 cases avec un X doit, au minimum, passer par 5 cases avec un O : XOXOXOXOXOX (mais, bien sûr, certains O de cette série peuvent représenter la même case)
Et comme au départ, des cases blanches avec un O, il n'y en a qu'une seule, soit on passe sur au moins 4 cases O bleues au départ, soit on passe plusieurs fois sur la case O blanche au départ (un nombre impair de fois évidement)

Salut, j'ai essayé d'appliquer cette logique à une autre grille comme celle-ci dont je sais que les tracés les plus courts doivent passer par 7 cases bleues au minimum. Je n'ai pas l'impression que ça fonctionne..
Du coup on aurait OXOXOXOXOXOXOXOX, soit les 6 blanches en O, les 8 blanches en X et 2 bleues en O.
Alors qu'on doit obligatoirement avoir OXOXOXOXOXOXOXOXOXOXOXOXOXOX.



J'ai créé la grille à la cette url pour essayer : http://simili-le-jeu.com/jeu3_2.html