Vous êtes ici : Accueil > Equipes de travail > LaTeX > Un problème d’intersections
Publié : 27 décembre 2009

Un problème d’intersections

Analyse combinatoire et géométrie élémentaire

Nos exercices d’analyse combinatoire comptent bien peu d’exercices d’inspiration géométrique.
Voici un tel exercice, simple mais élégant ainsi que sa représentation à l’aide d’une figure LaTex dont la réalisation est, elle, beaucoup moins simple.

On donne n points sur un cercle (une courbe fermée convexe ou un polygone convexe feraient aussi l’affaire).

  1. On trace tous les segments dont les extrémités sont choisies parmi ces segments. Combien y en a-t-il ?
  2. Si trois quelconques de ces segments ne sont jamais concourrants, quel est le nombre de points d’intersections de ces segments ?

Le nombre de segments, qui est aussi le nombre d’arêtes du graphe complet à n sommets, est C(n,2) [1].
Ensuite, on remarque qu’il existe un jolie bijection entre les points d’intersection de deux des C(n,2) segments et les quadrilatères dont les sommets sont choisis parmi les n points donnés.
En effet, ces quadrilatères sont convexes donc leurs diagonales se coupent en un point qui est dans l’ensemble des points qu’on essaie de dénombrer. Et un tel point est, par définition, l’intersection de deux segments dont les extrémités sont parmi les n points donnés.
Le nombre de points d’intersection des segments est donc C(n,4)

Pour construire la figure tikz-LaTeX correspondante, on passe par les étapes suivantes :

  1. Construire les C(n,2) segments de la figure ce qui est réalisé grâce à deux boucles \foreach emboîtées

    2. .

  2. Générer toutes les combinaisons de n éléments pris 4 à 4.
    Cette étape exige l’élaboration d’un algorithme de construction des combinaisons. A l’heure où on parle de réintroduire l’algorithmique dans les programmes, ce thème pourrait être exploité en Labo Informatique.
  3. Ces combinaisons correspondent chacune à un quadrilatère dont on construit l’intersection des diagonales.
    Tikz se charge de gérer ces intersections et le code joint à cet article ne comporte donc pas de calculs effectifs d’intersection.

On le voit, ceci nécessite une programmation déjà assez élaborée.
Il est intéressant de remarquer que là où le mathématicien se satisfera de ce qu’il y a C(n,4) point d’intersections, l’informaticien, lui devra effectivement générer ces combinaisons, une tâche plus rarement envisagée dans nos cours tant il est vrai qu’on considère que l’analyse combinatoire est l’art de compter sans énumérer ainsi que le professe Yvan Morton Niven dans son excellent ouvrage "Mathematics of Choice, How to Count without Counting" (The Mathematical Association of America, 1964)

\documentclass{article}
\usepackage{tikz}
\usepackage{xifthen}
\usepackage{amsmath}
\usetikzlibrary{arrows,calc,intersections}

