Messages de enigmegraphe

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.

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: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é.

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

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.

up

up

up

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

vinz en sueur

t'as aussi 66% de chances d'avoir neutre ou défavorable

Je n'ai toujours pas la réponse, mais visiblement c'est vraiment un problème assez chaud.
Pour vous donner une idée, je l'ai posée à plusieurs chercheurs spécialistes de la théorie des graphes, ainsi qu'à des doctorants en informatique et post doc (tous plutôt familiers avec la théorie des graphes) et pour l'instant absolument personne n'a trouvé la réponse, ni même fait une avancée majeure. (Alors qu'ils sont plusieurs dans le lot à y avoir réfléchi plusieurs heures, et qu'on se partage nos idées dès qu'on en a).

Le 14 juin 2022 à 23:49:04 :

Le 14 juin 2022 à 03:45:28 :
C'est un problème très dur.
Il me semble qu'il y'a un conjecture actuelle en maths qui dit "Tout entier naturel (non premiers) peut s'écrire comme la somme de deux nombres premiers"

Essayes avec 27

ou 3.

Les golems : "Non mais c'est normal qu'elle grandisse, elle va finir par rapetisser d'ici quelques jours vous verrez"

La vérité : https://youtu.be/koOQGxD4YLQ?t=175 (nous dans deux semaines).

Le 13 juin 2022 à 23:24:37 :
Non Kévin on fera pas ton devoir maison de théorie des graphes

Je me doute que tu n'es pas capable de le faire tkt.
C'est pas un DM, c'est une "énigme" qu'on m'a posé mais le type qui me l'a posée n'a pas non plus la solution.
Je cherche dans mon coin et je ne lirai pas le détail des différentes réponses tant que j'aurai pas abandonné, mais au cas où j'abandonne j'aimerais bien que quelqu'un ait trouvé une solution élégante.

Considérons le graphe d'une grille carrée, de taille n*n.
Par exemple, pour n=5 :
http://sketchtoy.com/70760924
Si on prend deux sommets quelconques, il existe bien sûr plusieurs chemins différents permettant de lier l'un à l'autre.
Voici par exemple 3 chemins différents permettant de relier les 2 points verts :
http://sketchtoy.com/70760927
Le chemin rose est très long, en revanche le chemin vert et le chemin orange sont tous deux des "plus courts chemins" : je ne peux pas relier les deux points verts en passant par moins de 4 arêtes.

Enigme :

a) Est-il possible de trouver n "plus courts chemins" qui sont tous disjoints les uns des autres (ie ils ne doivent pas passer par les même sommets) et qui couvrent tous les sommets de la grille ?
Réponse :Evidemment que oui... voici deux exemples pour la grille 5x5, qui se généralisent évidemment. Il existe bien sûr plein d'autres exemples.
http://sketchtoy.com/70760930
http://sketchtoy.com/70760929

b) Quel est le nombre minimal de "plus courts chemins" disjoints deux à deux dont on a besoin, pour recouvrir une grille de taille n x n ?
Réponse :Jsp. pour n=1, n=2 ou n=3 on prouve facilement qu'on ne peut pas faire mieux que n chemins. Pour le cas général, c'est moins clair, mais j'imagine que c'est pareil.