Canalblog
Editer l'article Suivre ce blog Administration + Créer mon blog
Publicité
Le Blog des mathématiques concrètes.
4 mars 2016

Genèse de la démonstration d'un théorème.

 

 

geometrie10

 

Notre dernier problème, celui des spaghetti, a été l'occasion d'un échange intéressant au sujet des résultats trouvés. Cet échange s'étant fait principalement par mails, nous allons ci-dessous en présenter le déroulement, avec bien sûr l'accord des intervenants.

D'abord l'énoncé du résultat obtenu, le Théorème du Spaghetto:

Théorème: Soit un spaghetto brisé en n morceaux, les points de rupture étant répartis suivant une loi de probabilité uniforme sur toute la longueur du spaghetto. Alors la probabilité que ces n morceaux constituent les cotés d'un n-polygone est:  1-(n/(2ⁿ⁻¹)) 

Historique de l'obtention de ce puissant résultat.

Les deux responsables du blog, Dominique Strazzabosco et Eric Zeltz, après avoir résolu le cas particulier du triangle (n=3), se frottèrent ensuite au cas n=4 et au cas général. Dominique en partant sur un calcul direct de la probabilité en jeu, mais n'ayant pu finaliser le cas général. Eric en partant sur une méthode élémentaire (par un arbre) mais n'arrivant pas au même résultat ((1/2)) obtenu par Strazza dans le cas du quadrilatère. Par contre Eric traita sans difficulté par sa méthode le cas général, avec un résultat qui était confirmé par le résultat obtenu tous les deux pour n=3 ((1/4)) et celui obtenu par lui pour n=4 avec la même démarche que dans le cas général.
Pour trancher, Eric fit appel à deux autres collègues (Stéphane Kirsch et Olivier Bertrand) et leur soumit le problème.


C'est l'échange mail qui en suivit que nous allons maintenant relater:

D'abord le premier apport de Stéphane:

Premier_apport_de_Stephane

qui suscita la réaction et confirmation suivante d'Olivier:

"Stéphane m'a devancé, et m’épargne de rédiger ma solution car je trouve les même résultats, et en faisant exactement comme lui !"

Peu après, Stéphane finalise son travail par l'apport suivant: 

suite_Stephane 

Ce à quoi Eric réagit de la manière suivante: 

"Merci pour ce joli résultat, Stéphane, mais effectivement, tu utilises l'artillerie lourde! Moi j'étais parti tout bêtement à partir d'un arbre, mais je n'avais pas obtenu ton résultat. J'ai du me tromper quelque part. Si ton résultat est juste (et je pense qu'il l'est) l'événement contraire (ne pas pouvoir faire un polygone) aurait pour probabilité n/2^(n-1) ce qui correspondrait à n branches de longueur n-1 et de proba 1/2 pour chaque arête de l'arbre. J'étais pas loin d'avoir cela, mais j'ai dû mal analyser quelque chose quelque part. Je reprendrais cela à tête reposée et quand j'aurai plus de temps."

 

 Olivier donne alors son grain de sel et propose une méthode certes moins technique que celle de Stéphane, mais loin d'être élémentaire. (C'est là-dessus que Strazza avait échoué).

"En tout cas, en passant par l’événement contraire, on est amené, suivant la même méthode que Stéphane, à intégrer la mesure le Lebesgue sur la réunion disjointe des domaines de la forme :{ (x1,...,x(n-1))  / 0<x1<x1<...<xk<x(k+1)-1/2<...<x(n-1)-1/2<1/2}.
La somme de ces intégrales se simplifie en fait très bien avec un binôme de Newton, et j'obtiens au final le même résultat que Stéphane sans passer par des tranches d'hypercube et les nombres eulériens. 
Cela reste cela dit un peu bourrin, et je suis curieux de voir un raisonnement et/ou un calcul plus simple avec un arbre !"
Eric répond à Olivier de la manière suivante:
 "Soit Xi i variant de 1 à n-1 les abscisses croissantes des points de rupture.
Si tous les Xi sont supérieurs à 1/2 (proba 1/2^(n-1)) on ne peut faire le polygone.
Si X1<1/2 (proba 1/2) et les autres Xi>1/2 , Pour i>=2, les Xi sont répartis uniformément sur l'intervalle de longueur 1: [X1;X1+1], Y. Si tous les Xi sont plus grands que X1+ 1/2  (proba 1/2^(n-2), on ne peut faire le polygone. Finalement cette situation a pour proba 1/2*1/2^(n-2)=1/2^(n-1).

 Si X1<1/2 et X2<1/2 (proba 1/2²) et les autres Xi>1/2, Pour i>=3 les Xi sont répartis uniformément sur l'intervalle de longueur 1: [X2;X2+1]. Si tous les Zi  sont sup à X2+1/2 (proba 1/2^(n-3)), on ne peut faire le polygone. 

 Cette situation a encore pour proba (1/2²)*1/2^(n-3)=1/2^(n-1).

 Etc, etc.

 

 On balaye ainsi les n cas possibles où on ne peut faire de polygone, et toujours avec le même résultat de 1/2^(n-1). Donc la proba de ne pouvoir faire un polygone est de n/2^(n-1) et celle de pouvoir en faire un de 1-n/2^(n-1)"
