[ENIGME 150 QI] Couvrir une GRILLE

Le 19 juin 2022 à 02:07:37 :
Remarque : une autre solution à n chemins : faire des zigzags diagonaux tous dans la même direction.

Oui, il existe ENORMEMENT de solutions à n chemins, c'est super facile d'en trouver.
C'est l'une des raisons qui me font penser que n-1 chemins c'est sûrement pas possible.

Le 19 juin 2022 à 02:07:26 :

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

Je ne comprends déjà pas la phrase :

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²

Tu dis que chaque sommet couvre un ensemble de sommets tel que "une condition qui ne me semble pas faire intervenir cet ensemble de sommets".

Aussi, je ne comprends pas d'où sort précisément ce duo n+x / n-x.

Le 19 juin 2022 à 02:07:26 :

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

Je ne suis pas d'accord sur le fait que l'existence d'un chemin couvrant n+x sommets implique l'existence d'un chemin en couvrant n-x.
Peut-être qu'un chemin couvre n+4 sommets et que deux chemins en couvrent respectivement n-1 et n-3 par exemple.

Le 19 juin 2022 à 02:09:30 :

Le 19 juin 2022 à 02:07:37 :
Remarque : une autre solution à n chemins : faire des zigzags diagonaux tous dans la même direction.

Oui, il existe ENORMEMENT de solutions à n chemins, c'est super facile d'en trouver.
C'est l'une des raisons qui me font penser que n-1 chemins c'est sûrement pas possible.

Ca peut donner envie de regarder du côté des matroïdes. Quand tu as des trucs qui ont une saveur type "toute famille libre et génératrice a un cardinal fixé" et que tu bosses avec des structures combinatoires, ça peut ne pas être hors-sujet. Mais bon, invoquer un mot-clé ne nous dira pas magiquement comment faire interagir harmonieusement la condition individuelle d'être des chemins orientés (orientations incompatibles, grrr) et la condition mutuelle d'évitement.

Aussi :
Admettons qu'il existe une grille de taille n x n recouvrable par n-1 chemins.
Alors c'est également le cas de n'importe quelle grille plus grande (enfin, je veux dire : pour tout m > n , la grille de taille m x m se recouvre avec m-1 chemins).
C'est trivial à démontrer (récurrence immédiate) mais potentiellement utile à avoir en tête.

Le 19 juin 2022 à 02:09:31 :

Le 19 juin 2022 à 02:07:26 :

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

Je ne comprends déjà pas la phrase :

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²

Tu dis que chaque sommet couvre un ensemble de sommets tel que "une condition qui ne me semble pas faire intervenir cet ensemble de sommets".

Aussi, je ne comprends pas d'où sort précisément ce duo n+x / n-x.

Je pars du principe qu'il y a n chemins pour commencer, si c'est le cas alors pour chaque chemin de longueur n+x il existe un chemin de longueur n-x ce qui est évident à voir car tu vas toujours couvrir un total de n² sommets
x peut être = à 0 bien sur

Le 19 juin 2022 à 02:14:18 :

Le 19 juin 2022 à 02:09:31 :

Le 19 juin 2022 à 02:07:26 :

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

Je ne comprends déjà pas la phrase :

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²

Tu dis que chaque sommet couvre un ensemble de sommets tel que "une condition qui ne me semble pas faire intervenir cet ensemble de sommets".

Aussi, je ne comprends pas d'où sort précisément ce duo n+x / n-x.

Je pars du principe qu'il y a n chemins pour commencer, si c'est le cas alors pour chaque chemin de longueur n+x il existe un chemin de longueur n-x ce qui est évident à voir car tu vas toujours couvrir un total de n² sommets
x peut être = à 0 bien sur

http://sketchtoy.com/70769772 ?

Le 19 juin 2022 à 02:10:39 :

Le 19 juin 2022 à 02:07:26 :

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

Je ne suis pas d'accord sur le fait que l'existence d'un chemin couvrant n+x sommets implique l'existence d'un chemin en couvrant n-x.
Peut-être qu'un chemin couvre n+4 sommets et que deux chemins en couvrent respectivement n-1 et n-3 par exemple.

Dans ce cas tu n'as pas n chemins ce qui est ma supposition de base dans la démonstration proposée

