Cliquez pour afficher

On peut assimiler les différentes régions du plan délimitées par les droites à des points , et on les relie si et seulement si les régions associées ont un bord en commun. On obtient ainsi un graphe non orienté dont on va devoir colorier les sommes avec deux couleurs (allez je choisis mes couleurs préférées : le violet et le bleu ).

Déjà on remarque qu'une condition nécessaire pour que l'on puisse colorier les régions avec deux couleurs est que jamais 3 droites ne se rencontrent en un point, ce qui se traduit dans le graphe par une absence de triangle reliant 3 points.

J'ai l'intime conviction que c'est même une condition suffisante, c'est-à-dire étant donné un graphe non orienté (avec un nombre fini de sommets) et tel que partant d'un sommet on revient à celui-ci en empruntant au moins 4 chemins (cela équivaut à l'absence de triangles) alors il est possible de colorier les sommets du graphes de façon à ne jamais avoir 2 sommets de même couleur reliés directement.

Un tel graphe est bien sûr connexe, j'aimerais pouvoir appliqué un algorithme du type : partant d'un sommet quelconque colorié en violet, on colorie tous les sommets directement reliés à ce dernier avec l'autre couleur et on réitère le procédé pour chaque sommet obtenu. Bon le problème c'est qu'il ne termine pas, et la correction n'est pas assurée Bref je suis encore loin du compte...

Je pars dans la bonne direction ? _{les seules fois où j'ai travaillais sur des graphes c'était aux écrit d'ENS...}

 Cliquez pour afficher

Je comprends pas bien l'énoncé peut-être mais convient non ? (on peut en créer tout pleins des comme ça)

 Cliquez pour afficher

C'est un exemple ça prouve rien

 Cliquez pour afficher

Ah ok, je l'avais pas pris comme ça. On cherchez une CNS en fait ? J'ai regardé ton poste, c'est possible que  trois droites se coupent en un point et que l'énoncé marche

 Cliquez pour afficher

Hum ce que j'ai dis pour la coloration d'un graphe quelconque c'est faux ! Et géométriquement ça se voit bien

En fait là où ça foire (comme pour la configuration des triangles) c'est dès qu'on a un cycle de longueur impaire !

Donc en fait le problème reviendrait à montrer que pour un graphe connexe ne comportant aucun cycle de longueur impaire on peut colorier les sommets avec 2 couleurs de façon à ce que les sommets reliés ne soient pas de la même couleur.

Bon encore faut-il : 1) que ça soit vrai, 2) le démontrer

 Cliquez pour afficher

Non si 3 droites se coupent en un point, les trois régions du plan "autour" de ce point se contigues donc avec 2 couleurs y'en a forcément 2 de la même couleur qui vont se toucher.

Sauf erreur.

 Cliquez pour afficher

 Cliquez pour afficher

J'insinué exactement 3 et j'ai précisé plus loin que ça ne marchait pas plus généralement avec un nombre impair de régions contigues.

Tu es d'accord ?

_{Bon allez j'vais manger pizza}

 Cliquez pour afficher

Ah non mince me suis planté

 Cliquez pour afficher

Ah ok j'avais lu juste les 3 droites (parce que j'en ai tracé 3) et pas un nombre impair de régions.

Mais j'y crois toujours pas, ok pour 3 régions mais pas pour 11 (ici avec un nombre de droite impair (7) mais on aurait pu faire avec un nombre paire aussi) par exemple, voir ici où les trois droites se coupent au point vert.

Bonne ap

 Cliquez pour afficher

Bien bonne cette pizza ^^

Tu m'as mis le doute ! Mais je pense que c'est juste, on s'est juste mal compris (et pour cause je me suis mal exprimé), en fait le nombre de régions contigues ne peut pas être impair, sur ton joli dessin (qui ressemble à la guitare de Van halen ) autour du point vert il y a 6 régions contigues ! Et du point de vue de mon graphe ça veut bien dire qu'on n'a pas de cycle de longueur impair (les points représentent une région et sont reliés si les régions correspondantes sont contigues (j'entends par là qu'elles ont un bord commun)).

On est d'accord ?

 Cliquez pour afficher

Quand on trace une nouvelle droite, il suffit de garder les couleurs au dessus de la droite et d'inverser les couleurs au dessous; deux zones contiguës auront toujours des couleurs différentes.

 Cliquez pour afficher

On a ici une quantité finie de polygones qui sont formés. On considère donc un polygone quelconque. Est-il suffisant de prouver que lorsqu'un côté du polygone (c'est à dire un polygone ayant avec celui-ci un côté en commun) est de couleur différente alors il en est de même pour tous les côtés de ce polygone? Comme le plan n'est formé que par des polygones côtes à côtes, par récurrence on arriverait à la solution.

 Cliquez pour afficher

Comme il s'agit d'un plan on n'a pas que des polygones finis (je ne sais pas comment on appelle ces figures, si elles ont un nom). Mais ça ne change en rien mon raisonnement. J'espère avoir été clair

 Cliquez pour afficher

La solution suggérée n'est pas claire.
Donc, il faut améliorer.
Il est possible de ne pas faire de récurrence.