Olivier objecte alors ceci à Eric:
"Ok merci beaucoup !
Mais je ne suis pas très à l'aise avec le principe de supposer les points de rupture ordonnés, tout en donnant des probas de la forme 1/2^k qu'un ensemble de k d'entre eux soit dans un intervalle de longueur 1/2, ce qui suppose que justement ils ne sont plus ordonnés."
Eric prend acte de l'objection d'Olivier mais reste persuadé qu'une solution élémentaire existe à ce problème. Il en propose effectivement une peu après:
"Si on admet que la probabilité que la longueur du premier morceau soit supérieure à 1/2 est de 1/2^(n-1), la répartition des cassures obéissant à une loi uniforme, on est obligé d'admettre qu'il en est de même pour les autres morceaux: pourquoi le résultat-serait-il différent pour les autres morceaux?Or c'est bien le cas puisque pour que le premier morceau soit supérieur à 1/2, cela nécessite que toutes les abscisses des n-1 cassures dépassent 1/2, ce qui à chaque fois a une probabilité de 1/2.D'où le résultat: proba de 1/2^(n-1) pour que l'un quelconque des n morceaux soit >1/2. Donc proba de n/2^(n-1) pour qu'on ne puisse faire un polygone.Où est la faille, cette fois?"
Olivier reconnait la pertinence de l'argument mais ne le valide pas comme pleinement mathématique: Lisons-le:
" Oui, c'est un argument de symétrie qui est parfaitement convainquant, mais j'ai tendance à le ranger dans la catégorie des arguments "à la physicienne" (ce qui n'est pas du tout péjoratif dans mon intention, bien au contraire, je suis pour la simplicité pour répondre correctement à un problème).
J'ai peut-être une vision trop étroite du problème, mais la phrase "on est obligé d'admettre qu'il en est de même pour les autres morceaux" ne constitue pas selon moi une preuve mathématique. Bien sûr, on ne voit pas pourquoi le résultat serait différent pour les autres morceaux, mais je ne vois pas comment étayer cette "vision" par un véritable argument mathématique de symétrie.
De fait, on est soulagé de constater qu'avec un véritable calcul, sans cette hypothèse de symétrie, on trouve bien que le fait d'avoir une loi uniforme sur le (n-1)-uplet des répartitions des brisures, chacune d'entre elle ne suivant  pas une loi uniforme, (c'est bien la le hic !), la loi donnant la longueur du k-ième morceau ne dépende pas de k."
Dans la foulée, Stéphane propose alors une solution qui a le mérite d'être à la fois élémentaire et pleinement satisfaisante pour un mathématicien scrupuleux:
Si on note X1,X2,...,Xn-1 les variables aléatoires représentant les différentes points de cassures se notre spaghetto (n morceaux = n-1 cassures).
Les Xi suivent toutes une loi uniforme sur [0,1] et sont mutuellement indépendantes.
On cherche alors la probabilité d'avoir un morceau de longueur >1/2:
- premier cas: ce morceau est délimité à gauche par 0. La probabilité de ce cas est (1/2)^{n-1} puisque c'est la probabilité que tous les Xk soient >1/2.
- autres cas: ce morceau est délimité à gauche par un Xk. 
    Pour k fixé, la probabilité d'un tel événement est la probabilité que Xk<1/2 et que Xh pour h≠k vérifie Xh appartient à [0,1]\[Xk,Xk+1/2]. Cet ensemble est de mesure 1/2, les Xh sont indépendants, donc la probabilité obtenue est bien (1/2)*(1/2)^{n-2}=(1/2)^{n-1}.
Tous les événements décrits plus haut sont presque disjoints (leur intersection est négligeable à chaque fois, puisque la probabilité qu'un Xk soit nul ou que Xk=Xh pour 
h≠k est nulle). La somme des probabilité obtenues vaut alors n/2^{n-1}. CQFD."
Il ne restait plus qu'à conclure. Voici la conclusion d'Eric:

"La solution de Stéphane met parfaitement au clair l'évidence intuitive que la position du plus gand morceau ne change rien à la donne. Comme quoi il est souvent plus difficile de trouver et mettre au point une solution utilisant un raisonnement élémentaire qu'une solution technique mathématiquement (du moins quand on maitrise cette technicité mathématique). 

Mais la beauté d'une démonstration est à mon avis (c'est très subjectif) obtenue quand elle utilise un minimum de techniques pour un maximum de résultat"

 