Au pire si tu as n+z chemins tu peux réduire à n chemins avec certitude donc inutile à considérer

Le 19 juin 2022 à 02:15:52 :

Le 19 juin 2022 à 02:10:39 :

Le 19 juin 2022 à 02:07:26 :

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

Je ne suis pas d'accord sur le fait que l'existence d'un chemin couvrant n+x sommets implique l'existence d'un chemin en couvrant n-x.
Peut-être qu'un chemin couvre n+4 sommets et que deux chemins en couvrent respectivement n-1 et n-3 par exemple.

Dans ce cas tu n'as pas n chemins ce qui est ma supposition de base dans la démonstration proposée

Au pire si tu as n+z chemins tu peux réduire à n chemins avec certitude donc inutile à considérer

J'ai donné un exemple sur sketchtoy avec la grille 4x4, on a exactement quatre chemins dont un chemin de taille 4+2 et aucun chemin de taille 4-2
http://sketchtoy.com/70769772

Le 19 juin 2022 à 02:15:34 :

Le 19 juin 2022 à 02:14:18 :

Le 19 juin 2022 à 02:09:31 :

Le 19 juin 2022 à 02:07:26 :

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

Je ne comprends déjà pas la phrase :

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²

Tu dis que chaque sommet couvre un ensemble de sommets tel que "une condition qui ne me semble pas faire intervenir cet ensemble de sommets".

Aussi, je ne comprends pas d'où sort précisément ce duo n+x / n-x.

Je pars du principe qu'il y a n chemins pour commencer, si c'est le cas alors pour chaque chemin de longueur n+x il existe un chemin de longueur n-x ce qui est évident à voir car tu vas toujours couvrir un total de n² sommets
x peut être = à 0 bien sur

http://sketchtoy.com/70769772 ?

D'accord, il peut exister plusieurs chemins tel que la somme des sommets manquants = n, je regarde si ça gêne la suite

( le raisonnement repose plutôt sur l'existence d'un chemin plus petit donc à part reformuler je ne sais pas si le raisonnement est gêné )

Le 19 juin 2022 à 02:17:57 :

Le 19 juin 2022 à 02:15:34 :

Le 19 juin 2022 à 02:14:18 :

Le 19 juin 2022 à 02:09:31 :

Le 19 juin 2022 à 02:07:26 :

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

Je ne comprends déjà pas la phrase :

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²

Tu dis que chaque sommet couvre un ensemble de sommets tel que "une condition qui ne me semble pas faire intervenir cet ensemble de sommets".

Aussi, je ne comprends pas d'où sort précisément ce duo n+x / n-x.

Je pars du principe qu'il y a n chemins pour commencer, si c'est le cas alors pour chaque chemin de longueur n+x il existe un chemin de longueur n-x ce qui est évident à voir car tu vas toujours couvrir un total de n² sommets
x peut être = à 0 bien sur

http://sketchtoy.com/70769772 ?

D'accord, il peut exister plusieurs chemins tel que la somme des sommets manquants = n, je regarde si ça gêne la suite

( le raisonnement repose plutôt sur l'existence d'un chemin plus petit donc à part reformuler je ne sais pas si le raisonnement est gêné )

Je comprends pas la suite de ton raisonnement, pour être honnête
J'avais juste compris cette affirmation et elle me semblait fausse

Le 19 juin 2022 à 02:14:13 :
Aussi :
Admettons qu'il existe une grille de taille n x n recouvrable par n-1 chemins.
Alors c'est également le cas de n'importe quelle grille plus grande (enfin, je veux dire : pour tout m > n , la grille de taille m x m se recouvre avec m-1 chemins).
C'est trivial à démontrer (récurrence immédiate) mais potentiellement utile à avoir en tête.

Dans cette veine, si on arrivait à caractériser toutes les solutions à n chemins, ça pourrait servir à démontrer qu'il n'y en a aucune à n-1. Comment ? Tu te places au plus petit n tel qu'il existe une solution à n-1 chemins. Tu regardes ce qu'il se passe dans le carré n-1 par n-1 inférieur gauche. Tes chemins, étant orientés, induisent chacun un chemin dans le sous-carré ! On a donc un recouvrement de ce carré de taille n-1 par n-1 chemins. Si on a un théorème de structure qui permet de les comprendre, on peut alors espérer en déduire que "bah non, en prolongeant ces chemins dehors, on ne peut pas couvrir tout le carré n par n".

