04 juillet 2009
La nuit des courbes monstres
Courbe de Hilbert (7 itérations)
Nous nous étions arrêtés la semaine dernière aux monstres du peuple des courbes, à savoir les courbes continues mais dérivables nulle part (Courbe de Weierstrass, de Bolzano, du blanc-manger, de Koch...). Mais ces courbes restent des monstres gentils, face aux démons réveillés par Peano. Il est temps de passer du côté obscur, avec les courbes de Peano-Hilbert, qui parviennent à visiter chaque point d'un carré unité.
La courbe de Peano (1890)
Courbe de Peano (4 itérations)
L'histoire se déroule à la fin du XIXe siècle, où Cantor étudie l'infini. De ses travaux découlent différents type d'infini : le dénombrable et le continu (et le reste). D'un côté, il y a les ensembles dénombrables, qui ont "autant" d'élément qu'il y a d'entiers dans ℕ. De l'autre, les ensembles continus, qui ont "autant" d'éléments qu'il y a des réels dans ℝ.
Un ensemble de nombres (pourvu qu'il ne soit pas trop compliqué) est soit fini, soit dénombrable, soit continu. Par exemple, l'ensemble des nombres pairs est dénombrable : il y a autant d'entiers pairs que d'entiers (en doublant un entier, on trouve toujours un entier pair, et vice-versa). De même, en étirant un segment de longueur 1 ([0,1]), on peut obtenir un segment de longueur 2 ([0,2]) : il y a "autant" d'éléments dans [0,1] que dans [0,2]. En poussant un peu, on peut voir qu'il y a autant de nombres dans [0,1] que dans ℝ.
Cantor fini par démontrer (en 1877) qu'il y a "autant" d'éléments dans [0,1] que dans [0,1]×[0,1]. Dit autrement, il y a "autant" d'élément dans le côté d'un carré que dans le carré ! Lui-même n'arrive pas à croire ce qu'il vient de démontrer !
Pour s'en convaincre, il faudrait construire une courbe (le déformé d'un segment, dont autant de point que dans [0,1]) qui recouvre entièrement un carré. On montrerait alors qu'il y a le même nombre de points dans un carré et dans son côté.
Quand on cherche, on trouve ! En 1890, c'est Peano qui a eu le privilège de donner le premier exemple d'une telle courbe, qui seront appelés courbes de Peano-Hilbert.
La courbe est donnée par la fonction suivante :
où (t1t2t3...)3 est la décomposition de x∈[0,1] en base 3 (tk∈{0,1,2})
et k(0)=2, k(1)=1 et k(2)=0
J'admets, cette formulation est complètement tordue, mais je la trouvais au moins aussi jolie que la courbe qu'elle engendre !
En fait, on construit dans la pratique la courbe de Peano plutôt comme la limite d'une suite de courbes :
4 premières étapes de la construction de la courbe de Peano
Pour construire cette courbe, on part d'un carré que l'on divise en 9 régions (3×3). On numérote alors ces régions en suivant le chemin en N de la première étape illustré ci-dessus. En reliant les centres des cases, on trouve la première étape de la courbe de Peano.
Pour obtenir la deuxième étape, on part de la grille de 9 régions déjà dessinée, et on découpe chacune d'entre elles en 9 cases (on obtient une grille vierge de sudoku). Pour chaque région, on numérote les cases de 1 à 9 en suivant le motif en N (ou son symétrique par un axe vertical), de façon à ce que le 9 d'une région touche le 1 de la suivante. Pour chaque région, on relie de 1 à 9 le centre des cases : on obtient l'étape 2 de la construction de la courbe de Peano.
On réitère ce principe pour obtenir les étapes suivantes de la construction.
De façon générale, on peut obtenir de nombreuses courbes de Peano-Hilbert par ce procédé. En découpant à chaque étape les carrés en 4, on peut par exemple obtenir la courbe de Hilbert, la courbe de Lebesgue ou la courbe de Moore (De telles courbes sont appellées courbes de Peano-Hilbert binaire).
La courbe de Peano est une fonction P(x)=(x(t),y(t)). On peut alors remarquer que les deux fonctions x(t) et y(t) sont continues partout et dérivables nulle part ! Tout concorde !
Graphe de la première composante de la fonction de Peano : continue partout, dérivable nulle part
La courbe de Hilbert (1891)
Courbe de Hilbert (7 itérations)
L'année suivante, Hilbert donne un autre exemple de courbe remplissante, donnant à ce type de courbe le nom de courbe de Peano-Hilbert. Elle se construit sur le même principe que la courbe précédente.
6 premières étapes de la construction de la courbe de Hilbert
Grâce à un langage comme Logo (Mon tout premier langage de programmation, découvert en CM1 !) et le L-système, on peut construire facilement ce type de courbe.
Le L-système est une façon de décrire ce type de courbe de manière algorithmique. Pour cela, il suffit simplement de définir des règles de remplacement. Pour la courbe de Hilbert, elles sont :
"L" ↦ "+RF-LFL-FR+"
"R" ↦ "-LF+RFR+FL-"
A l'étape 0, on commence par "L" (l'axiome). Chaque étape consiste alors à remplacer les L et R par l'expression correspondant.
Etape 0 : "L"
Etape 1 : "+RF-LFL-FR+"
Etape 2 : "+-LF+RFR+FL-F-+RF-LFL-FR+F+RF-LFL-FR+-F-LF+RFR+FL-+"
Pour dessiner la n-ième étape de la construction de la courbe de Hilbert, on commence par calculer l'expression de l'étape n. On enlève ensuite les L et R qui deviennent inutiles, puis on dessine la courbe en convenant que :
+ signifie tourner à gauche
- signifie tourner à droite
F signifie avancer d'une unité
Par exemple, l'algorithme de l'étape 1 est : "+F-F-F+", c'est à dire :
gauche - avancer - droite - avancer - droite - avancer - gauche
La courbe de Peano peut se représenter de la même façon, avec pour axiome X et les deux règles de remplacement :
"X" ↦ "XFYFX+F+YFXFY-F-XFYFX"
"Y" ↦ "YFXFY-F-XFYFX+F+YFXFY"
La courbe de Lebesgue (1904)
Courbe de Lebesgue (4 itérations)
Cette courbe se construit sur le même principe que les deux précédente (c'est une courbe de Peano-Hilbert binaire), en découpant le carré unité en N, puis en reportant exactement le même motif dans chaque sous-case.
Reliez les points
Contrairement aux courbes de Peano et deux Hilbert, cette courbe est un peu moins monstrueuse. En effet, elle est dérivable presque partout !
Toutes ces courbes (à priori, de dimension 1) ont la particularité d'être de dimension 2 (de Hausdorff) !
Les autres
Terminons cet article avec quelques autres jolies courbes de la famille Peano-Hilbert:
La courbe de Moore (7 itérations)
C'est simplement 4 courbes de Hilbert recollées
La courbe de Sierpiński
Sources :
Courbes remplissante sur Mathcurves.com (D'où proviennent la courbe de Lebesgue et de Sierpiński)
Continuous Nowhere Differentiable Functions - Thèse de Johan This
28 juin 2009
Les courbes monstres
Elles sont apparues au XIXe siècle, et ont été loin de laisser indifférent : Poincaré les a qualifiées de "monstres" et Hermite de "plaies lamentables". On les appelle plus affectueusement "pathologiques"... Mettons-les pour une fois à l'honneur !
Une courbe continue : une courbe que l'on peut tracer sans lever le crayon.
Si le mouvement de la main est soyeux et délicat (le crayon ne s'arrête pas, ne trace pas d'angles), on dit que la courbe est dérivable (enfin, on dit plutôt que la fonction est différentiable, mais on est pas à cette approximation près...).
Les courbes les plus simples que l'on imagine sont continues et dérivables, mais il arrive, même dans la vie d'un lycéen, que la courbe de la fonction ne soit plus dérivable en un point précis. La courbe y est alors anguleuse, et n'y admet pas de tangente. L'exemple le plus simple est le graphe de la fonction valeur absolue :
Graphe de la fonction f(x)=|x|
Fonction continue et dérivable sauf en 0
Cette fonction a le mérite d'être continue (la courbe peut sans problème être tracé sans lever le crayon), mais n'est pas dérivable en 0 (la courbe y est anguleuse, le mouvement de la main pour tracer la fonction ne sera pas velouteux). Heureusement, partout ailleurs, la courbe est bien dérivable (On dit qu'elle est dérivable presque partout)
On peut alors facilement s'imaginer des courbes continues qui ne sont pas dérivables partout : on appelle ça des zig-zag !
Graphe d'une fonction zigzag
Fonction continue mais non dérivable en -1, 0, 1, 2 et 3
Cette fonction reste tout de même dérivable presque partout : il n'y a que 6 points où elle ne l'est pas (les points anguleux), ce qui est négligeable vu le nombre de points où elle l'est. On peut même imaginer une fonction continue mais non dérivable en une infinité de points (un zig-zag infini), mais l'ensemble des points où la fonction n'est pas dérivable reste négligeable !
Ce genre de choses était déjà bien connu à la fin du XVIIIe siècle (où les problèmes étaient généralement de trouver la dérivée d'une fonction donnée), et on s'est rapidement dit que toutes les courbes continues devaient n'avoir qu'un nombre négligeable de points anguleux. Une courbe partout continue et nulle part dérivable : inimaginable !
André-Marie Ampère (celui qui a donné son nom à l'unité électrique) a même tenté de démontrer en 1804 que toute courbe ne devait avoir qu'un nombre négligeable de points de non-dérivabilité. Aujourd'hui, on a toujours du mal à comprendre ce qu'il a voulu prouver, et de toutes façons, il avait tord !
La courbe de Bolzano
La toute première courbe partout continue et nulle part dérivable (On va appeler ça une courbe ND) est l'œuvre du mathématicien tchèque Bernard Bolzano, découverte en 1830. Il faudra tout de même attendre 1930 avant qu'elle ne soit publiée. Par sa construction, on peut l'identifier comme étant la première fractale de l'histoire ! Elle ressemble à ceci :
Courbe de Bolzano
(Continue partout, dérivable nulle part)
Pour la construire, on part de deux points A(0,0) et B(1,1). (On a le segment B0=[AB]). Pour obtenir B1, on construit les trois nouveaux points suivants : C(3/8,5/8), D(1/2,1/2) et E(7/8,9/8). La courbe B1 est le zigzag ACDEB. Pour passer à B2, il faut reprendre chaque segment composant B1, et les transformer en zigzag selon l'opération décrite à l'étape précédente. En itérant ce processus une infinité de fois, on obtient la courbe de Bolzano. Les trois premières étapes sont représentées ci-dessous :
En pointillé, B0 ; en bleu B1 ; en rouge B2
Cette courbe est ND : elle est continue (ce ne sont que des bouts de segments), mais dérivable nulle part (tout point est un angle)
Les courbes de Weierstrass
La star des courbes ND, c'est bien celle-ci ! Le 18 juillet 1872, le mathématicien Karl Weierstrass présente devant une foule médusée non pas une, toute une famille entière de fonctions continues dérivables nulle part ! Il en existait bien deux autres alors, mais n'étaient pas publiées (celle de Bolzano et celle de Cellérier, qui est un cas particulier de celle de Weierstrass).
Les courbes de Weierstrass sont données par la formule suivante :
Pour 0<a<1 et b impair donnés tels que ab>5,72 (On a prouvé bien plus tard que ab>1 suffit)
Prenons par exemple a=1/3 et b=5. On a alors :
W(x) = cos(πx) + cos(5πx)/3 + cos(25πx)/9 + ...
Autrement dit, une somme de fonctions cosinus (toutes aussi continues et dérivables les unes que les autres, mais de plus en plus sinueuses et tassées), ce qui donne :
Fonction de Weierstrass
En gris les sinusoïdes à sommer pour obtenir la fonction
Bref : dérivable + dérivable + dérivable +... = non dérivable !
La courbe du blanc-manger
Une petite dernière, datant de 1903 : la courbe de Tagaki, alias courbe du blanc-manger (parce qu'elle ressemblerait au blanc-manger, un pouding au lait d'amande. On y ajoute de la noix de coco, de l'abricot ou des fruits rouges, selon les préférences culinaires).
Elle est bâtie sur le même principe que la courbe de Weierstrass : une somme de fonctions de plus en plus oscillantes (mais non dérivables pour cette fois). Sa formule est la suivante :
Elle consiste donc en la somme de fonctions en montagnes. En rouge, pour k=1, en jaune, pour k=2 etc.
Courbes à sommer pour obtenir la courbe de blanc-manger :
La courbe de Tagaki
L'année suivante, Koch construisait son célèbre flocon, lui aussi continu partout et dérivable nulle part... On a dernièrement découvert une famille de fonctions à base de produits infinis (Les fonctions de Wen, en 2002) !
Fonction de Wen
Continuous Nowhere Differentiable Functions - Thèse de Johan This
Recette du blanc-manger
21 juin 2009
La sphère cornue
La sphère à cornes, sculpture de Jean-Louis Lhermitte, dans la cour du Centre de mathématiques et d’informatique
Prenez un crayon, une feuille de papier et dessinez-y une courbe revenant à son point de départ sans lever le crayon, ni passer deux fois sur le même point :
Vous obtenez quelque chose comme ça.
Voilà, vous venez de délimiter le plan en deux parties : l'intérieur et l'extérieur ! Si vous coupiz la feuille le long de la courbe tracée, vous devrez obtenir deux bouts de papiers ! (On appelle ça une "composante connexe"). Jusqu'à là, c'est évident !...
Mais comment le démontrer ? Les adeptes du "ça se voit sur le dessin" (comme Kant) s'en contenteront et passeront à autre chose, les autres (comme Bolzano) déprimeront de ne pas trouver de démonstration. En effet, malgré sa simplicité apparente, la démonstration du théorème de Jordan (Puisque quasi démontré par le français Camille Jordan) est vraiment difficile !
Le théorème de Jordan
Ce que vous venez de dessiner est appelé "courbe de Jordan" (ou lacet simple), c'est-à-dire, une courbe (continue) fermée et simple (sans points double). L'énoncé du théorème de Jordan est le suivant :
Une courbe de Jordan délimite toujours le plan en deux composantes connexes : l'intérieur (qui est borné) et l'extérieur (qui ne l'est pas). Ces deux composantes ont pour frontière la dite courbe.
On peut voir une courbe de Jordan avec l'œil d'un topologue, c'est-à-dire, voir la courbe comme étant un cercle déformé. Notre cercle est un élastique : on peut l'étirer, le plier, mais interdiction de le couper ou de l'écraser. On a même le droit de l'étirer infiniment, du moment qu'on ne le coupe pas.
Lorsque l'on peut passer d'un objet à un autre simplement par déformation, on dit que ces deux objets sont homéomorphes ("de même forme"). Par exemple, un cercle et une ellipse sont homéomorphes (il suffit d'écraser un peu le cercle) ; c'est la même chose entre un beignet (un tore) et une tasse à café (nb : Faire un billet à propos de topologie sans évoquer la ressemblance entre le beignet et la tasse relève d'une faute professionnelle)
Illustration d'un tore-tasse
En fait, la simplicité apparente du théorème vient de notre intuition du lacet simple. On a bêtement tendance à l'imaginer simple... On ne pense pas forcément à des choses comme :
Le point jaune est-il à l'intérieur ou à l'extérieur de la courbe ?
Réponse : à l'extérieur
Le point est-il à l'intérieur ou à l'extérieur de ce flocon de Koch ?
Réponse : On pourrait peut-être le savoir avec une plus grande image...
Bernard Bolzano, au début du XIXe siècle, a été le premier à se dire que ce théorème n'avait rien d'évident. Même s'il a réussi à bien poser la question, il lui a été impossible d'y répondre. Il a fallut attendre la fin du siècle (en 1887), avec Jordan, pour avoir une première version d'une démonstration complète utilisant les prémisses de l'analyse complexe. Entre temps, l'étude des courbes a amené un grand nombre de monstres (Weierstrass et sa courbe continue partout et dérivable nulle part, Peano et sa courbe à deux dimensions...)
La sphère à cornes d'Alexander
Le théorème de Jordan supporte cependant très mal son passage à la dimension supérieure ! Le contre-exemple, c'est la sphère à cornes : cela ressemble à une sphère (pour un topologue), mais ne délimite rien de très simple.
Puisque, en dimension deux, on appelle courbe de Jordan un cercle déformé, on va appeler en dimension 3 "surface de Jordan" (nom inventé pour l'occasion de l'article) une sphère déformée (Un truc qui ressemble à une surface et qui est homéomorphe à une sphère). En toute logique, un extérieur de sphère et un extérieur de surface de Jordan devraient être homéomorphe... Et bien, non ! Cette découverte a été faite au début du XXe siècle par le topologue J. W. Alexander, qui cherchait à généraliser le théorème en 3 dimensions.
Pour cela, il faut construire la sphère à cornes. On va procéder par déformation, pour être sûr de bien avoir affaire avec une surface de Jordan. Pour cela, on part d'une sphère, de laquelle on tire deux cornes que l'on met face à face, sans qu'elles se touchent. Au bout de chacune de ces cornes, on tire deux nouvelles cornes qui s'entrecroiseront (toujours sans se toucher), et on répète l'opération à l'infini. On trouve alors un objet fractale et homéomorphe à une sphère (même s'il est très difficile de le voir au premier coup d'œil) :
La sphère à cornes d'Alexander
On peut alors voir que l'extérieur n'est pas homéomorphe à l'extérieur d'une banale sphère. Pour voir ça, il suffit de remarquer que l'extérieur de la sphère à cornes n'est pas simplement connexe.
Je m'explique. Prenez un élastique vivant, et enfilez-le autour d'un ballon. Cet élastique pourra s'échapper sans problème, aller visiter le reste de l'espace et se contracter autant qu'il le souhaite. On dit alors que l'élastique est homotope à un point. N'importe quel élastique vivant à l'extérieur du ballon peut se contracter, on dit que l'espace est simplement connexe.
Maintenant, imaginons un élastique vivant à l'extérieur d'un tore (d'une bouée). Si celui-ci entoure le tore, il lui sera impossible de se contracter sans déchirer le tore : l'extérieur d'un tore n'est pas simplement connexe (Le tore non plus, d'ailleurs).
Maintenant, on peut imaginer l'élastique vivant autour d'une branche de notre sphère à cornes. Même avec toute la volonté du monde, il n'arrivera jamais à sortir des embranchements, puisqu'ils sont en nombre infinis. L'extérieur de la sphère à cornes n'est pas simplement connexe (et peut plutôt s'apparenter à un tore).
L'un est simplement connexe, l'autre non : ils ne sont pas homéomorphes !
En réalité, la sphère à cornes ne contredit en rien le théorème de Jordan qui reste vrai en n'importe quelle dimension (il y a bien un intérieur et un extérieur, le théorème généralisé s'appelle théorème de Jordan-Brouwer), mais contredit le théorème de Jordan-Schönflies (qui dit que, dans le plan, l'extérieur d'une courbe de Jordan est homéomorphe à l'extérieur d'un cercle)
Sources :
Les dossiers de Pour la science n°41 - La sphère à cornes
Beaucoup de wikipédia (Pour toutes les pistes de démonstrations)
14 juin 2009
On a Conjecture about Partitions
De combien de façons différentes peut-on écrire un nombre sous la forme d'une somme ? Prenons par exemple le nombre 4, on a les partitions suivantes :
4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1
On a alors 5 partitions différentes de l'entier 4. On écrit p(n) le nombre de partitions de l'entier n. Les premières valeurs sont les suivantes :
p(1)=1, p(2)=2, p(3)=3 p(4)=5, p(5)=7, p(6)=11
On a ensuite p(7)=15, p(8)=22, p(9)=30, p(10)=42 etc.
On se retrouve donc avec une liste de nombres, les nombres-partitions : 1, 2, 3, 5, 7, 11, 15, 22...
Face à une telle suite de nombres, le mathématicien se pose systématiquement les mêmes questions :
- Quelle est sa série génératrice ? (la série génératrice d'une suite étant un est la fonction f(x)=u0+u1.x+u2.x2+u3.x3... ) Les fonctions génératrices sont merveilleuses pour les informaticiens désireux de faire des calculs toujours plus grand, et permettent de conjecturer et/ou démontrer des propriétés sur la suites.
- Où sont les nombres premiers ? On sait jamais, des fois que ça aide à casser l'hypothèse de Riemann ou à trouver de grands nombres premiers !...
- Où sont les nombres pairs ? et les impairs ? Le genre de questions réflexes qui ne peuvent qu'aboutir à des théorèmes qui vont aider ceux qui s'intéressent à la deuxième question.
...
Pour la première question, c'est Euler qui s'en est chargé, en démontrant la jolie formule suivante :
...
Pour la deuxième question, il se trouve que la suite possède son lot de nombres premiers : 2, 3, 5, 7, 11, 101, 17977, 10619863, 6620830889, 80630964769...
Le plus grand que l'on connaisse, c'est p(15118525), qui compte 4324 décimales (ce qui est peu par rapport aux 13 millions du plus grand connu). Y en a-t-il une infinité ? Impossible aujourd'hui de le savoir, mais la recherche avance.
...
Pour la troisième question, on en sait déjà un peu plus, depuis 1959 : Kolberg a démontré qu'il y a une infinité de nombres-partitions pairs et de nombres-partitions impairs. A vrai dire, on s'en doutait déjà pas mal !
Mais le plus important, c'est le théorème suivant :
Il existe C>0 tels que le nombre de p(n) pairs pour n<N est plus grand que ln(N)C. En écrivant ça plus mathématiquement :
Cette propriété est également vraie en remplaçant "pair" par "impair", et ce théorème est appelé "Théorème de Nicolas-Sárközy". Ce nom vient tout simplement du mathématicien français Jean-Louis Nicolas et du mathématicien hongrois András Sárközy qui ont conjointement signé la démonstration en 1995 !
Reste une question à résoudre : a-t-on environ autant de nombres-partitions pairs que d'impairs ? Les tests sont concluants (sur les 2000 premiers, 1012 sont impairs) cependant, la conjecture de Nicolas-Sárközy est ouverte !
Brève du canard enchainé (quelqu'un a la date ?)
(Pour dire la vérité, cette conjecture porte plutôt le nom de "conjecture de Parkin et Shanks". Le nom "conjecture de Nicolas-Sarkozy" est l'œuvre du mathématicien Tunisien Ben Saïd, qui, faisant suite aux travaux du trio Nicolas-Sarkzy-Ruzsa, a intitulé son article On a Conjecture of Nicolas–Sárközy about Partitions)
06 juin 2009
Jeu, set et match
Roger Federer est-il le meilleur joueur du monde ? La réponse dans cet article remplie de jolies équations, et de charmants graphiques ! Après le sport le plus aléatoire de la semaine dernière, passons à celui le plus prévisible : le tennis !
Rappelons-en rapidement les règle.
Le principe de base de ce sport est de taper dans une baballe à l'aide d'une raquette. En face de soi, l'adversaire doit faire de même, l'idée globale étant d'empêcher son adversaire de rattraper cette dite baballe. Si votre adversaire ne la rattrape pas ou la renvoie dans une zone du jeu inadaptée, vous marquez une quinzaine de point. En marquant des points, on gagne des jeux ; en gagnant des jeux, on gagne des set ; en gagnant des sets, on remporte le match.
Soyons plus précis : pour remporter un jeu, il faut gagner au moins quatre points, avec une avance de deux points (au détail près que le décompte des points se fait sous la forme 0-15-30-40-JEU, un système irrationnel hérité du jeu de paume). Pour remporter un set "sans tie-break", il faut gagner au moins 6 jeux, avec deux points d'écart. Dans un set "avec tie-break", les mêmes règles s'appliquent, mais si le score en vient à être 6/6, un jeu décisif se joue (le premier rendu à au moins 7, avec deux points d'écarts), et qui gagne gagne. Un match se joue en 5 sets (4 sets "avec tie-break" + 1 "sans tie-break"), il faut en remporter 3 sur 5 pour gagner le match.
Maintenant que l'on a tous bien compris le décompte des points, il est temps de se poser la question qui fâche : imaginons que je dispute un match contre Federer. Sachant que j'ai à peu près une chance sur 3 de réussirun point, quelle est ma probabilité de gagner un match contre lui ?
Étape un : gagner un jeu
Pour gagner un jeu contre Federer, le plus simple est de gagner 4 points successifs : la probabilité est de p4, où p=1/3 est ma probabilité de gagner un point (La probabilité est donc d'une chance sur 81 : c'est faisable). A moins que je lui laisse gagner un point sur 5, ce qui peut se passer de 4 manière différente : il gagne le 1er coup et je gagne les 4 autres, il gagne le 2eme et je gagne les 4 autres etc. En notant q sa probabilité de gagner (et donc, q=1-p), ma probabilité de gagner de cette façon est de 4qp4. On peut voir les choses par ce tableau, où un jeu gagnant est un chemin dans le tableau partant de 0-0 et arrivant dans une case bleue.
Combinatoire d'un jeu
Les nombres dans les cases indiquent le nombre de façon d'accéder à un score donné. En bleu les issues favorables, en jaune les défavorables, en gris les égalités (40-A).
On peut voir par exemple qu'il y a 10 façons de gagner avec un score final de 4-2, 20 avec 5-3, etc.
La probabilité pour moi de gagner un jeu est donc :
p4+4qp4+10q2p4+20q3p5+40q3p5+80q4p6+...
A cause de cette règle des deux points d'écart, un jeu peut durer théoriquement aussi longtemps que l'on veut (en oubliant la pluie, la nuit...), d'où la somme infinie. Les observateurs auront remarqué qu'il s'agit en fait d'une somme géométrique, et auront simplifié d'eux mêmes : la probabilité de gagner un jeu est donc de :
Ce qui, en graphique, donne :
Probabilité de gagner un jeu en fonction de la probabilité de marquer un point.
A la vue de la courbe, on peut dire que le système des points amplifie la domination du plus fort : si j'ai une chance sur 3 de gagner un point, j'aurais une probabilité de gagner un jeu de 35/243 ! (Environ 1/7).
Étape deux : gagner un set
Maintenant que l'on sait comment gagner un jeu, il est temps de gagner un set ! Un set peut se gagner avec un score de 6/0, 6/1, 6/2, 6/3, 6/4 ou 7/6. Si c'est 6/6, c'est tie-break, et on rigole (pour les calculs...).
Dans le cas d'un set sans tie-break, les choses sont similaires au cas précédent.
On peut résumer les choses avec ce tableau :
Combinatoire d'un set (à gauche, avec tie-break, en gris ; à gauche sans tie-break)
La probabilité de gagner un set sans tie-break est alors, avec p la probabilité de gagner un jeu, et q=1-p :
L'équation avec tie-break est finalement plus simple à déterminer, mais il reste la probabilité de gagner dans un tie-break :
(Avec T la probabilité de gagner un tie-break, p celle de gagner un jeu, et q=1-p)
La probabilité de gagner un tie-break (7 points à gagner, avec 2 d'avance) en fonction de la probabilité de gagner un point, est la suivante :
Sous forme de graphe, cela nous donne deux courbes qui se ressemble pas mal :
A gauche, la probabilité de gagner un set avec tie-break en fonction de celle de gagner un point ; à droite, la même chose, mais pour un set sans tie-break.
La domination du plus fort se fait encore plus grande !... (avec ma proba de gagner un point de 1/3, ma proba de gagner un set ne dépasse pas 0,13% !)
Qu'en sera-t-il à l'issue du match... Suspens !
Étape trois : gagner le match
Cette fois, le tableau des différentes issues possibles est plus simples :
Combinatoire d'un match : dans le cas 2-2, le dernier
Et donc, la probabilité de gagner un match est de :
où: p est la probabilité de gagner un set avec tie break
p' est la probabilité de gagner sans tie break
q=1-p (la probabilité de perdre un set avec tie break)
Mis sous forme de graphique, cela donne ça :
Probabilité de gagner le match on fonction de la proba de gagner un point
Le graphique est éloquent : je n'ai aucune chance contre Federer! Seulement une chance sur 37 millions !
En fait, même avec une probabilité de réussir un point est de 43%, on ne dépasse pas les 1% de chance de gagner le match. Le système de points du tennis a beau être complètement incompréhensible, il permet au plus fort de gagner à coup sûr, même s'il n'est plus fort que de peu. Le secret de Roger est là : il est un tout petit peu plus fort que ses adversaires ! Au dernier match, Monfils a gagné 45% des balles, et s'est donc logiquement fait laminer !
Au détail près que tout ces calculs ne rendent absolument pas compte de l'avantage du service, de la dimension psychologique, des spectateurs qui perdent leur chapeau sur le terrain ou d'éventuelles blessures...
Sources :
L'algèbre du tennis - Pour la science n°127, mai 1988
31 mai 2009
Oooooon refait le match !
Victoire de Bordeaux avec 80 points, Marseille arrive en seconde place avec 77 points, Lyon sur la troisième place du podium... Nantes termine sur l'avant-dernière place, c'est inacceptable ! Comment est-ce possible qu'une nation du football comme le FC Nantes arrive si bas dans le classement ? Il y a forcément anguille sous roche...
380 matchs, 30% de matchs nul, un écart de 52 points entre le premier et le dernier... Notre ligue 1 est exceptionnelle, c'est surement pour ça qu'on adore en débattre !
Petit rappel des règles du jeu : deux équipes d'une douzaine de joueurs (11, pour être exact) se disputent un ballon, et doivent le mettre au fond du but adverse le plus de fois possible en 90 minutes. Si l'une des deux équipes marque plus de but que l'équipe adverse, elle gagne le match. Sinon, le match est nul.
En ligue 1, il y a 20 équipes, chacune disputant 38 matchs. Une équipe gagnant un match remporte 3 points au score général, 1 point en cas de match nul et 0 points en cas de défaite.
Nantes n'est pas nul, c'est les autres qui sont égaux !
Pour comprendre ce qu'il se passe, imaginons une ligue ou toutes les équipes seraient d'égales force : ils ont 33% de chances de faire un match nul, 33% de gagner et 33% de perdre. En moyenne, une équipe devrait avoir à la fin de la saison un score de 38*(3*35/100 + 1*30/100)=51.3. Lançons une simulation :
Simulation d'un championnat où toutes les équipes ont les mêmes chances de gagner
Première observation : même en faisant une simulation où toutes les équipes ont la même force, le PSG arrive dernier.
Deuxième observation : l'équipe qui arrive en tête mène de 6 points la deuxième équipe, et 35 points séparent les extrêmes du classements (pour des équipes de même force...).
Deuxième simulation : l'une des équipes est plus forte que les autres. En effet, quand elle ne fait pas match nul (45 chances sur 100), elle gagne avec 3 chances sur 5 ! Cette équipe a donc une espérance de 38*(3*42/100 + 1*30/100)=59.28 points.
Simulation d'un championnat où Nantes serait meilleure que les autres
Observation : L'équipe la meilleure du championnat n'arrive pas au sommet du classement ! (Et encore, ils étaient tellement bas dans le classement lors de ma première simulation que j'ai du la relancer...)
Malgré tout son talent et une motivation sans faille, l'équipe favorite n'a pas réussi à arriver aux sommets du classement... Les autres équipes, de talent égales, se partagent des scores vraiment différents... Que s'est il passée ?
Nantes n'est pas nul, ils ont juste pas de chance !
La réponse vient des règles du football : à la fin d'un match
professionnel, les scores sont généralement très bas, et une mauvaise
équipe, suite à un rebond malheureux, peut malgré tout marquer un point
contre toute attente ! Une équipe au top de sa forme qui rate 3 occasions perdra contre l'équipe à qui l'on donne un pénalty hasardeux !
Prenons au hasard deux équipes : l'OM et le FCN. La première équipe marque en général deux fois plus de but que son adversaire. Sachant que le score final est 1-0, qui a bien pu marquer ? 1/3 pour que ce soit le FCN qui a marqué, et 2/3 pour que l'OM ait gagné, et donc, 33% de chance pour Nantes de gagner avec un tel score ! Si 3 buts on été marqué, Nantes gagne dans 25% des cas ; si 5 buts ont été marqué, Nantes gagne dans 20% des cas... Mais ne rêvons pas, 5 buts, c'est bien rare, et les pires équipes gardent finalement toutes leur chance, même face à des adversaires difficiles !
Nantes n'est pas nul, c'est juste Bordeaux qui ne mérite pas sa place !
Donc, c'est Bordeaux qui arrive premier du championnat, suivi de 3 points par Marseille, et Lyon est à 6 points derrière. Bordeaux est-il vraiment le meilleur ? On peut se poser la question ! Et même y répondre !
Le FCGB a donc marqué 80 points sur 114 : ce score reflète le talent du club, mais pas le talent apparent. Peut-être ont-ils été bénis par la grâce, ou alors, il ont joué de malchance. On appelle capacité d'une équipe le score qu'ils auraient du avoir si ils avaient joué avec leur vrai potentiel. Comme on ne sait pas si Bordeaux joue mieux ou moins bien que son potentiel, la capacité de l'équipe se trouve quelque part autour de 80, à plus ou moins 15 points : on peut se dire donc que la capacité de Bordeaux suit une loi normale (même si prendre une loi binomiale aurait pu être une bien meilleure idée pour les calculs... L'exposé n'est ici que qualitatif). sa capacité peut-être tiré au hasard sous cette courbe :
Probabilité de la capacité de Bordeaux
Mais toutes les équipes sont sur le même pied d'égalité, avec leur capacité autour de leur nombre de points réellement obtenus.
En bleu foncé, Bordeaux ; en bleu cyan, Marseille ; en rouge, Lyon ; en rose, Toulouse
Imaginons que seulement Bordeaux et Marseille ont une chance d'être les meilleurs, et que toutes les équipes sont derrière. Pour connaître la probabilité que Bordeaux soit la meilleure, il faut se demander dans quelle mesure ils sont potentiellement devant Marseille :
Face à face entre Bordeaux et Marseille : en faisant 80 points, Bordeaux est devant si le score de Marseille est dans la zone bleu clair.
Si Bordeaux fait 77 points (ce qui arrive dans moins de 5% des cas) , il y a 50% de chance qu'ils soient premier tout de même (77 points de Bordeaux coupent en 2 la courbe de Marseille).
Si Bordeaux fait 80 points (ce qui se produit dans 5 % des cas), il y a 66% de chance qu'ils soient premier tout de même. (La proportion de bleu ciel sous la courbe)
En faisant la somme de tous les cas possible, on trouve que, en ne considérant que ces deux équipes, Bordeaux a une probabilité d'être la meilleure qu'à 62% !
En faisant la même chose avec les autres équipes, on trouve les résultats suivants :
Finalement, si les canaris du Football Club de Nantes sont au fond du classement... C'est juste parce qu'il sont nuls, ya rien d'autre à dire !..
Sources :
La glorieuse incertitude du football - Pour la science, novembre 2002
24 mai 2009
De la ronditude du cercle
Un cercle euclidien (de centre O, de rayon r)
Depuis la nuit des temps (au moins depuis que Grüm a inventé de la roue), nous en sommes tous convaincus : un cercle, c'est rond. Si on nous en demande plus, on peut dire que ça n'a pas d'angle, ça possède un centre parfaitement au milieu, ça a des rayons biens droits... What else ?
Seulement, il n'existe aucun concept assez simple pour ne pas être tordu par l'esprit du mathématicien. Le cercle ne peut évidemment pas y échapper !
La distance euclidienne
Un cercle, en fait, c'est quoi ? Par définition même, c'est l'ensemble des points situés à une distance donnée d'un point appelé centre. C'est même pour cela qu'on utilise un compas pour les dessiner.
On le sait grâce au théorème de Pythagore : la distance entre deux points (x0,y0) et (x,y) est donnée par la formule 
. Pour un point (x0,y0) et une valeur r donnée, la formule précédente nous donne l'équation du cercle que l'on connaît bien.
Même en oubliant la formule donnant la distance entre deux points du plan, on peut tout de même se rappeler de l'équation du cercle grâce à sa définition : le cercle de centre O et de rayon r est l'ensemble des points M tels que :
d(O,M)=r
Ici, d(O,M) est la distance entre O et M.
Oui, mais... Une distance, c'est quoi ?! Même si la boulangerie est à 500 mètres à vol d'oiseau de l'appart, il va falloir quand même se rallonger d'un demi kilomètre pour contourner le stade et aller s'acheter des croissants ! D'un côté, la distance à vol d'oiseau, de l'autre, la distance à pied. Si on peut différencier plusieurs type de distance dans la vie de tous les jours, on peut le faire dans le monde merveilleusement utopique des mathématiques !
La distance de Manhattan
Rendez-nous donc à Manhattan. Un Manhattan idéalisé, où tout le monde est écolo, et où toutes les rues sont perpendiculaires les unes aux autres.
Manhattan, idéalisé, et ses routes en pointillé traits courts interrompus
Imaginons que toutes les rues fassent exactement 500m, quelle est la distance entre le point A et le point B ? Le chemin à vol d'oiseau, en rouge, fait 5 km. Mais Manhattan, même idéalisé, est toujours rempli de buildings, et impossible de passer à travers. Il faut donc soigneusement les éviter : le chemin qu'il faudra emprunter est en zigzag, et le résultat final est une distance à pieds de 7 km entre A et B (Peu importe le chemin choisi, du moment qu'il ne fait pas de détours inutiles) ! La distance entre deux points peut donc ici être donnée par la formule |xA-xB|+|yA-yA|.
On peut se poser alors la question à l'envers : quels sont les points situés à une distance de 1,5 km du point O ? La réponse, ce sont les points en bleu, formant un carré. Un carré qui est le cercle (de Manhattan) de centre O et de rayon 1,5 km !
En gardant la même formule et transposée dans un plan, un cercle de Manhattan est donc un cercle carré !
Un cercle de Manhattan (de centre O, de rayon r)
Les cercles de Minkowski
Il existe donc plusieurs sortes de distance : la distance euclidienne, la distance de Manhattan... Pour généraliser, il faut donc définir ce qu'est une distance !
On est en droit d'attendre trois chose d'une distance : la symétrie (la distance de A à B est la même que celle de B à A), la séparation (deux points situé à distance nulle l'un de l'autre sont les mêmes) et l'inégalité triangulaire (passer par un troisième point rallonge). En traduisant mathématiquement ces propriétés, on peut vérifier que les deux distances déjà définies portent bien leur nom :
Distance euclidienne :
Distance de Manhattan :
Ce qui se généralise par la distance de Minkovski (même s'il n'est pas évident de vérifier qu'il s'agit d'une distance), appelée aussi p-distance :
La distance euclidienne n'est rien d'autre que la 2-distance, et la distance de Manhattan est la 1-distance.
Qui dit nouvelle distance dit nouveau cercle, qui peuvent, suivant les valeurs de p, ressembler à :
A gauche, le cercle pour la 3-distance
A droite, le cercle pour la 0.5-distance
La distance de Chebychev
Mais on peut aller voir ailleurs, et tenter d'autres formules de distance. La plus utilisée est la distance de Tchébicheff, aussi appelée ∞-distance. Elle est donnée par la formule :
Et cette formule nous donne encore un nouveau cercle, lui aussi carré :
Cercle de Чебышёв
Dans tous les cas vu, j'ai parlé de distance entre deux points d'un plan, mais cela fonctionne toujours dans l'espace, dans l'espace-temps (à 4 dimensions) ou dans un espace à 42 dimensions, au détail près que les cercles s'appelleront alors sphère (S2) , hypersphère (S3) ou 41-sphère (S41).
La distance entre sommet d'un graphe
On peut même parler de distance en dehors de la géométrie, dans la théorie des graphes par exemple. Un graphe, c'est un ensemble de points (des sommets) reliés entre eux (par des arrêtes). On peut aller d'un point à un autre en se déplaçant sur les arrêtes. La distance entre deux points d'un graphe, c'est alors le nombre minimal d'arêtes à franchir pour aller d'un point A à un point B.
Si on peut parler de distance, on peut parler de cercle, qui peuvent ressembler à :
Cercle de centre O et de rayon 2, sur le graphe en bleu
(Le cercle, c'est l'ensemble des points noir, le polygone noir n'est ici que pour faire joli)
La distance hyperbolique
Allez, un petit dernier pour finir : le cercle du monde hyperbolique. (Bien que je n'ai pas assez d'un seul paragraphe pour résumer ce qu'est exactement le monde hyperbolique) :
Cercle hyperbolique de centre O et de rayon r (vu dans le demi-plan de Poincaré)
23 mai 2009
Evolution
Réponse de maternelle :
C'est long comme mon doigt.
Réponse de CM1 :
Avec ma règle, je mesure 3,6 cm.
Réponse de 4eme :
ABC est un triangle rectangle en C.
D'après le théorème de Pythagore :
Donc AB ≈ 3,6 cm
Réponse de 3eme :
On a : A (2;4) et B (5;2)
Donc AB ≈ 3,6 cm
Réponse de Terminale S:
A et B sont des points du plan complexe. Ils ont respectivement pour affixe
ZA=2+4i et ZB=5+2i
On a alors :
ZB-ZA = (5-2)+i(2-4) = 3-2i
Le module de ZB-ZA est 
, on a donc :
AB =
Réponse de 2eme année de licence de mathématiques :
On considère l'espace vectoriel ℝ2, muni de sa p-norme usuelle, ainsi que les vecteurs uA=(2,4) et uB=(5,2). On recherche donc la norme du vecteur v=uB-uA=(3,-2)
Pour p∈]0,+∞], on définit la norme Np
Suivant la valeur de p, on a , par exemple :
Remake d'une note de mon vieux blog (2004), mais qui méritait sa place sur Chouxrom'.
En attendant l'article de demain
17 mai 2009
Leibnizdx
Récemment, un collègue blogueur nous parlait de cette étrange formule, découverte là :
Pour un bachelier scientifique, l’erreur doit sauter aux yeux : la même variable est utilisée comme variable muette, et dans l’intervalle d’intégration… Enfer et damnation ! On peut tout de même accorder le bénéfice du doute à Casio : peut-être faut-il différencier les X majuscule des x minuscules, et la formule aurait bien un sens… Dans le deuxième cas, le calcul est très loin d'avoir un intérêt quelconque... La bonne version ça serait plutôt :
Mais au fait, c’est quoi ce ∫ et ce dx qui viennent se balader autour de notre fonction ? Leibniz, on a besoin de toi !
Qu'il est beau, Gottfried
Gottfried Wilhelm von Leibniz (1er juillet 1646 - 14 novembre 1716) (Après maintes vérifications, ces dates sont exactes...) est celui qui nous a inventé cette symbolisation plutôt étrange, en faisant la découverte mathématique du calcul différentiel ! L’a-t-il découvert de lui-même, ou dans les manuscrits de Newton (qui a aussi découvert le calcul différentiel au même moment, et qui a très mal pris le fait de ne pas avoir été le premier à publier...), la polémique ne désenfle toujours pas. Une chose est sûre, c'est lui qui détient le secret de ces notations étranges !
Remontons à l'origine de la découverte, et la question alors primordiale : étant donné une courbe, comment trouve-t-on ses tangentes ? L'idée de Gottfried est le triangle caractéristique, que l'on obtient en traçant une sécante TAA' à la courbe. Le triangle caractéristique est ici le triangle AA'D.
Dans le cas général, nos deux triangles AA'D et TAB sont semblables (proportionnels). Mais que se passe t'il quand les points A et A' sont confondus ? Dans le cas où la droite est tangente à la courbe, les deux points A et A' coïncident, et le triangle caractéristique devient infiniment petit... L'hypoténuse de notre triangle infiniment petit, c'est la tangente à la courbe. Le bon côté, c'est qu'il existe toujours dans une version grand format de ce triangle, grâce au triangle TAB !
On appelle alors AD par dx et A'D par dy ; un d qui provient de "différence". En effet, l'axe des abscisses contient une infinité de point. La longueur dx, c'est précisément la différence entre deux points successifs de cette droite, c'est à dire, une différence infiniment petite.
Maintenant, pour trouver la tangente en un point de la courbe, il suffit simplement de voir que tan(α)=dy/dx. Grâce à l'équation de la courbe de départ, le rapport dy/dx peut être calculé facilement. Ce rapport s'appelle aujourd'hui nombre dérivé, et l'idée que l'on s'en fait n'a pas changé depuis Leibniz !
La définition actuelle de la dérivée : on retrouve bien la notion de différence infinitésimale
Mais notre philosophe allemand ne s'est pas arrêté en si bon chemin ! Un deuxième problème traînait depuis très longtemps : celui de la quadrature. Étant donné une courbe, comment faire pour connaître l'aire délimitée par la courbe ?
Leibniz garde la méthode qui marche : il dessine plusieurs triangles caractéristiques, délimitant un rectangle. Tout ces rectangles forment alors un polygone inscrit sous la courbe. Toujours dans le même ordre d'idée, il rend ces rectangles infiniment petit. L'aire sous la courbe, c'est alors l'aire du polygone aux côtés infinitésimaux !
Infinitésimaux ou pas, ces rectangles restent des rectangles ! Des rectangle de hauteur h et de largeur dx, leur aire est donc y.dx.
L'aire sous la courbe, c'est alors l'aire de tous les rectangles de bases dx, que Leibniz note omn(ydx) (comme "omnia", "tout"). Il le remplacera plus tard par un s allongé, comme "somme", qui ressemble à ∫. Aujourd'hui, pour calculer l'aire sous une courbe, on procède toujours de la même façon, en considérant l'aire des rectangles infinitésimaux sous la courbe.
La technique a été formalisée par Riemann, mais le principe reste toujours le même : on considère des rectangles infinitésimaux, et on somme leur aires.
La formule actuelle de l'intégration de Riemann, bien plus tordue, mais qui rend exactement compte de l'observation de Leibniz
Finalement, le d, placé devant une variable la rend infiniment petite, et le ∫ la rend infiniment nombreuse. Le d représente une différence, et le ∫ représente une somme... La réciprocité est toute trouvée : les deux opérations sont inverses l'une de l'autre, et on appelle aujourd'hui cette réciprocité sous le nom de "théorème fondamental de l'analyse"...
Finalement, dans toute cette histoire, Leibniz a inventé la dérivation et l'intégration, a découvert le théorème fondamental de l'analyse, et a même au passage inventé la notion de fonction !
A moins qu'il ne s'agisse de Newton ?
Sources :
Leibniz, le penseur de l'universel - Les génies de la science,n°28, août-septembre 2006 n°28
10 mai 2009
A mi-chemin entre le triangle et le cercle
- Question mathématique, vous laissez ou prenez la main ?...
- Je prend la main !
- L'indice s'affiche en bas de votre écran....
Il ne tourne pas rond !
- Je suis... top !
Je suis une courbe découverte par un ingénieur allemand du début du XIXe siècle, dont l'une des propriétés est d'être de largeur constante, c'est à dire, dont tous les diamètres sont les mêmes. J'ai permis aux étudiants de l'Institut Royale de Berlin de comprendre qu'un cylindre donnant toujours la même mesure avec un pied à coulisse n'est pas forcément cylindrique...
- Le cercle ?
A gauche, un cercle, dont tous les diamètres sont constants
A droite, un pentagone, avec deux diamètres différents
Le cercle n'est pas la seule courbe à posséder un diamètre constant !
- Non... La main passe... top !
Parmi toute les courbes possédant cette propriété de largeur constante, je suis, selon le théorème de Lebesgue-Blaschke, celle qui minimise l'aire. Ainsi, ma forme permet d'obtenir une forme de plaque d'égout non seulement économique, mais en plus originale, comme à San Francisco...
- Le cercle ?
Plaque d'égouts à San Francisco
La forme habituellement circulaire des plaque d'égout leur permet de ne pas tomber accidentellement, grâce à leur diamètre constan.
- Mais non, un cercle, ce n'est pas très original !... top !
Je suis un polygone curviligne, mais possède moins de côté que ma grande sœur qui a donné sa forme aux pièces britanniques de 20 et 50 pence, ce qui leur permettent d'entrer dans n'importe quel distributeur automatique...
- Le cercle !
Pièces de 50 et 20 pence
Ces pièces ne sont pas circulaires, mais basés sur des heptagones (polygone à 7 côtés). Elles ont cependant un diamètre constant, et peuvent rentrer dans les distributeurs automatiques.
- Mais non, un cercle, ce n'est pas original... top !
Ma forme particulière a permis en 1930 à l'ingénieur britannique Harry Watts de fabriquer une fraiseuse pouvant forer des trous carrés...
- Le cercle ?
Comment forer des trous carrés !
- Mais non, c'est pas le cercle !... top !
Également appelée orbiforme équilatérale, je suis construit à partir d'un triangle équilatéral et de trois arcs de cercles. Je tiens mon nom de mon inventeur, Franz Reuleaux... Je suis... Je suis ...
- Le triangle de Reuleaux !
- Oui ! ! !
Le triangle de Reuleaux, dans toute sa splendeur
Sources :
Des trous carrés
Wikipédia, toujours.
