[ENIGME 150 QI] Couvrir une GRILLE

Le 19 juin 2022 à 01:37:42 :
As-tu un contre-exemple si on enlève la condition "deux chemins différents ne passent jamais par un même sommet ou par une même arête" ?

Oui, une croix gammée.

Le 19 juin 2022 à 01:39:47 :

Le 19 juin 2022 à 01:37:42 :
As-tu un contre-exemple si on enlève la condition "deux chemins différents ne passent jamais par un même sommet ou par une même arête" ?

Oui, une croix gammée.

Ah oui en effet, merci.

Le 19 juin 2022 à 01:42:10 :
J'imagine qu'une question intermédiaire, c'est de montrer que si tous les chemins sont de même direction (par exemple tous Nord-Est), alors la borne n fonctionne. Est-ce que tu sais démontrer ça ?

Ah bah oui : on prend la diagonale perpendiculaire et chaque sommet appartient à au plus un chemin

Pour cette question intermédiaire, pas besoin du non-croisement des chemins, d'ailleurs.

Le 19 juin 2022 à 01:45:02 :
En fait, en y réfléchissant un peu, je pense que c'est pas si difficile que ça à démontrer. Mais là, je suis au lit. Je vais pas rallumer pour sortir une feuille et faire la démo

La marge est trop petite ?

Le 19 juin 2022 à 01:42:10 :
J'imagine qu'une question intermédiaire, c'est de montrer que si tous les chemins sont de même direction (par exemple tous Nord-Est), alors la borne n fonctionne. Est-ce que tu sais démontrer ça ?

Non, mais effectivement ça pourrait être un résultat utile à démontrer.

EDIT : ah bah tu viens de le démontrer, bien

Le 19 juin 2022 à 01:45:02 :
En fait, en y réfléchissant un peu, je pense que c'est pas si difficile que ça à démontrer. Mais là, je suis au lit. Je vais pas rallumer pour sortir une feuille et faire la démo

Il n'est pas impossible qu'il existe une preuve "bidon", mais honnêtement j'irai pas parier là-dessus :
J'ai parlé de ce problème à des chercheurs spécialistes de la théorie des graphes et ils n'ont pas (encore) trouvé la solution. Bon, je ne pense pas qu'ils aient TOUS passé des heures à y réfléchir, mais pour au moins un ou deux je sais qu'il y réfléchissent régulièrement.

Le 19 juin 2022 à 01:38:41 Yusei_Fudo a écrit :
Du coup je pense que le résultat n-1 est impossible, parce que ce sont des carrés et qu'avec cet énoncé, il n'est pas possible de recouvrir un carré entier en un seul chemin, peu importe la valeur de n

Bref, pour mieux l'expliquer, je pense que l'exemple du haut et l'exemple de droite sur le premier screen sont la démonstration "optimisée" du problème créé par ces conditions. En faisant une grille n*n t'as forcément n entrées et n sorties donc n chemins minimums

S'il s'avère que je me trompe, la solution m'intéresse, mais je ne pense pas me tromper

Sur un domaine général qui serait un sous-graphe fini quelconque du réseau carré, as-tu une formule conjecturale pour le n optimal ? Si oui, on pourrait envisager de la démontrer par récurrence sur le nombre de chemins qu'on enlève et en déduire comme corollaire le cas du carré.

En fait, on est en train de chercher un invariant, où une quantité du genre "si j'enlève un chemin à mon graphe, je fais diminuer telle quantité d'où plus cela". Si tout est orienté dans le même sens, on tombe sans trop de difficulté sur une telle quantité en regardant la direction perpendiculaire, qui révèle plus ou moins une relation d'ordre cachée. Sauf que dans ton problème, on n'a pas cette hypothèse... mais qu'on a une hypothèse (qu'on doit exploiter) de non-croisement. Toute la question, c'est donc "comment exploiter le caractère orienté des chemins (sans que les orientations soient compatibles) et le caractère disjoint des chemins ?" Ca semble délicat à faire interagir, tout ça.

Intéressant...

Le 19 juin 2022 à 01:46:20 :

Le 19 juin 2022 à 01:45:02 :
En fait, en y réfléchissant un peu, je pense que c'est pas si difficile que ça à démontrer. Mais là, je suis au lit. Je vais pas rallumer pour sortir une feuille et faire la démo

