[MATHS] La fausse conjecture de la découpe du cercle

[brusicor02]

Prenez un cercle accompagné de son disque. Disposons $n \in \mathbb{N} \backslash \{0 \}$ points sur ce disque et traçons tous les segments reliant les points deux à deux.

Question : si je découpe selon les segments le disque, combien obtiens-je de morceaux (au maximum) ?

conjecturons les premiers cas...
Comme on en a aucune idée, on a envie de faire les premiers cas afin de conjecturer la solution :

• pour $n=1$, notre cercle reste en 1 seul morceau.
• pour $n=2$, un segment coupe le cercle en 2.
• pour $n=3$, on obtient 4 morceaux : un triangle et trois pièces au bord arrondi.
• pour $n=4$, on obtient 8 morceaux.
• pour $n=5$, on obtient 16 morceaux.

A ce moment-là, je suis sûr que cette liste vous semble familière : 1,2,4,8,16... ce sont les puissances de 2. Alors, avons-nous envie de conclure :

En découpant un disque selon les segments issus de $n$ points du cercle, je peux obtenir $2^{n-1}$ morceaux au maximum.
Et, au moment où vous êtes fier de votre découverte, le matheux va vous demander de faire le cas $n=6$... Je vous invite à compter par vous même.

La démonstration, au prochain épisode.

[darrigan]

Pour $n=6$, j'en compte 31, c'est ça ? (et pas 32)

[brusicor02]

Tout à fait ! Pour la démonstration, on aura besoin de ça :

théorème de la caractéristique d'Euler : tout graphe planaire connexe vérifie la relation : $$ \heartsuit \; \boxed{S-A+F=2} \; \heartsuit$$ avec :

