Depuis le 1er avril 2022, ce forum devient accessible uniquement en lecture. (Voir ce message)
Il n'est plus possible de s'y inscrire, de s'y connecter, de poster de nouveaux messages ou d'accéder à la messagerie privée. Vous pouvez demander à supprimer votre compte ici.

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

Pour des échanges de points de vue sur des sujets scientifiques, des nouvelles découvertes, des controverses...
brusicor02
Messages : 506
Inscription : 09/02/2012, 18:09
Niveau d'étude / Domaine : M2 Chimie - magistère PCM d'Orsay
Localisation : Lyon, FRANCE
Remarque : Ancien pseudonyme : RuBisCO
Contact :

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

Message par 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) ?
Image
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$... :demon: Je vous invite à compter par vous même. ;-)

La démonstration, au prochain épisode. :mrblue:
♫ Because you know all about that base, 'bout that base, no acid ! ♫
darrigan
Administrateur
Administrateur
Messages : 2548
Inscription : 16/03/2011, 15:48
Niveau d'étude / Domaine : Docteur en chimie physique
Localisation : Pau (64), France
Contact :

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

Message par darrigan »

Pour $n=6$, j'en compte 31, c'est ça ? (et pas 32) :demon:
Aide-toi et le forum t'aidera ! :mrblue:
brusicor02
Messages : 506
Inscription : 09/02/2012, 18:09
Niveau d'étude / Domaine : M2 Chimie - magistère PCM d'Orsay
Localisation : Lyon, FRANCE
Remarque : Ancien pseudonyme : RuBisCO
Contact :

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

Message par brusicor02 »

Tout à fait ! Pour la démonstration, on aura besoin de ça :
La théorie des graphes a écrit :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.
Image
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. ;-)
♫ Because you know all about that base, 'bout that base, no acid ! ♫
darrigan
Administrateur
Administrateur
Messages : 2548
Inscription : 16/03/2011, 15:48
Niveau d'étude / Domaine : Docteur en chimie physique
Localisation : Pau (64), France
Contact :

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

Message par 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 :
Image (ici on a pris les sommets d'une face pentagonale et on a étiré dans toutes les directions)
Aide-toi et le forum t'aidera ! :mrblue:
brusicor02
Messages : 506
Inscription : 09/02/2012, 18:09
Niveau d'étude / Domaine : M2 Chimie - magistère PCM d'Orsay
Localisation : Lyon, FRANCE
Remarque : Ancien pseudonyme : RuBisCO
Contact :

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

Message par 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 :-D )

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. :joie:).

Image $\; \; \; \; \; \;$ Image
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.
♫ Because you know all about that base, 'bout that base, no acid ! ♫
brusicor02
Messages : 506
Inscription : 09/02/2012, 18:09
Niveau d'étude / Domaine : M2 Chimie - magistère PCM d'Orsay
Localisation : Lyon, FRANCE
Remarque : Ancien pseudonyme : RuBisCO
Contact :

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

Message par brusicor02 »

Bon, il est temps de faire une démonstration ! Vous êtes prêts ? C'est parti !
Image
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$ ? 8-|
La réponse au prochain épisode, mais je vous invite à chercher de votre côté avec l'ami Pascal. ;-)
♫ Because you know all about that base, 'bout that base, no acid ! ♫
alexchimiste
Messages : 829
Inscription : 04/04/2011, 09:48
Niveau d'étude / Domaine : DUT chimie
Localisation : Strasbourg

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

Message par alexchimiste »

Y'a pas à dire, mais les mathématiciens sont vraiment vicieux *retourne à sa colonne* :fete:
brusicor02
Messages : 506
Inscription : 09/02/2012, 18:09
Niveau d'étude / Domaine : M2 Chimie - magistère PCM d'Orsay
Localisation : Lyon, FRANCE
Remarque : Ancien pseudonyme : RuBisCO
Contact :

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

Message par brusicor02 »

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

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.
♫ Because you know all about that base, 'bout that base, no acid ! ♫
Verrouillé