Sinon, ce n'est pour l'instant qu'une idée vague mais j'ai l'impression qu'il faut vraiment traiter le problème en se disant qu'on a A chemins Nord-Ouest (type 1) et B chemins Nord-Est (type 2) et qu'il s'agit de montrer que A + B vaut au moins n. Pour ce faire, j'ai envie de dire que si tu go qu'avec des chemins de type 1, c'est mort pour faire moins que n, à cause de mon argument de tout à l'heure. Donc tu vas utiliser quelques chemins de ce type. Si tu es glouton, tu vas utiliser des chemins très longs, genre une grande diagonale. Tu manges alors pas mal de sommets mais tu découpes le plateau en deux, et deux parties assez longues dans la direction Nord-Ouest. Ces parties se couvrent bien avec des chemins de type 1 mais on a vu qu'on ne pouvait pas se limiter à ça. Donc on va devoir utiliser des chemins de type 2, et là, on va se mordre les doigts d'avoir découpé le plateau en plusieurs bouts, perdant ce qu'on croyant gagner au départ.

D'ailleurs, as-tu des solutions avec A+B=n mais ni A ni B égal à 0 ?

En tout cas, je verrais bien un invariant à base de "j'enlève un chemin de type 1 à mon graphe et je regarde quelles sont les paires de sommets qui ne sont plus joignables par un chemin de type 2", un truc comme ça. Ces chemins orientés ont une saveur relativiste aussi.

Bref, je partage mes images mentales foireuses de mi-nuit

Le 19 juin 2022 à 02:21:26 :

Le 19 juin 2022 à 02:17:57 :

Le 19 juin 2022 à 02:15:34 :

Le 19 juin 2022 à 02:14:18 :

Le 19 juin 2022 à 02:09:31 :

Le 19 juin 2022 à 02:07:26 :

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

Je ne comprends déjà pas la phrase :

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²

Tu dis que chaque sommet couvre un ensemble de sommets tel que "une condition qui ne me semble pas faire intervenir cet ensemble de sommets".

Aussi, je ne comprends pas d'où sort précisément ce duo n+x / n-x.

Je pars du principe qu'il y a n chemins pour commencer, si c'est le cas alors pour chaque chemin de longueur n+x il existe un chemin de longueur n-x ce qui est évident à voir car tu vas toujours couvrir un total de n² sommets
x peut être = à 0 bien sur

http://sketchtoy.com/70769772 ?

D'accord, il peut exister plusieurs chemins tel que la somme des sommets manquants = n, je regarde si ça gêne la suite

( le raisonnement repose plutôt sur l'existence d'un chemin plus petit donc à part reformuler je ne sais pas si le raisonnement est gêné )

Je comprends pas la suite de ton raisonnement, pour être honnête
J'avais juste compris cette affirmation et elle me semblait fausse

Elle est fausse

Le coeur du raisonnement c'est ça : "Cependant l'existence de ce chemin implique l'existence d'un chemin de taille (x1-xy) qui n'existait pas auparavant."

Mais avec un ensemble de chemins ça ne semble pas aussi vrai donc j'y réfléchis un peu plus

http://sketchtoy.com/70769782
Pour l'exemple avec A=/= 0 et B=/=0

Le 19 juin 2022 à 02:27:40 :
http://sketchtoy.com/70769782
Pour l'exemple avec A=/= 0 et B=/=0

7 5 3 1
4+3 4+1 4-1 4-3

Mais c'est bon tu m'a déjà donné un contre exemple qui SEMBLE ne pas causer de problème sauf qu'il faut considérer qu'un ensemble de chemin peut exister au lieu d'un chemin unique

Le 19 juin 2022 à 02:31:04 :

Le 19 juin 2022 à 02:27:40 :
http://sketchtoy.com/70769782
Pour l'exemple avec A=/= 0 et B=/=0

7 5 3 1
4+3 4+1 4-1 4-3

Mais c'est bon tu m'a déjà donné un contre exemple qui SEMBLE ne pas causer de problème sauf qu'il faut considérer qu'un ensemble de chemin peut exister au lieu d'un chemin unique

