Découpons le plan

On s’intéresse au problème suivant: on trace (au hasard) n droites dans le plan. On suppose seulement que deux droites quelconques ne sont jamais parallèles entre elles, et que trois droites quelconques ne sont jamais concourantes.

La question est: en combien de régions ces n droites découpent-elles le plan ?

Quelques exemples

Si vous suivez ce blog régulièrement, vous savez que je suis fan de l’expérimentation sur des petites valeurs lorsqu’on s’intéresse à un problème. Traçons successivement une, deux, trois puis quatre droites dans le plan et voyons combien de régions apparaissent à chaque fois.

Et nous pourrions continuer comme ceci indéfiniment… Mais nous n’avons pas le temps. Nous allons plutôt essayer de trouver une formule générale pour n droites. Voyons voir si nous pouvous deviner un motif à partir des premières valeurs de n.

\begin{array}{c|c} n & \text{Nb de regions} \\ \hline 0 & 1 \\ 1 & 2 \\ 2 & 4 \\ 3 & 7 \\ 4 & 11 \\ 5 & 16 \end{array}

Rien ne saute aux yeux a priori… Il va donc falloir pousser les investigations.

Pelle à tartes et tronçonneuse

Nous allons dénombrer le nombres de régions par récurrence. Dans la suite, nous noterons u_n le nombre de parties du plan découpées par n droites.

On se donne un entier naturel n quelconque. On suppose connu le nombre u_n. En d’autres termes, nous avons placés n droites dans le plan, notées (d_1), (d_2), ... , (d_n). Pour trouver u_{n+1}, on trace une (n+1)-ème droite dans le plan, qu’on notera (d) (en respectant la consigne de départ, à savoir qu’elle n’est parallèle à aucune des autres droites et qu’elle ne passe par aucune intersection de deux droites déjà tracées).

La droite (d) va couper chacune des n premières droites. Quitte à renommer les droites, son parcours sera le suivant:

  • (d) traverse une région;
  • (d) coupe (d_1);
  • (d) traverse une région;
  • (d) coupe (d_2);
  • (d) coupe (d_n);
  • (d) traverse une région.

Combien de régions a-t-elle traversé ? Eh bien, d’après la description ci-dessus, (d) traverse une région avant de couper une droite, puis termine par une région. Puisqu’il y a n droites, cela nous donne n+1 régions traversées. Ce qui va nous donner 2(n+1) régions, puisque chaque fois que (d) traverse une région, elle va couper celle-ci en deux.

Il reste à savoir combien de régions n’ont pas été traversées et sont laissées intactes. Il suffit de faire une petite soustraction: « Nombre de régions de départ moins nombre de régions traversées ». Ce qui donne u_n - (n+1).

Au final, lorsqu’on a placé n+1 droites, le nombre de régions crées est:

u_{n+1} = 2(n+1) + (u_n - (n+1))

C’est-à-dire:

u_{n+1} = u_n + n+1

Taille-moi les hanches, à la hache

Il s’agit donc à présent de donner une expression de u_n en fonction de n. La relation précédente induit:

\forall k \geq 0, u_{k+1}-u_k= k+1

Ca sent donc bon la somme téléscopique. Allons-y, et sommons donc cette égalité de 0 à n:

\sum_{k=0}^n (u_{n+1}-u_n) = \sum_{k=0}^n (k+1)

La somme de gauche n’est rien d’autre que u_{n+1} - u_0 (rappelons que u_0=1). La somme de droite, quant à elle, vaut \sum_{k=0}^n (k+1) = ( \sum_{k=0}^n k) + (n +1)= \frac{n(n+1)}{2} + n+1.

On a donc

u_{n+1} - 1= \frac{n(n+1)}{2} + n+1

D’où, en réindexant, nous obtenons la formule:

u_{n}=\frac{n(n-1)}{2} + n + 1 = \binom{n}{2} + \binom{n}{1} + \binom{n}{0}

Nous avions déjà vu une formule très similaire dans un problème tout aussi proche dans un précédent article de ce blog (que je vous invite à aller lire si vous ne l’avez pas encore fait!). Il s’agissait de compter le nombre de régions dans un cercle découpé par les cordes définies par la donnée de n points sur le cercle. Nous avions à l’époque utilisé une formule d’Euler pour répondre au problème posé.

Une autre preuve…

La démonstration suivie à l’époque est parfaitement adaptable dans le cas qui nous intéresse ici. Nous irons rapidement sur certains arguments déjà détaillés dans l’article précédemment cité.

On se donne  n droites dans le plan. On assimile cela à un graphe planaire dont les sommets sont les intersections des droites. Le nombre F de faces (donc le nombre u_n de régions du plan) est donné par la (très belle) formule d’Euler:

F = A - S + 2

où A est le nombre d’arêtes et S le nombre de sommets.

Chaque configuration peut être vue comme un graphe, dont les sommets sont les intersections des droites. Dans le cas de 4 droites, il y a 6 sommets (+1 sommet dit à l'infini) et 16 arêtes.

Chaque droite coupe les (n-1) autres donc elle contient (n-1) sommets. Ainsi, sur chaque droite, nous avons le schéma suivant:  arête – sommet – arête – sommet – …. – arête (l’argument est similaire à celui utilisé lorsque la droite (d) traversait le plan). Cela donne (n-1) + 1 = n arêtes sur chaque droite. Puisqu’il y a n droites, cela donne A= n^2 arêtes.

D’autre part, il y a autant de sommets qu’il y a de paires de droites, c’est-à-dire \binom{n}{2}= \frac{n(n-1)}{2}. Mais, afin de prendre en compte les régions « extérieures », et pour que les arêtes extrêmes aient bien chacune deux extrémités, nous allons introduire un point à l’infini (appelé aussi « point de colle »), point qui est rejoint par toutes les arêtes les plus extrêmes. Notre figure peut donc être vue aussi comme le patron d’un polyèdre (irrégulier, cela va de soi). Cela nous donne donc S = \frac{n(n-1)}{2} + 1 sommets au total.

La formule d’Euler donne:

F = n^2 - (\frac{n(n-1)}{2}+1) + 2= \frac{2n^2 - n(n-1) }{2} + 1= \frac{n^2 + n}{2} + 1= \frac{n^2-n}{2} + n + 1

Le nombre de régions vaut donc bien u_n = \frac{n(n-1)}{2} + n + 1.

Je ne sais pas pour vous, mais moi, ça me la coupe (la région).

A voir aussi…

Pour une autre approche (que nous qualifierons de plus anglo-saxonne…) de ce problème (et de sa résolution), vous pouvez consulter cette page (en anglais).

Pour le cas plus général où les droites peuvent être parallèles ou concourantes, consultez ce très intéressant article du blog de Pierre Lecomte.

Advertisements
Cet article, publié dans Dénombrement, Géométrie, est tagué , , , , . Ajoutez ce permalien à vos favoris.

3 commentaires pour Découpons le plan

  1. En fait, il n’est pas bien difficile de régler le cas de n droites qui ne vérifient pas nécessairement vos hypothèses. J’en ai dit un mot sur mon blog à l’adresse suivante : http://pierrelecomte.wordpress.com/2010/05/24/regions-determinees-par-des-droites-dun-plan/
    Voir également :
    http://pierrelecomte.wordpress.com/2010/05/26/regions-determinees-par-des-droites-d%e2%80%99un-plan-ii-les-tangentes-a-une-courbe/

    Cordialement,

    Pierre Lecomte

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s