Quand il pleut des cordes dans un cercle

Commençons par une question simple: dans la figure ci-dessous, en combien de régions le cercle est-il découpé ? Je précise qu’on a relié tous les points placés sur le cercle entre eux et que si on prend trois segments au hasard sur cette figure, ils ne sont pas concourants à l’intérieur du cercle (en clair, il y a parfois des zones de quelques pixels de large qu’il ne faut pas oublier de compter). C’est une contrainte importante, qui permet, en quelque sorte, de briser les éventuelles symétries et ainsi d’augmenter le niveau de sadisme de cette question.

Pour ceux qui auraient la flemme de compter (et je les comprends), ils peuvent imprimer ce dessin et colorier une case sur deux (de telle sorte que deux cases adjacentes ne soient pas de la même couleur) afin d’impressionner leur entourage. Pour les courageux qui auraient décidé de relever le défi, je leur souhaite tout simplement bon courage (et leur rappelle qu’il faut toujours compter deux fois, pour être sûr).

Tirons sur la corde

Trêve de plaisanterie,  et posons le problème de manière un peu plus générale. On considère un cercle sur lequel on dispose n points de manière quelconque (avec n \geq 1 bien sûr). On trace toutes les cordes possibles à partir de ces points, c’est-à-dire qu’on relie les n points deux à deux par un segment. On suppose en outre que trois cordes prises au hasard ne sont jamais concourantes (ce qui signifie qu’aucun point dans le cercle n’est l’intersection de trois cordes). En combien de régions a-t-on divisé le cercle ?

Cela ne nous servira pas dans la suite, mais on peut déjà donner le nombre total de cordes. Il y aura autant de cordes qu’il y a de paires de points, c’est-à-dire qu’il y a autant de cordes qu’il y a de parties à 2 éléments dans un ensemble à n éléments. Autrement dit, il y en a \binom{n}{2}=\frac{n(n-1)}{2}.

Avant de vouloir tout de suite le résultat du nombre de parties dans le cercle pour n quelconque (je sais, vous vous impatientez…), commençons par voir ce qu’il se passe pour des petites valeurs de n. Puisque vous êtes fainéants (sinon vous ne seriez pas là à lire ce texte, mais en train de compter les cases de la figure du dessus !), j’ai fait les figures pour vous :

On peut donc dresser le tableau suivant:

\begin{array}{c|c} n & \text{Nombre de r\'egions} \\ \hline  1 & 1 \\  2 & 2 \\  3 & 4 \\  4 & 8 \\  5 & 16 \\ \end{array}

On voit bien le schéma qui se profile, un cercle comportant n points serait donc divisé en 2^{n-1} parties ? Cela voudrait donc dire que la figure initiale (pour laquelle n=9) comporterait 2^{8}=256 régions? Bon, puisque personne n’a compté, on ne sait pas si c’est effectivement le bon résultat ou bien si nous sommes en train de nous tromper violemment.

Quand même, essayons de tracer une figure pour n=6 , juste pour confirmer cette formule 2^{n-1}:

Malheur ! Il n’y a pas 2^{5}=32 régions à l’intérieur du cercle comme on pouvait (voulait) s’y attendre, mais seulement 31 (même en recomptant plusieurs fois, d’où le côté démoniaque de ce problème des cordes !). Il va donc falloir se débrouiller autrement pour trouver la formule donnant le nombre de cases, et mon petit doigt me dit qu’elle n’a rien de trivial… Pour les curieux qui souhaitent chercher la formule par eux-mêmes, ne lisez pas la suite (et accessoirement, préparez le thermos de café, ça risque de vous prendre pas mal de temps).

Euler, à la rescousse

Adoptons un autre point de vue. Chaque configuration (cercle+cordes) peut être vue comme un graphe planaire (c’est-à-dire un graphe dont les arêtes ne se coupent pas entre elles). Compter le nombre de parties en lesquelles le cercle est divisé revient à compter le nombre de faces que possède ce graphe. Par exemple, on a représenté tous les sommets du graphe dans le cas n=4 ci-dessous:

On dispose d’une magnifique formule (due à Euler), qui lie le nombre de faces F, le nombre de sommets S et le nombre d’arêtes A. Plus précisément,

F = A - S + 2

Attention, la face « extérieure » (l’extérieur du cercle) est comptée dans F. Elle ne nous intéresse pas puisqu’on souhaite simplement connaître le nombre de faces dans le cercle, il faut donc la soustraire. Pour n point donnés sur le cercle, le nombre de régions qui divisent l’intérieur du cercle (que l’on notera désormais R(n)) est donc donné par la formule:

R(n) = A - S +1

Il suffit donc de dénombrer le nombre de sommets et d’arêtes pour obtenir la formule tant convoitée.

Il y a deux types de sommets: les n points qui sont sur le cercle, et les points dans le cercle qui sont l’intersection des cordes. Pour compter les « points-intersection », l’astuce consiste à dire que chacun de ces points est associé à un unique ensemble de quatre points du cercle. En effet, puisqu’on a supposé que trois cordes ne sont jamais concourantes, chaque point-intersection n’appartient jamais à plus de deux cordes différentes. On peut donc l’associer aux quatre points du cercle qui définissent ces deux cordes.

Le point-intersection rouge est uniquement déterminé par les quatre points bleus du cercle.

Il y a donc autant de points-intersection qu’il y a de parties à 4 éléments dans un ensemble à n éléments, c’est-à-dire \binom{n}{4}. Le nombre total de sommets est donc S=n+\binom{n}{4}.

Les points-intersection (en rouge) sont au nombre de 15. Au total, il y a donc S=21 sommets sur la figure.

A présent, il reste à déterminer le nombre d’arêtes. Pour cela, nous allons faire un petit tour dans les pâturages de France, car tel le berger qui compte le nombre de pattes puis divise par 4 pour trouver le nombre de moutons, nous allons compter le nombre d’extrémités des arêtes puis diviser par 2. Plus clairement, pour chaque sommet, nous allons compter combien de fois il est extrémité d’un segment, additionner le tout puis diviser le résultat en deux.

  • De chaque sommet situé sur le cercle partent exactement n+1 arêtes (ne pas oublier de compter les portions de cercle qui partent depuis les points !). Puisqu’il y a n points, cela donne n(n+1) extrémités d’arêtes.
  • De chaque point-intersection partent quatre arêtes (toujours parce que trois cordes ne sont jamais concourantes). Ce qui donne 4 \times \binom{n}{4} extrémités d’arêtes supplémentaires.

Au final, le nombre d’arêtes est A= \frac{1}{2} \left(n(n+1) + 4 \times \binom{n}{4} \right) = \frac{n(n+1)}{2} + 2 \times \binom{n}{4}.

Enfin la réponse !

Finissons le boulot maintenant. Le nombre de parties à l’intérieur du cercle est

R(n) = \frac{n(n+1)}{2} + 2 \times\binom{n}{4} - ( n + \binom{n}{4} ) + 1

d’où

R(n) = \binom{n}{4} + \frac{n(n+1)}{2} - n + 1

Ainsi,

R(n) = \binom{n}{4} + \frac{n(n-1)}{2} +1

On peut réécrire plus élégamment cette formule en remarquant successivement que

La (superbe) formule finale est donc:

R(n) = \binom{n-1}{4} + \binom{n-1}{3} + \binom{n-1}{2} + \binom{n-1}{1} + \binom{n-1}{0}

En particulier, pour n = 9,  R(9) = 70 + 56 + 28 + 8 + 1 = 163 ! Non, vous ne rêvez pas, dans la figure initiale, le cercle était coupé en 163 parties. Ca mérite bien une petite musique de victoire (que les fans reconnaîtront).

Mais pourquoi la formule 2^{n-1} marchait quand même pour les premières valeurs de n ?

Réécrivons 2^{n-1} sous la forme (1+1)^{n-1}. Lorsqu’on développe cette formule à l’aide du binôme de Newton, on obtient 2^{n-1} = \binom{n-1}{0} + \binom{n-1}{1} + \cdots + \binom{n-1}{n-1}. Les cinq premiers termes sont notre R(n). Et lorsque n est plus petit ou égal à 5, il n’y a pas plus de cinq termes. C’est bien pour cela que ça commençait à coincer à partir de n=6.

Morale de l’histoire

Car oui, maintenant j’aime donner une morale à chacun de mes articles. J’accuse… Hum, non, c’est pas celle-là. La morale est qu’il faut se méfier avant de généraliser immédiatement une formule qu’on a extrapolée à partir uniquement des premières valeurs d’une suite. Cependant, il est sain (et même encouragé !) de vouloir généraliser et proposer des conjectures. Faire des maths, c’est aussi faire des essais et des erreurs. Aucun théorème n’a jamais été prouvé sans qu’on n’ait pas eu besoin de faire des tests sur des petites valeurs, ou bien un petit schéma pour visualiser la situation. Je conclurais donc par cette citation attribuée au génial Niels Bohr:

Un expert est une personne qui a fait toutes les erreurs possibles dans un domaine spécifique.

P.S: le temps que vous lisiez cet article, j’ai pu colorier la figure du départ. Voilà le résultat:

Ça a de la gueule ! Si j’osais, je dirais qu’avec ce chef-d’œuvre, je pourrais même concurrencer Escher (évitez quand même de regarder cette figure trop longtemps si vous êtes épileptique).

Source: Un excellent article de Richard K. Guy sur la loi forte des petits nombres. Cet article est tellement dense qu’il sera très certainement à la base d’un futur article de ce blog !

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

8 commentaires pour Quand il pleut des cordes dans un cercle

  1. Bruckert dit :

    Quelle est la condition que doit respecter la distribution des points sur le cercle pour qu’il n’y ait pas de triplet de diagonales concourantes ?

    • blogdemaths dit :

      Bonjour, c’est une très bonne question à laquelle je n’ai pas de réponse pour le moment. Je cherche, mais cette caractérisation (si tant est qu’il y ait une caractérisation simple) m’échappe.

      • RB dit :

        Alors ? Avez-vous trouvé ? Cherchez-vous encore ? Si c’est une bonne question, serait-il bon de la soumettre à la communauté des mathématiciens ? Récemment sur le site d’images des mathématiques du CNRS, quelques mathématiciens semblaient à la recherche de problèmes simples auxquels on puisse répondre une fois résolus : « C’est pourtant simple !!! » (cf. http://images.math.cnrs.fr/C-est-pourtant-simple.html)

        • blogdemaths dit :

          Et non, je n’ai pas trouvé… Pourquoi pas ne pas la soumettre à la communauté des mathématiciens en effet ! 😉

  2. Anonyme dit :

    tros clas

  3. Magda dit :

    comment trouve t’on tous ses resulta ( ceu de la repons final ) ?? je suis en 4eme et mon prof nous a demandé de trouvé pour 7,8 et 9 point … j’y arrive pas :0

  4. Francois77R dit :

    C’est quand même super vicieux (astucieux ?) d’utiliser la caractéristique d’Euler, prévue pour les polyèdres convexes, à un graphe planaire, en considérant que l’extérieur du cercle (cet extérieur est infini) est une face de polyèdre, et qu’une arête « arrondie » reste valable (d’ailleurs deux arêtes différentes (dont une arrondie) reliées par les deux mêmes points, étrange comme polyèdre!)
    Ça pose tellement de questions !!! Mais bizarrement, je suis convaincu, et j’adore ces maths là.
    Merci pour ce blog très intéressant !

    • blogdemaths dit :

      Je trouve l’idée d’utiliser la caractéristique d’Euler géniale même… (géniale car cette idée ne vient évidemment pas de moi !)

      Merci et content que ça vous plaise 🙂

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