PS: Alors que nous réfléchissions à une autre démonstration fondée sur des considérations géométriques, nous avons appris après coup que l'énoncé et la démonstration de ce résultat existaient déjà.

Voir spaguetto_gomez__2_, article paru en 2006.

La démonstration est géométrique et ressemble assez à celle que nous étions en train de mijoter.

Par contre, il nous paraît abusif d'admettre sans autre forme de procès concernant les variables aléatoires en jeu que la proba recherchée est le rapport des mesures des domaines géométriques concernés. C'est ce que pourtant font les auteurs de l'article cité quand ils affirment ceci:

"It is clear that P(n) = µ(Υn)/µ(∆n), where µ is any (n − 1)-dimensional Euclidean measure on the subsets of ∆n."

A notre sens, il faut le justifier, et c'est ce qui d'ailleurs manque encore actuellement à notre démonstration en construction pour que nous puissions vous la présenter.

 

 

 

Publicité
Publicité
Commentaires
O
je voulais dire bien sûr " qu'exactement un morceau soit de longueur supérieur à d"
Répondre
O
Un morceau étant fixé, sa proba qu'il soit de longueur supérieure à d est effectivement (1-d)^{n-1}, qu'on l'obtienne avec le raisonnement de Stéphane ou bien par intégration de la densité (n-1)(1-x)^{n-2}. Ce résultat est vrai quel que soit d.<br /> <br /> <br /> <br /> Par contre, pour la proba qu'au moins un morceau soit de longueur supérieure à d, ou encore qu'exactement un morceau soit de longueur d, c'est effectivement a priori beaucoup plus compliqué pour d d" ne sont plus incompatibles.
Répondre
M
C'est en relisant la démonstration de Stéphane que je me suis posé la question: <br /> <br /> J'avais l'impression qu'elle ne s'adaptait pas à une longueur d quelconque, En fait si: <br /> <br /> <br /> <br /> Quelle est la proba qu'au moins un intervalle soit de longueur supérieure à d? <br /> <br /> <br /> <br /> Avec les notations de Stéphane: <br /> <br /> <br /> <br /> ce morceau est délimité à gauche par un Xk. <br /> <br /> Pour k fixé, la probabilité d'un tel événement est la probabilité que Xk<1-d et que Xh pour h≠k vérifie Xh appartient à [0,1]\[Xk,Xk+d]. Cet ensemble est de mesure 1-d, les Xh sont indépendants, donc la probabilité obtenue est bien (1-d)*(1-d)^{n-2}=(1-d)^{n-1}.<br /> <br /> <br /> <br /> Et ce que tu dis le confirme d'une autre manière.<br /> <br /> <br /> <br /> Par contre, si d<1/2, on n'a peut-être pas unicité de tels morceaux de longueur d.<br /> <br /> Donc dans ce cas, la proba d'avoir un seul morceau de longueur supérieure à d n'est pas donné par le résultat précédent.
Répondre
O
Je ne suis pas sûr que cela réponde à ta question, mais comme dit précédemment, la loi de proba de la longueur d'un morceau est la même pour tous les morceaux, et donc la proba qu'un morceau soit de longueur supérieure à d quelconque ne dépend pas du morceau. Est-ce que tu veux dire par "l'ordre des brisures ne modifie pas la proba" ?
Répondre
M
Bon, j'abdique.<br /> <br /> Au moins cette tentative m'a permis de revoir certaines notions sur les va continues et leurs calculs que je n'avais pas revues depuis une éternité. Et de me méfier de l'intuition sur de tels problèmes.<br /> <br /> Merci à tous les deux.<br /> <br /> Et maintenant, je pense qu'il est très difficile de faire plus simple que la belle solution finale donnée par Stéphane.<br /> <br /> <br /> <br /> En même temps d'autres questions se sont fait jour. Par exemple celle-ci:<br /> <br /> <br /> <br /> On a vu qu'un changement d'ordre des brisures ne modifie pas la proba quand une des brisures a une longueur supérieure à 1/2 (pour un spaghetto de longueur 1).<br /> <br /> Est-ce que cela reste vrai pour une autre valeur que 1/2 ou cette invariance est-elle spécifique à ce cas?<br /> <br /> <br /> <br /> Mais bon, j'ai plus que largement assez abusé de votre aide et de votre temps, Stéphane et Olivier, ce problème viendra peut-être un jour à partir d'un autre de nos sujets.<br /> <br /> <br /> <br /> Merci encore.<br /> <br /> <br /> <br /> eric
Répondre
Le Blog des mathématiques concrètes.
  • Les mathématiques, cela sert à quoi ? Ce blog propose des problèmes concrets que les mathématiques permettent de résoudre. Il aborde aussi des questions plus générales, parfois philosophiques, mais toujours en rapport avec les mathématiques.
  • Accueil du blog
  • Créer un blog avec CanalBlog
Publicité
Archives
Newsletter
Publicité