Messages de enigmegraphe

Le 26 juin 2022 à 23:44:47 :
Et si ton gosse a des anomalies qui font qu'il va passer une vie terrible après la naissance. Est-ce que tu ne souhaiterais pas abréger ses souffrances le plus tôt possible par exemple en faisant avorter ta femme ?

pourquoi tu feed

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

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