• $S$ le nombre de nœuds du graphe
• $A$ le nombre d'arêtes (ou liens) du graphe
• $F$ le nombre de faces du graphe (en comptant l'extérieur comme une face)

Ajoutons quelques définitions supplémentaires :

• un graphe est connexe lorsqu'il existe un chemin d'arêtes reliant entre eux n'importe quel couple de sommets.
• un graphe est planaire lorsqu'il peut être représenté sur un plan sans que deux arêtes ne se coupent.

un exemple de graphe planaire connexe
On peut vérifier la relation sur l'exemple : $S=11$, $A=14$ et $F=5$ et on a bien $S-A+F=11-14+5=2$.

Si vous voulez réfléchir au problème, je vous laisse encore un peu de temps.

[darrigan]

Je connaissais cette relation pour les polygones et polyèdres, mais je ne savais pas qu'elle était applicable aussi aux graphes planaires connexes.
En y réfléchissant, c'est évident, car par transformation topologique on peut "aplatir" un polyèdre pour le représenter sous forme de graphe.
Un peu comme le fullerène C60, dont une représentation plane serait :
(ici on a pris les sommets d'une face pentagonale et on a étiré dans toutes les directions)

[brusicor02]

En effet, c'est comme cela que Cauchy a démontré la conjecture d'Euler sur les polyèdres et que c'est devenu aujourd'hui un théorème de la théorie des graphes. (puisque, finalement, un polyèdre n'est qu'un exemple de graphe )

Par contre, cela marche sur les polyèdres convexes. Ce que j'ai défini est la caractéristique d'Euler $\chi = S-A+F$ et elle sert énormément en topologie. Car, bien entendu, les mathématiciens adorent étendre leurs jouets à d'autres domaines et à d'autres cas (on ne peut pas leur en vouloir, on fait tous pareil en sciences. ).

$\; \; \; \; \; \;$
un icosidodécaèdre et un petit dodécaèdre étoilé

A gauche, un icosidodécaèdre qui est un polyèdre convexe :

• 20 faces triangulaires et 12 faces pentagonales
• 60 arêtes de même longueur
• 30 sommets de degré 4
  D'où sa caractéristique d'Euler de $\chi = 30-60+32=2$

A droite, un petit dodécaèdre étoilé qui est un polyèdre non-convexe :

• 12 faces en pentagrammes étoilés qui s'interpénètrent
• 30 arêtes de même longueur
• 12 sommets de degré 12
  D'où sa caractéristique d'Euler de $\chi = 12-30+12=-6$

Heureusement, les fullerènes sont des polyèdres convexes, donc ils sont équivalent à des graphes planaires.

[brusicor02]

Bon, il est temps de faire une démonstration ! Vous êtes prêts ? C'est parti !

Représentations du cas $n=6$ à différents stades du raisonnement
Nous avons donc un graphe planaire, mais on ne peut pas utiliser le théorème de Euler-Descartes... puisqu'il n'est pas connexe ! On a des arêtes qui se coupent de partout, c'est pas beau ! Donc, si on veut pouvoir utiliser le joli théorème, il va falloir apporter quelques modifications :

Commençons par dénombrer les segments liant les points : pour les tracer, il suffit de choisir un point parmi les $n$ points initiaux, puis d'en choisir un deuxième. Comme on se fiche de l'ordre du choix des sommets, le nombre d'arêtes est donc : $$\binom{n}{2}=\frac{n !}{2 \, (n-2) !}$$ Mais si on veut obtenir un graphe convexe, il va falloir ajouter des points lorsque ces segments se croisent. Il suffit de remarquer qu'en sélectionnant des quadruplet de points, on obtient un des points cherchés. On va ajouter un certain nombre de points dans le cercle (en rose), et plus précisément : $$\binom{n}{4}=\frac{n !}{24 \, (n-4) !}$$ On en déduit le nombre de sommets du graphe planaire connexe créé : $$ S = n + \binom{n}{4}$$ Mais nous avons bouleversé aussi le nombre d'arêtes : à chaque fois qu'on ajoute un point d'intersection, cela revient à créer 2 arêtes en plus. Vous ne me croyez pas ? Prenez un segment et ajoutons un point sur celui-ci : il séparer le segment initial en deux petits segments. Comme le point est ici défini par l'intersection de deux segments, le point sépare non pas un mais deux segments, d'où l'apparition de 2 arêtes en plus à chaque point d'intersection. Finalement, on a donc dans le disque un certain nombre d'arêtes :$$\binom{n}{2} + 2 \binom{n}{4}$$ Pour obtenir le nombre d'arêtes total, il ne faut pas oublier les $n$ arcs de cercles, ce qui donne : $$A = n + \binom{n}{2}+2 \binom{n}{4}$$ Maintenant que nous avons notre graphe planaire connexe, on va s'empresser d'appliquer Descartes-Euler : $$S -A + F = 2 \\
\Leftrightarrow F=2 -S + A \\
\Leftrightarrow F= 2 - \left [ n+\binom{n}{4} \right ] + \left [ n+\binom{n}{2} + 2 \binom{n}{4} \right ] \\
\Leftrightarrow F=2 + \binom{n}{2} + \binom{n}{4}$$ Mais, désolé pour la face représentant l'extérieur, elle ne fait pas partie de notre problème, la solution $\phi$ pour $n$ points est donc : $$\phi(n) =1+ \binom{n}{2} + \binom{n}{4}$$

Mais je pense que vous devez vous poser une question... pourquoi cette chose ressemblait à une suite de puissance de 2 lorsque $n \leq 5$ ?
La réponse au prochain épisode, mais je vous invite à chercher de votre côté avec l'ami Pascal.

[alexchimiste]

Y'a pas à dire, mais les mathématiciens sont vraiment vicieux *retourne à sa colonne*

[brusicor02]

Ce n'est pas de la faute des matheux, c'est de la faute des maths.

Pour terminer avec cette énigme, il suffit de regarder le triangle de Pascal : $$\begin{matrix}
1 & & & & \\
1 & 1 & & & \\
1 & 2 & 1 & & \\
1 & 3 & 3 & 1 & \\
1 & 4 & 6 & 4 & 1 \\
\cdots & \cdots & \cdots & \cdots &\cdots & \ddots
\end{matrix}$$Le début du triangle de Pascal C'est en fait la liste des coefficients binomiaux $\binom{n}{p}$ où $n\in \mathbb{N}$ augmente lorsqu'on passe à la ligne suivante et où $p\in \mathbb{N}$ augmente lorsqu'on se décale vers la droite. $$\begin{matrix}
& p \rightarrow \\
\begin{matrix}
n\\
\downarrow
\end{matrix} & \begin{matrix}
\binom{0}{0}=1 & & & & \\
\binom{1}{0}=1 & \binom{1}{1}=1 & & & \\
\binom{2}{0}=1 & \binom{2}{1}=2 & \binom{2}{2}=1 & & \\
\binom{3}{0}=1 & \binom{3}{1}=3 & \binom{3}{2}=3 & \binom{3}{3}=1 & \\
\binom{4}{0}=1 & \binom{4}{1}=4 & \binom{4}{2}=6 & \binom{4}{3}=4 & \binom{5}{4}=1 \\
\cdots & \cdots & \cdots & \cdots &\cdots & \ddots
\end{matrix} \end{matrix}$$Le début du triangle de Pascal vu par un mathématicien
Le coefficient binomial $\binom{n}{p}$ est le nombre de possibilités de choisir $p$ objets parmi $n$ (sans ordre). Vous savez tous comment construire le triangle de Pascal : chaque élément est la somme de deux coefficients voisins situés sur la ligne du dessus :$$\binom{n}{p}=\binom{n-1}{p-1}+\binom{n-1}{p}$$On peut donc réécrire la nombre de morceaux dans le cercle ainsi : $$\phi(n)=1+\binom{n}{2}+\binom{n}{4} \\ \Leftrightarrow \phi(n)=1+\binom{n-1}{1}+\binom{n-1}{2}+\binom{n-1}{3}+\binom{n-1}{4}$$ Et, comme l'indique la première colonne du triangle de Pascal :$$\forall n \in \mathbb{N}, \binom{n}{0} = 1$$On peut finalement écrire que : $$\phi(n) = \sum_{p=0}^{4} \binom{n-1}{p}$$Reste à savoir ce que vaut la somme des coefficients binomiaux d'une ligne. Vous vous en doutez, la somme d'une ligne fait :$$\sum_{p=0}^{n} \binom{n}{p} = 2^n$$ Cela se montre facilement si vous utiliser de la fameuse formule du binôme de Newton dans le cas suivant : $$2^n=\left ( 1 + 1 \right ) ^n = \sum_{p=0}^n \binom{n}{p} \; 1^p \times 1^{n-p} = \sum_{p=0}^n \binom{n}{p}$$

Conclusion : on a $\phi(n)=2^{n-1}$ seulement si $0 \leq n-1 \leq 4 \Rightarrow 1 \leq n \leq 5 $. A partir de $n=6$, il manque donc des coefficients binomiaux pour former la puissance de 2.

Remarque : il y a une exception pour $n=10$ où $\phi(10)=256=2^8$, ce qui est la moitié de la ligne du triangle de Pascal correspondante.