La marge est trop petite ?

D'accord jean fermat

n x n grille = n² cases
Pour qu'un ensemble de n chemins couvre tous les sommets il faut que chaque chemin couvre un ensemble de sommet tel que pour chaque chemin couvrant n+x il existe un chemin couvrant n-x sommet, tel que la somme de tous les n+x et n-x soit = n²

Supposons qu'il existe cette formation de n chemins telle que ((n+x1) + (n+x2) ... + (n-x1) + (n-x2) ... ) = n²

Remarquons également qu'un chemin de taille maximale pour une grille de taille n est de longueur 2n-1

supposons maintenant qu'il est possible de rallonger un chemin de telle sorte qu'un autre chemin plus petit disparaisse, on a alors un chemin :

((n+x1+n-xy) + n+x2 + ... + n-x1 + n-x2 + ... + n-xy-1) -> Un chemin de taille 2n+x1-xy et on sait que x1-xy doit etre <= -1 car le plus grand chemin mesure 2n-1. Cela implique que x1 < xy. Cependant l'existence de ce chemin implique l'existence d'un chemin de taille (x1-xy) qui n'existait pas auparavant.

Par conséquent si on créé un nouveau chemin qui en fusionne deux on créé automatiquement un chemin nouveau de taille (x1-xy). Donc on conserve n chemins.

C'est à vérifier mais la comme ça ça a l'air de tenir la route.

edit : J'ai trouvé un problème potentiel mais pas encore convaincue que c'est un problème lmao

edit2 : l'unicité de 2n-1 résout le problème que je venais de trouver

Le 19 juin 2022 à 01:57:35 :

Le 19 juin 2022 à 01:38:41 Yusei_Fudo a écrit :
Du coup je pense que le résultat n-1 est impossible, parce que ce sont des carrés et qu'avec cet énoncé, il n'est pas possible de recouvrir un carré entier en un seul chemin, peu importe la valeur de n

Bref, pour mieux l'expliquer, je pense que l'exemple du haut et l'exemple de droite sur le premier screen sont la démonstration "optimisée" du problème créé par ces conditions. En faisant une grille n*n t'as forcément n entrées et n sorties donc n chemins minimums

S'il s'avère que je me trompe, la solution m'intéresse, mais je ne pense pas me tromper

Intéressant comme idée mais par exemple, si on considère que les entrées/sorties qualifient les sommets au bord du carré, alors il est possible de couvrir toute la frontière avec deux chemins seulement : un L et un L inversé. Bien sûr, ça laisse à gérer un carré à l'intérieur n-2 par n-2.

Bref, je n'ai pas l'impression que ton argument suffise tel quel. Mais il n'est pas du tout exclu qu'on puisse le faire marcher en le malaxant convenablement.

