GaBuZoMeu a écrit: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 a écrit: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 a écrit: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.
lyceen95 a écrit: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.
lyceen95 a écrit: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.
Ben314 a écrit: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)
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :