[ENIGME 150 QI] Couvrir une GRILLE

Considérez une grille de forme carrée.

Vous devez tracer plusieurs chemins sur cette grille, tels que :
-Si un de vos chemins commence à aller dans une direction (donc nord, sud, est ou ouest) alors il est interdit que ce chemin aille par la suite dans la direction opposée.
-Deux chemins différents ne passent jamais par un même sommet ou par une même arête.

Le but est de recouvrir tous les sommets de la grille, en utilisant le moins de chemins possible.

Existe-t-il une grille de taille n x n qu'on peut recouvrir avec strictement moins de n chemins ?

Quelques exemples de recouvrements valides pour la grille 5x5 :
https://image.noelshack.com/fichiers/2022/24/6/1655574466-bonrecouvrements.png

Quelques exemples de recouvrements INVALIDES pour la grille 5x5 :
https://image.noelshack.com/fichiers/2022/24/6/1655574499-mauvaisrecouvrements.png

Je précise d'avance, je ne connais PAS la réponse mais j'aimerais que les kheys y réfléchissent ensemble. Non ce n'est pas un DM ou un exercice, c'est un problème a priori assez difficile puisque plusieurs doctorants et docteurs dans mon entourage y réfléchissent depuis quelques jours.

up

up

up

Métallique la grille?

Déjà pour 1x1 c'est impossible ça c'est sur !

Pourquoi sur la "figure de gauche" du premier screen t'as mis un "chemin" tout seul alors que techniquement il pouvait ne pas l'être sur cet exemple ?

Le 19 juin 2022 à 01:25:30 :
Pourquoi sur la "figure de gauche" du premier screen t'as mis un "chemin" tout seul alors que techniquement il pouvait ne pas l'être sur cet exemple ?

J'ai montré des recouvrements possibles, mais effectivement je ne les ai pas forcément créés de façon optimale.

À quoi sert cette grille?

Le 19 juin 2022 à 01:27:24 :
À quoi sert cette grille?

à se faire couvrir par n-1 chemins. Mais on sait pas si c'est possible, c'est le problème

Oui sur un 3X3 c'est possible

Le 19 juin 2022 à 01:29:43 :
Oui sur un 3X3 c'est possible

Prouve-le, car je n'y crois pas.
Sur un 3x3 tu peux faire un recouvrement avec seulement deux chemins en faisant une croix gammée, mais les deux chemins se croisent donc ça n'est pas toléré.

Si je démontre que c'est impossible tu valides ?

A partir du point en haut à gauche: Est sud sud est nord nord est sud sud sud
Et le deuxieme chemin par du sommet juste en dessous du point de départ du premier chemin: Sud sud est est

Le 19 juin 2022 à 01:31:34 :
Si je démontre que c'est impossible tu valides ?

Je pense aussi que c'est impossible qu'une telle grille existe.
Si tu postes une démo je la lirai et je te dirai si j'y vois une faille ou non, si j'en vois pas bah ouais je te la valide même si en soi on pourrait tous les deux se tromper sur la véracité de ta preuve.

Le 19 juin 2022 à 01:31:54 :
A partir du point en haut à gauche: Est sud sud est nord nord est sud sud sud
Et le deuxieme chemin par du sommet juste en dessous du point de départ du premier chemin: Sud sud est est

tu peux pas aller au sud puis au nord avec un seul chemin, puisque ce sont deux directions opposées.

J'ai l'impression que c'est pas possible, mais ça m'a l'air galère à démontrer

Le 19 juin 2022 à 01:34:05 :

Le 19 juin 2022 à 01:31:54 :
A partir du point en haut à gauche: Est sud sud est nord nord est sud sud sud
Et le deuxieme chemin par du sommet juste en dessous du point de départ du premier chemin: Sud sud est est

tu peux pas aller au sud puis au nord avec un seul chemin, puisque ce sont deux directions opposées.

Ah mais je pensais que c''était juste l'opposé première direction qui était interdite par la suite déso

Les lo QI qui se passionnent pour des enigmes eco+ vous etes les meilleurs

Le 19 juin 2022 à 01:35:19 :

Le 19 juin 2022 à 01:34:05 :

Le 19 juin 2022 à 01:31:54 :
A partir du point en haut à gauche: Est sud sud est nord nord est sud sud sud
Et le deuxieme chemin par du sommet juste en dessous du point de départ du premier chemin: Sud sud est est

tu peux pas aller au sud puis au nord avec un seul chemin, puisque ce sont deux directions opposées.

Ah mais je pensais que c''était juste l'opposé première direction qui était interdite par la suite déso

Non effectivement j'avais peur que ça ne soit pas clair quand j'ai rédigé mais je m'étais dit que les exemples clarifiraient la règle.

L'idée c'est que quand tu relies deux sommets, tu dois toujours le faire avec des chemins les plus courts possibles, aucun détour autorisé.