Droites et polygones — Les-mathematiques.net The most powerful custom community solution in the world

Droites et polygones

Modifié (9 Jan) dans Combinatoire et Graphes
Bonjour,
Soit $n$ un entier naturel plus grand que $3$. $n$ droites dans le plan en position générale (c'est-à-dire que deux droites ne sont jamais parallèles, ni trois droites concourantes) dessinent des polygones séparés par des segments. Si l'intérieur d'un polygone rencontre une des droites, on ne compte pas ce polygone. Quel est le plus grand entier $k$ (fonction de $n$), tel que pour tout ensemble de $n$ droites en position générale, il existe un polygone (dessiné par les $n$ droites) à $k$ côtés ou plus ?
Autre formulation: on considère $n$ droites dans le plan en position générale. Soit $E$ la réunion de ces $n$ droites. Toute composante connexe bornée de $\R^2 \setminus E$ est un polygone.
Quel est le plus grand $k$ fonction de $n$, tel que pour tout ensemble de $n$ droites, il existe une composante connexe bornée du complémentaire, à $k$ côtés ou plus ?
Merci. 

Réponses

  • Modifié (9 Jan)
    Je n'ai aucune idée de comment le montrer, mais soit $n \in \mathbb{N}^*$, et considérons l'ensemble $D$ des droites réelles tangentes au cercle unité du plan complexe centré à l'origine, en les points $e^{i\tfrac{k\pi}{2n}}$ pour $k$ allant de $0$ à $n$ ([EDIT : ajout pour que ce soit plus clair] donc $D$ est une partie finie de l'ensemble des droites dont l'enveloppe est un quart de cercle). Alors j'ai l'impression que $D$ ne dessine que des triangles et des quadrilatères.
    Donc je dirais que la réponse est $4$.
  • Cette construction donne (ou donnerait) des triangles et des quadrilatères , pour les portions extérieures au cercle, mais on a un polygone à $n$ côtés au centre de la figure.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Non non ! Il n'y a qu'un quart de cercle !
  • Bonjour,
    Voilà la construction de @Georges Abitbol si j'ai bien compris

  • Voilà, c'est ça ! Merci pour l'image, @Calli !
  • Modifié (9 Jan)
    Edit : il y a une erreur.

    Ça montre $k\leqslant 4$, mais il reste à montrer que $k=4$ et non $k=3$ (au moins quand $n>3$).  Considérons le graphe dont les sommets et arêtes sont les sommets et arêtes des polygones étudiés. La formule d'Euler pour les graphes donne $s-a+f=2$ avec $s=\frac{n(n-1)}2$ le nombre de sommet, $a=n(n-2)$ le nombre d'arêtes et $f$ le nombre de faces (en comptant celle non bornée). Donc $f=\frac{n(n-3)}2+2$. Or $\sum_{\rm faces} \deg F=2a$ avec $\deg F$ le nombre d'arêtes adjacentes à la face $F$. Donc si, par l'absurde, il n'y a que des triangles, alors le degré de la face non bornée est $2a-3(f-1) = \frac{n(n+1)}2-3$. Or ceci est $>n$ dès que $n>3$, ce qui est absurde.
  • Attends, c'est quoi, "la" face non bornée ? En fait, tu gommes toutes les demi-droites qui ne sont plus intersectées par les autres droites, c'est ça ? Et tu regardes juste ce graphe-là ?
  • Oui !
  • Modifié (9 Jan)
    Salut
    Je ne comprends pas bien pourquoi le fait que la face non bornée ait un degré $>n$ est absurde.
    Sur le dessin de Cali avec $n=8$, il me semble que la face non bornée a un degré 18 :  sauf erreur, il y 6 triangles, 15 quadrilatères et la formule concernant la somme des degrés est $6\!\times\!3\!+\!15\!\times\!4\!+\!18\!=\!2\times 48$, non ?
    Ou alors j'ai mal compris . . .
  • Modifié (9 Jan)
    Ben si le degré est le nombre de côtés, la face non bornée ne peut pas avoir plus de côtés qu'il y a de droites dans la configuration, puisqu'un côté est contenu dans exactement une droite. EDIT : Et dans le dessin de Calli, la face non bornée a degré exactement $8$. RE-EDIT : Non, mince, voir ci-dessous.
  • Modifié (9 Jan)
    Tu peut, si tu veut, effectivement compter 8 comme degré de la face non bornée, mais dans ce cas tu ne peut plus écrire que la somme des degrés vaut 2 fois le nombre d'arêtes vu que ce que tu as compté comme une unique arrête de la face non bornée se retrouve en face de plusieurs arêtes des faces non bornées et tu ne peut plus affirmer que ce que tu as compté comme "une arrête" est systématiquement commune à 2 faces.
    Et tu peut vérifier que, sur le dessin, si on veut que les deux relations $a\!=\!n(n\!-\!2)$ et $\sum\mbox{deg}=2a$ soient toutes les deux correctes, il n'y a pas le choix concernant le degré qu'on doit attribuer à la face non bornée : c'est 18.

    Sinon, si on ne veut pas s’embêter, pour montrer que, lorsque $n\!\geqslant\!4$, il y a forcément au moins un quadrilatère, on peut vérifier que c'est vrai pour $n\!=\!4$ puis dire que, si on coupe un quadrilatère en deux sans passer par les sommets, alors au moins une des deux coupes est au moins un quadrilatère.
  • Modifié (9 Jan)
    Ah non mince tu as raison, je n'avais pas fait attention ! C'est bien $18$ !
  • En effet ! Merci @Ben314159.
  • Modifié (9 Jan)
    J'ai essayé vite fait de voir ce qui se passait si on prend le graphe avec tout (sans enlever les demi-droites comme Calli) et qu'on rajoute un sommet à l'infini. Le calcul est long et je suis bloqué à un endroit. Mais j'ai l'espoir que ça marche... Je posterai peut-être demain.
  • Merci pour les réponses !
  • On ne peut pas s'en tirer en constatant que deux triangles ne peuvent pas avoir un côté en commun (étant donné que les droites sont en position générale) ?

    Donc si on a un triangle, toute composante connexe bornée qui lui est adjacente (il y en a toujours une pour $n\geq 4$) aurait plus que 3 côtés.

    Bon il faudrait formaliser...
  • Modifié (10 Jan)
    @raoul.S : Ben ouais, c’est une bonne idée ! Soient $A,B,C,D$ des points tels que $ABC$ et $BCD$ sont des triangles. Alors $[AB], [AC], [DB], [DC]$ sont des segments de droite. Comme les points $B$ et $C$ sont simples, $(AB)=(DB)$ et $(AC)=(DC)$. Donc… $B=C$.
  • Modifié (10 Jan)
    Merci @Ben314159 ! Je viens de comprendre.
    Bien vu @raoul.S !
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!