L'ensemble remplit les propriétés suivantes :
Il est de la forme n-x1 + n-x2 ... tel que la la somme des xn = le x de n+x
Ca peut exister dans l'autre sens aussi
Mais au final ce n'est pas essentiel tant qu'il existe un chemin pouvant être fusionné

Je suis.juste plus convaincue que l'existence de chemin ainsi créé implique l'existence d'un nouveau chemin qui n'existait pas avant

Le 19 juin 2022 à 02:27:40 :
http://sketchtoy.com/70769782
Pour l'exemple avec A=/= 0 et B=/=0

En effet.

En fait, il faut un énoncé qui généralise celui de ton topic mais qui se récure bien.

Ne peut-on pas envisager un truc du genre suivant ? Si je me donne un nombre A de chemins mutuellement évitants de type 1, alors le nombre de sommets couverts est au plus une certaine formule f(A). La même fonction f fonctionne avec un nombre B de chemins de type 2. Maintenant, si je prends A chemins mutuellement évitants de type 1 et B chemins mutuellement évitants de type 2, ça couvre évidemment au plus f(A)+f(B). Il y a potentiellement moyen d'avoir une meilleure borne (en ne comptant pas deux fois les sommets visités par un chemin de chaque type). Mais surtout, on ne s'intéresse pas à ça mais à la situation où les chemins sont mutuellement évitants même d'un type à l'autre. Donc étant données nos deux configurations, on s'intéresse à compter le nombre S1 (resp. S2) de sommets couverts par le type 1 (resp. 2) et le nombre T de sommets couverts deux fois.

J'imagine alors que ce qui nous intéresse, ce serait une inégalité reliant S1+S2-T à A+B+T. En effet, S1+S2-T est le nombre de sommets couverts. Et A+B+T est le nombre de chemins si on les force à devenir disjoints (si on les prenait bien initialement disjoints, alors T=0).

Bref, j'essaie d'étendre le problème pour permettre un découplage de certaines interactions, un truc comme ça.

C'est pas abouti, juste je partage mes idées au cas où ça ferait popper quelque chose chez vous.

on suppose qu'il existe une telle grille
on montre qu'alors un des chemins dépasse la taille n
on montre que c'est absurde ?

Au sujet de
"Cependant l'existence de ce chemin implique l'existence d'un chemin de taille (x1-xy) qui n'existait pas auparavant."

Si on fusionne un chemin en n+x1 avec son opposé c'est impossible car on obtient n+x1+n-x1 = 2n > 2n-1

Si on ne le fusionne pas avec son opposé mais avec un chemin plus petit cela signifie qu'un des grands chemins perd son opposé petit ( ou l'un des petits si c'est un ensemble de chemins ) donc cela signifie qu'il est possible de créer un parcours de chemins tel que
L'un des chemins a n+x sommets
Aucun autre chemin n'a n-x sommets ( ou plutôt, aucun autre ENSEMBLE de chemin de taille n-x_n n'a une somme de x_n sommets tel qu'ils sont égaux au x du n-x )
Ce qui signifie qu'on ne parcours pas un total de n² sommets ?
( à démontrer rigoureusement mais je stoppe la pour cette nuit..No thoughts, brain empty )

Pour l'instant, la piste qui me parle le plus consiste à essayer de passer d'un carré de taille n à un carré de taille n+1 en lui rajoutant un L. En gros, si l'optimal est n à taille n mais aussi n à taille n+1, ça veut dire qu'on a une solution à n dans le carré en bas à gauche dont les chemins peuvent légalement se prolonger de façon à couvrir le L tout entier. Il faudrait comprendre pourquoi les solutions ne peuvent pas ainsi se prolonger. Je ne fais que reformuler : on pétrit le problème jusqu'à ce qu'un angle d'attaque se révèle...

Un autre problème intéressant qui se dégage, c'est montrer que l'optimal pour couvrir un carré de taille n+1 privé d'un de ses coins, c'est n. Si on sait montrer ça, ça implique ce que tu cherches. Est-ce que ce problème-ci passe mieux à la récurrence ?

En tout cas, quand on décompose le carré de taille n+1 en un carré de taille n, un de taille 1 (un point quoi) et deux bandes n par 1, le carré de taille 1 ne joue pas un rôle anodin, ce qui m'a amené au problème ci-dessus.