Si on a un chemin qui ne fait que longer un bord (autant le faire couvrir intégralement deux côté du bord, alors, j'imagine), alors on se ramène à un carré d'1 plus petit et 1 chemin de moins, donc c'est bon. Si ma parenthèse précédente et correcte, on peut donc supposer qu'aucun chemin n'est inclus dans le bord du carré.

Le 19 juin 2022 à 02:01:55 :
n x n grille = n² cases
Pour qu'un ensemble de n chemins couvre tous les sommets il faut que chaque chemin couvre un ensemble de sommet tel que pour chaque chemin couvrant n+x il existe un chemin couvrant n-x sommet, tel que la somme de tous les n+x et n-x soit = n²

Supposons qu'il existe cette formation de n chemins telle que ((n+x1) + (n+x2) ... + (n-x1) + (n-x2) ... ) = n²

Remarquons également qu'un chemin de taille maximale pour une grille de taille n est de longueur 2n-1

supposons maintenant qu'il est possible de rallonger un chemin de telle sorte qu'un autre chemin plus petit disparaisse, on a alors un chemin :

((n+x1+n-xy) + n+x2 + ... + n-x1 + n-x2 + ... + n-xy-1) -> Un chemin de taille 2n+x1-xy et on sait que x1-xy doit etre <= -1 car le plus grand chemin mesure 2n-1. Cela implique que x1 < xy. Cependant l'existence de ce chemin implique l'existence d'un chemin de taille (x1-xy) qui n'existait pas auparavant.

Par conséquent si on créé un nouveau chemin qui en fusionne deux on créé automatiquement un chemin nouveau de taille 1. Donc on conserve n chemins.

C'est à vérifier mais la comme ça ça a l'air de tenir la route.

edit : J'ai trouvé un problème potentiel mais pas encore convaincue que c'est un problème lmao

Qu'entends-tu par "couvrant n+x" ?

Le 19 juin 2022 à 02:04:49 :

Le 19 juin 2022 à 02:01:55 :
n x n grille = n² cases
Pour qu'un ensemble de n chemins couvre tous les sommets il faut que chaque chemin couvre un ensemble de sommet tel que pour chaque chemin couvrant n+x il existe un chemin couvrant n-x sommet, tel que la somme de tous les n+x et n-x soit = n²

Supposons qu'il existe cette formation de n chemins telle que ((n+x1) + (n+x2) ... + (n-x1) + (n-x2) ... ) = n²

Remarquons également qu'un chemin de taille maximale pour une grille de taille n est de longueur 2n-1

supposons maintenant qu'il est possible de rallonger un chemin de telle sorte qu'un autre chemin plus petit disparaisse, on a alors un chemin :

((n+x1+n-xy) + n+x2 + ... + n-x1 + n-x2 + ... + n-xy-1) -> Un chemin de taille 2n+x1-xy et on sait que x1-xy doit etre <= -1 car le plus grand chemin mesure 2n-1. Cela implique que x1 < xy. Cependant l'existence de ce chemin implique l'existence d'un chemin de taille (x1-xy) qui n'existait pas auparavant.

Par conséquent si on créé un nouveau chemin qui en fusionne deux on créé automatiquement un chemin nouveau de taille 1. Donc on conserve n chemins.

C'est à vérifier mais la comme ça ça a l'air de tenir la route.

edit : J'ai trouvé un problème potentiel mais pas encore convaincue que c'est un problème lmao

Qu'entends-tu par "couvrant n+x" ?

Qu'il passe par n+x sommets

Le 19 juin 2022 à 02:03:28 :

Le 19 juin 2022 à 01:57:35 :

Le 19 juin 2022 à 01:38:41 Yusei_Fudo a écrit :
Du coup je pense que le résultat n-1 est impossible, parce que ce sont des carrés et qu'avec cet énoncé, il n'est pas possible de recouvrir un carré entier en un seul chemin, peu importe la valeur de n

Bref, pour mieux l'expliquer, je pense que l'exemple du haut et l'exemple de droite sur le premier screen sont la démonstration "optimisée" du problème créé par ces conditions. En faisant une grille n*n t'as forcément n entrées et n sorties donc n chemins minimums

S'il s'avère que je me trompe, la solution m'intéresse, mais je ne pense pas me tromper

Intéressant comme idée mais par exemple, si on considère que les entrées/sorties qualifient les sommets au bord du carré, alors il est possible de couvrir toute la frontière avec deux chemins seulement : un L et un L inversé. Bien sûr, ça laisse à gérer un carré à l'intérieur n-2 par n-2.

Bref, je n'ai pas l'impression que ton argument suffise tel quel. Mais il n'est pas du tout exclu qu'on puisse le faire marcher en le malaxant convenablement.

Si on a un chemin qui ne fait que longer un bord (autant le faire couvrir intégralement deux côté du bord, alors, j'imagine), alors on se ramène à un carré d'1 plus petit et 1 chemin de moins, donc c'est bon. Si ma parenthèse précédente et correcte, on peut donc supposer qu'aucun chemin n'est inclus dans le bord du carré.

Je suis d'accord qu'aucun chemin n'est inclus dans le bord, pour les raisons que tu donnes.
De là on en déduit que les 4 coins de la grille sont tous des "points de départ" de chemins.
Or il est possible de montrer que si un chemin relie deux coins opposés, donc concrètement qu'il découpe la grille en deux parties, alors forcément le recouvrement compte (au moins) n chemins.
Donc SI une solution avec n-1 chemins existe, elle contient au moins 4 chemins distincts, démarrant aux 4 coins (donc on est sur une grille de taille 5 au minimum) .