% 1) Represent n points on a cercle
% 2) Draw all segments between any two of these points
% 3) Draw all the intersections between any two of these segments
\begin{document}
        \def\r{4}
        %\def\n{4} \def\myangles{{0,65,120,250,320}}
        \def\n{8} \def\myangles{{25,50,85,125,160,220,250,280,340}}
        %\def\n{5} \def\myangles{{0,40,80,150,220,300}}
        %This vector contains the angles determining the position of the points.
        %-----------------------------------------------------------
        % Variables and counters used to generate the 4-combinations
        \newcounter{np} \pgfmathsetcounter{np}{\n+1}
        \newcounter{na} \newcounter{nb} \newcounter{nc}
        \newcounter{ia}
        \pgfmathsetcounter{na}{\n-1}        % saves some computations later
        \pgfmathsetcounter{nb}{\n-2}        % ""
        \pgfmathsetcounter{nc}{\n-3}        %        ""
        \newcounter{q} \setcounter{q}{0}        % if flag q=1 then exit the whiledo loop
        \newcounter{e} \setcounter{e}{0}        % e is a real counter!
        \newcounter{a} \setcounter{a}{0}        % element of the combination
        \newcounter{b} \setcounter{b}{1}        % ""
        \newcounter{c} \setcounter{c}{2}        % ""
        \newcounter{d} \setcounter{d}{2}        % ""
        %Watch out! The initial value {0,1,2,2} is not a 4-combination
        %-----------------------------------------------------------
        On dispose $n$ points sur un cercle.
        \begin{enumerate}
                \item On construit les $\begin{pmatrix}n\\2\end{pmatrix}$ segments joignant deux quelconques de ces sommets (on obtient ainsi le graphe complet sur les $n$ sommets).
                \item Ensuite, on construit les $\begin{pmatrix}n\\4\end{pmatrix}$ points d'intersections de tous ces segments pris deux \`a deux.
        \end{enumerate}
       
        \begin{center}
        \begin{tikzpicture}
                % Draw the complete graph
                \fill[fill=blue!10!green!10!,draw=blue,dotted,thick] (0,0) circle (\r);
                \pgfmathparse{\n-1} \let\nn\pgfmathresult
                \foreach \i in {0,...,\nn}{
                        \pgfmathparse{\i+1} \let\ii\pgfmathresult
                        \pgfmathparse{\myangles[\i]} \let\t\pgfmathresult
                        \foreach \j in {\ii,...,\n}
                                \pgfmathparse{\myangles[\j]} \let\u\pgfmathresult
                                \draw[blue,very thick] ({\r*cos(\t)},{\r*sin(\t)})--({\r*cos(\u)},{\r*sin(\u)});
                        }
                \foreach \i in {0,...,\n}{
                        \pgfmathparse{\myangles[\i]}        \let\t\pgfmathresult
                        \pgfmathsetcounter{ia}{\i+1}
                        \fill[draw=blue,fill=blue!20!,thick]
                                        ({\r*cos(\t)},{\r*sin(\t)})circle (2.5mm) node{$\mathbf{\theia}$};
                        }
                        % Points and segments are now drawn
                        %
                \whiledo{\theq=0}{ % this loop generates the 4-combinations
                        \stepcounter{e}
                        \ifthenelse{\thee=1000}{\setcounter{q}{1}}{}% just to be sure to get out some day...
                        \ifthenelse{\thed=\n}
                                {\ifthenelse{\thec=\thena}
                                        {\ifthenelse{\theb=\thenb}
                                                {\ifthenelse{\thea=\thenc}
                                                        {\setcounter{q}{1}}
                                                        {        \stepcounter{a}
                                                                \pgfmathsetcounter{b}{\thea+1}
                                                                \pgfmathsetcounter{c}{\thea+2}
                                                                \pgfmathsetcounter{d}{\thea+3}                                       
                                                        }
                                                }
                                                {        \stepcounter{b}
                                                        \pgfmathsetcounter{c}{\theb+1}
                                                        \pgfmathsetcounter{d}{\theb+2}                                               
                                                }
                                        }
                                        {        \stepcounter{c}
                                                \pgfmathsetcounter{d}{\thec+1}
                                        }
                                }
                                {\stepcounter{d}}
                        \ifthenelse{\theq=0}{
                                % Construction of the intersection points of the segments
                                \pgfmathparse{\r*cos(\myangles[\thea])} \let\xa\pgfmathresult
                                \pgfmathparse{\r*sin(\myangles[\thea])} \let\ya\pgfmathresult
                                \pgfmathparse{\r*cos(\myangles[\theb])} \let\xb\pgfmathresult
                                \pgfmathparse{\r*sin(\myangles[\theb])} \let\yb\pgfmathresult
                                \pgfmathparse{\r*cos(\myangles[\thec])} \let\xc\pgfmathresult
                                \pgfmathparse{\r*sin(\myangles[\thec])} \let\yc\pgfmathresult
                                \pgfmathparse{\r*cos(\myangles[\thed])} \let\xd\pgfmathresult
                                \pgfmathparse{\r*sin(\myangles[\thed])} \let\yd\pgfmathresult
                                %                               
                                \coordinate  (A) at (\xa,\ya);
                                \coordinate  (B) at (\xb,\yb);
                                \coordinate  (C) at (\xc,\yc);
                                \coordinate  (D) at (\xd,\yd);
                                % Name the coordinates, but do not draw anything!                               
                                \path[name path=sega] (A) -- (C);
                                \path[name path=segb] (B) -- (D);
                                \path [name intersections={of=sega and segb}];
                                \coordinate (X) at (intersection-1);
                                \fill[fill=blue!30,draw=blue] (X) circle (0.6mm);                               
                                %-----------------------------------------------------
                                }{}
                }% End of the whiledo loop
        \end{tikzpicture}
        \end{center}
        \addtocounter{e}{-1}
        nombre de points d'intersection g\'en\'er\'es : \thee
\end{document}

Documents joints

Post-scriptum

La rédaction de cet article a été suscitée par une discussion en salle de profs ; certain(e)s collègues, n’ayant pas la formation de mathématicien(ne), confessant être lassés par les exercices conformes au stéréotype "Combien y a-t-il de numéro de téléphone tels que etc".
Toute proposition d’exercice non stéréotypé sera acceuillie avec enthousiasme par les membres de l’Urem.

Notes

[1] C(n,k) désigne bien sûr le nombre de combinaisons de n éléments pris p à p