23 décembre 2012
[#] Papier toilette
Les vacances d'hiver sont enfin là, l'occasion pour ce blog de revêtir ses habits de Noël. Il me fallait un sujet de saison, un sujet familial qui plaise à tous. C'est donc tout naturellement que je vais aujourd'hui parler de l'épineux problème du papier toilette. Ce n'est pas moi qui ai commencé, mais Donald Knuth (l'inventeur du TEX) dans son papier "The toilet paper problem" publié en 1984 dans l'American Mathematical Monthly ! Là, c'est vraiment Noël avant Noël !
Le PQ mathématique Renova, en vente dans tous les bons magasins. Le cadeau de Noël idéal.
Le Toilet Paper Problem
Vivons l'espace de quelques instants la vie d'un responsable petits coins d'une grande société. Pour éviter les manques, chaque cabinet possède deux rouleaux de papier toilette. Il existe cependant deux types d'usagers de toilettes : les grands-choisisseurs et les petits-choisisseurs.
Quand ils ont le choix, les grands-choisisseurs utilisent toujours le rouleau le plus plein, alors que les petits-choisisseurs se serviront de celui qui est le plus entamé. Quand les deux rouleaux sont de même taille, le plus proche sera utilisé. C'est quand les deux rouleaux sont vides qu'il faut commencer à s'inquiéter. A quel point faut-il redouter ce problème ? Quand un rouleau arrive à son terme, qu'en est-il de l'autre ? C'est ça, le Toilet Paper Problem !
Supposons qu'un utilisateur ait une probabilité p d'être un grand-choisisseur et une probabilité q=1-p d'être un petit-choisisseur. Au matin, les deux rouleaux sont de longueur n, et chaque usager ne se servira que d'une seule feuille (ou du moins, d'une seule unité de PQ) lors de son passage. On s'intéresse à Mn(p), le nombre moyen de portions de papier toilette restant quand l'un des deux rouleaux arrive à son terme.
On peut procéder à quelques calculs simples :
Mn(1) = 1. Si chaque usager est un grand-choisisseur, les deux rouleaux seront choisis alternativement. Après 2n-1 passages, il ne restera plus qu'une seule feuille.
Mn(0) = n. Si tous les utilisateurs sont des petits-choisisseurs, un seul rouleau sera utilisé à partir du moment où il sera entamé. Quand il sera vidé, l'autre sera toujours intact.
M1(p) = 1. Quelle que soit la personne qui rentre, si chaque rouleau n'a qu'une feuille, il n'en restera plus qu'une quand il resortira.
M2(p) = 2-p. Pour s'en convaincre, on peut se faire un petit arbre de probabilités
M2(p) = 1×p + 2×(1-p) = 2-p
M3(p) = 3-2p-p2+p3 : de la même façon, on peut se faire un arbre de probabilités (bien qu'à ce niveau là, il faudrait plutôt envisager un graphe).
M3(p) = 1×p2 + 2×p.q + 1×p2.q + 2×p.q2 + 3×q2
= 3-2p-p2+p3
Récursivité
Pour généraliser ces calculs, introduisons la notation Mm,n(p), le nombre moyen de feuilles restant quand l'un des rouleaux est vidé si l'on part d'un rouleau à m feuilles et d'un autre à n feuilles. On supposera n>m.
Par définition, on a :
Mn,n(p) = Mn(p)
M0,n(p) = n
Quand les deux rouleaux sont égaux (et non vides), on se sert sur le premier rouleau, ce qui donne :
Mn,n(p) = Mn-1,n(p) si n>0
Sinon, le premier rouleau est plus petit que le deuxième. Il y a alors une probabilité p de se servir sur le deuxième et une probabilité q sur le premier :
Mm,n(p) = p.Mm,n-1(p) + q.Mm-1,n(p) si n>0
On peut ainsi calculer que M4(p) = 4-3p-2p2+p3+4p4-2p5.
Cette formulation récursive permet de visualiser l'ensemble des chemins possibles par le graphe suivant:
Si un chemin commence sur la diagonale en (n;n), il part en (n-1;n). Il a alors deux choix : aller en (n-1;n-1) ou en (n-2;n).
La valeur de Mm,n(k) peut être alors vue comme la somme, pour k∈[1..n], de k fois la somme du poids des chemins de (m;n) à (0;k), le poids d'un chemin étant le produit de ses arcs.
Notons ck le nombre de chemins allant de (n;n) à (n-k;n-k) qui ne passent pas par la diagonale. Un tel chemin a pour poids pk.qk-1.
On note également dn,k le nombre de chemins allant de (n;n) à (1;k) sans passer par la diagonale. Ces chemins ont pour poids pn-k.qn-1.
Du coup, si un chemin part de (n;n), soit il repasse par la diagonale en (n-k;n-k), soit il n'y repasse pas. On traduit ceci par :
(où la deuxième somme vaut 1 si n=1)
On peut reconnaître dans les ck les nombres de Catalan, et dans les dn,k les nombres qui apparaissent dans le problème du scrutin de Bertrand ("ballot problem").
Finalement ?
En considérant la série génératrice de Mn(p) devenue calculable grâce à l'apparition de termes biens connus, il est possible d'observer le comportement de Mn(p) pour n grand. Le cas p=q est une simple marche aléatoire 1D. (Je vous renvoie à l'article de Knuth pour les détails).
Formule valable pour n aussi grand que p est proche de q.
Supposons qu'il y ait un grand nombre (n) de feuilles dans les deux rouleaux du départ. S'il y a deux fois plus de grands-choisisseurs que de petits-choisisseurs (p=2/3), il restera environ 2 feuilles quand l'un des rouleaux arrivera à son terme. Dans le cas contraire (p=1/3), il en restera environ n/2+1.
Finalement, les résultats sont conformes à l'intuition : si les grand-choisisseurs sont majoritaires (p>q), il ne restera que très peu de feuilles disponibles quand l'un des rouleaux sera à sec. Dans le cas contraire, le papier toilette restant sera proportionnel à la taille des rouleaux !
Courbe du nombre moyen de feuilles de papier toilette restant dans le cas critique où un rouleau est terminé en fonction de la probabilité p de tomber sur un grand choisisseur. (Cas n=16)
Sources :
The toilet paper problem, par Donald Knuth
09 décembre 2012
[#] Quatre mariages et un prix Nobel
Demain, 10 décembre, nous célébrerons les 116 ans de la disparition d'Alfred Nobel. C'est ce jour qui a été choisi pour remettre à leur lauréat les prestigieux prix Nobel. Cette année, les travaux récompensés parlent de cellules souches, de protéines G ou d'optique quantique. A titre exceptionnel, les mathématiques (à travers la théorie des jeux) seront également mises en valeur, à travers le prix (de la Banque royale de Suède en mémoire d'Alfred) Nobel en sciences économiques.
Le cauchemar de Nobel s'est réalisé : des mathématiciens ont été récompensés d'un prix qui porte son nom !
Ce sont donc l'économiste Alvin Roth (61 ans) et le mathématicien Lloyd Shapley (89 ans) qui seront récompensés lundi pour leur utilisation malicieuse du théorème des mariages stables dans des problèmes où l'on doit accorder l'offre et la demande. Aucun aspect financier ici, on cherche plutôt à coupler au mieux internes et hôpitaux ou à donner à des patients en attente de greffe le rein de leur rêve. Le mathématicien David Gale (célèbre aussi pour avoir inventé le jeu de Chomp) aurait probablement été distingué cette année s'il n'a pas eu cette fâcheuse idée de mourir en 2008.
Ce n'est pas la première fois que la théorie des jeux fait l'objet du prix Nobel d'économie : en 2007, pour Hurwicz, Maskin et Myerson, mais surtout en 1994 pour Harsanyi, Selten et surtout John Nash (le mathématicien schizophrène qui ressemble à Russel Crowe) .
Episode 74088 : le problème des mariages stables
Résumé de l'épisode précédent :
Pamela rêve en cachette du beau Dr Sean, marié à l'odieuse Jessica, alors qu'elle a déjà déclaré son amour à Rodney. De plus, Pamela vient de dire "oui" à Bradley, qui ne pourrait jamais la quitter pour Jessica ou Kimberly. Mais Rodney sait, même s'il est marié à Kimberly, qu'il serait plus heureux avec Jessica. Sean révèlera-t-il à Pamela qu'il la préfère à Jessica ? Pamela révèlera-t-elle à Sean qu'elle le préfère à Bradley ? Rodney devra-t-il tout quitter pour Jessica qui, de toutes façon, ne l'aime pas ? Toutes les réponses dans le 74 088e épisode de Les Feux de la Passion !
Le problème est donc le suivant : trois femmes (Pamela, Jessica et Kimberly) et trois hommes (Bradley, Rodney et Sean) ont chacun une idée bien précise de leur idéal. Chaque femme a classé les trois hommes par ordre de préférence, et inversement :
| Pamela : | r > s > b | Bradley : | P > J > K |
| Jessica : | s > b > r | Rodney : | J > K > P |
| Kimberly : | b > r > s | Sean : | K > P > J |
Dans la situation actuelle, les mariages sont les suivants :
| Pamela | - | Bradley |
| Jessica | - | Sean |
| Kimberly | - | Rodney |
Cette situation n'est pas stable. Pamela préfère Sean à Bradley et Sean préfère Pamela à Jessica : ils ont donc intérêt à quitter leur conjoint respectif pour partir se marier à Las Vegas. Y a-t-il moyen de former des couples qui empêchent ces tentations d'infidélité ?...
Pour trois hommes et trois femmes, il existe en fait 6 façons de former trois couples. Parmi ces appariement, trois ne sont pas stables (comme dans l'exemple précédent, où un couple illégitime peut exister), et trois donnent des situations stables. En particulier, il y a la situation où chaque femme choisit son premier choix (solution non optimale pour les hommes), la situation où chaque homme choisit son premier choix (non optimal pour les femme) et une troisième situation où chacun choisit son deuxième choix :
| Pamela | - | Rodney | Pamela | - | Bradley | Pamela | - | Sean | ||
| Jessica | - | Sean | Jessica | - | Rodney | Jessica | - | Bradley | ||
| Kimberly | - | Bradley | Kimberly | - | Sean | Kimberly | - | Rodney |
Dans chacune de ces trois solutions, on ne peut pas créer de couple illégitime qui rendrait à la fois les deux membres plus heureux qu'il ne le sont déjà.
Episode 74089 : l'algorithme Gale-Shapley
Résumé de l'épisode précédent :
Pamela et Sean se sont mutuellement déclaré leur flamme, et ont décidé de laisser tomber Bradley et Jessica. Pour rendre jaloux Kimberly, Jessica a demandé en mariage Bradley. Mais Bradley restera-t-il insensible aux charmes des jumelles Ashley et Candyce qui viennent d'arriver en ville ? Daisy osera-t-elle dire la vérité à Astor à propos de Davy et de Barbra ? Charly aura-t-il sa greffe de rein à temps ? Toutes les réponses dans le 74089e épisode de Les Feux de la Passion !
De manière plus générale, le problème des mariages stables est le suivant :
N hommes et N femmes sont destinés à être mariés. Chaque homme a ses préférences, sous la forme d'une liste strictement et totalement ordonnée (pas d'ex-æquo, pas d'oubli), idem pour les femmes. Est-il toujours possible d'obtenir N couples stables, c'est à dire, sans qu'il existe de couples (A,α) et (B,β) tel que A préfère β à α et β préfère A à B ?
Cette question est reliée au problème des colocataires (l'équivalent "mariage pour tous" du problème des mariages stables) : 2n étudiants doivent se partager n chambres, chacun ayant des préférences (sous la forme d'une liste) sur celui qui partagera sa chambre. Ce partage doit être stable : il ne faut pas que deux étudiants non colocataires se préfèrent au dépit de leur réel colocataire.
En fait, ce problème n'a pas forcément de solutions. On peut imaginer un cas avec 3 étudiants A, B et C tel que A préfère B, B préfère C et C préfère A, ainsi qu'un "gros lourd" D classé dernier par tous les autres. Quel que soit le partage, celui qui se retrouvera avec D aura toujours intérêt à prendre une chambre avec l'un des deux autres.
Il existe également le lemme des mariages, variante du problème des mariages stables, mais c'est plus une question de combinatoire que de théorie des jeux.
Le problème des colocataires montre en fait que le problème des mariages stables n'est pas complètement évident, et pourtant, il existe toujours une solution stable, sans hypothèses supplémentaires !
La démonstration est algorithmique :
Dans un premier temps, chaque homme va se présenter à la femme qu'il préfère. Si une femme reçoit plus d'une proposition, elle ne gardera que le meilleur choix (sans pour autant accepter la demande en mariage).
Les hommes rejetés vont alors déclarer leur flamme à leur deuxième choix. Chaque femme choisit alors l'homme qu'elle préfère parmi les nouveaux prétendants et celui mis de côté à l'étape précédente (s'il existe).
Le speed-dating continue jusqu'à ce que chaque femme ait eu une proposition. Les mariages peuvent alors être célébrés.
Avec ce procédé, chaque femme reçoit forcément une proposition au bout d'un certain temps (au pire, après N²-2N+2 étapes), et un homme ne peut jamais se présenter plusieurs fois à une même prétendante. Surtout, les mariages qui en découlent sont stables. Imaginons que Rodney préfère Jessica à sa femme. Alors, Rodney aura rencontré Jessica avant sa femme, ce qui ne peut se passer que si Jessica a délaissé Rodney pour un meilleur postulant. Du coup, Jessica préfère son mari à Rodney : l'union est stable.
En fait, cet algorithme promet aux hommes une solution optimale. On peut évidement inverser les rôles, ce qui donnerait une solution optimale pour les femmes. Si les deux algorithme coïncident, c'est qu'il n'y a qu'une seule solution stable.
Remarquons de plus que l'algorithme fonctionne aussi dans le cas où le nombre d'homme et de femme n'est pas le même.
Essayons sur un exemple, avec quatre femmes (Ashley, Barbra, Candyce et Daisy) et quatre hommes (Astor, Bradley, Charly et Davy) dont les préférences sont les suivantes :
| Ashley : | d > c > a > b | Astor : | A > B > C > D |
| Barbra : | b > d > a > c | Bradley : | A > D > C > B |
| Candyce : | d > a > b > c | Charly : | B > A > C > D |
| Daisy : | c > b > a > d | Davy : | D > B > C > A |
A la première étape, Ashley aura deux propositions (Astor et Bradley) alors que Barbra et Daisy n'en auront qu'une. Ashley gardera Astor (3e choix) :
Ashley : Astor Bradley
Barbra : Charly
Candyce : ...
Daisy : Davy
En attente : Bradley
Bradley se risquera donc à aborder Daisy, son deuxième choix. Elle le préfèrera à Davy, qui se retrouve maintenant seul.
Ashley : Astor Bradley
Barbra : Charly
Candyce : ...
Daisy : Davy Bradley
En attente : Davy
Le défilé des prétendants continue alors. Davy trouvera du réconfort auprès de Barbra, qui délaissera Charly. Ce dernier trouvera Ashley, qui quittera alors Astor. Après une demande infructueuse auprès de Barbra, il prendra la main de Candyce. Les couples sont alors formés, et les mariages sont stables !
Ashley : Astor
Barbra : Charly Davy Astor
Candyce : Astor
Daisy : Davy Bradley
Grâce à l'algorithme, cette solution est optimale pour les hommes. Dans ce cas précis, il se trouve que ces couples sont aussi les meilleurs pour les femmes : cette configuration n'offrait en fait qu'une seule solution stable.
Episode 74090 : le prix Nobel est accordé à...
Résumé de l'épisode précédent :
Astor a, faute de mieux, déclaré son amour à Candyce. Mais comment va-t-elle réagir quand elle apprendra qu'elle n'est qu'un troisième choix ? Que fera l'impétueuse Jessica quand elle saura tout à propos de Bradley et Daisy ? Charly aura-t-il réellement une greffe de rein ? Sean est-il vraiment médecin ? Quel est le rapport entre le problème des mariages stables et l'économie ? Toutes les réponses dans le 74090e épisode de Les Feux de la Passion !
C'est dans un article paru en 1962 que Gale et Shapley ont posé les bases de ce théorème des mariages stables, en étudiant le problème de l'affectation de n postulants entre m universités, chaque université ayant des quotas. Un tel problème se résoud de la même façon que cette histoire de mariages stable, où chacun des postulants se présente aux différentes universités dans l'ordre de ses préférences.
Un autre problème étudié par Shapley est le cas où la moitié des partis en présence n'a pas de préférence. L'exemple type est celui de la répartition entre les donneurs d'organes et les patients attendant une transplantation. Le système composé par Shapley reste utilisé par de nombreux états américains.
Dans les années 80, Alvin Roth s'intéresse au NRMP, l'organisation chargée d'affecter les internes dans les hopitaux américains. Il découvre qu'ils utilisent l'algorithme Gale-Shapley, et que les attributions sont stables. Jusqu'au jour (en 1995) où le système commence à dérailler, quand un trop grand nombre de couples de médecins cherchent à s'installer dans la même région. Roth est appellé à la rescousse pour modifier l'algorithme. Ce système qu'il a élaboré reste toujours utilisé aujourd'hui.
Finalement, Shapley et Roth n'ont jamais travaillé ensemble, mais c'est la combinaison entre les travaux théoriques de l'un et les travaux pratiques de l'autre qui leur rapporte aujourd'hui le prix Nobel. Et surtout, les mathématiques sont récompensées (et non un domaine qui a davantage mérité sa mauvaise réputation), on ne va pas bouder son plaisir !
Sources :
College admission and the stability of marriage, l'article original de David Gale et Lloyd Shapley paru dans l'American Mathematical Monthly
Stable matching: Theory, evidence, and practical design, le communiqué de presse du prix Nobel d'économie.
25 novembre 2012
[#] Sohcahtoa
Il existe une fonction trigonométrique, c'est la fonction sinus (sin). Dans la vie, elle ne savait pas réellement ce qu'elle voulait, si bien qu'elle passait le plus clair de son temps à errer entre le positif et le négatif. Face à ces symptômes maniaco-dépressifs, on lui a créé un compagnon, la fonction cosinus (cos).
Il existe donc deux fonctions trigonométriques. Mais dans la vie, il n'est pas rare qu'un couple se transforme en famille, lorsque l'un monte sur l'autre. Neuf mois plus tard, une nouvelle fonction trigonométrique fut crée, la fonction tangente (tan).
Il existe donc trois fonctions trigonométriques. Jusqu'au jour où, lors d'une chaude journée d'été, chacun a ressenti l'irrépressible envie de faire des galipettes dans l'herbe fraîche de la campagne. Il tournèrent tellement que trois fonction naquirent : la fonction sécante (sec), la fonction cosécante (csc) et la fonction cotangente (cot).
Il existe donc six fonctions trigonométriques. Cos et Sin commençaient à se sentir à l'étroit au milieu de cette famille grandissante, ils décidèrent de revenir aux fondamentaux de leur relation trigonométrique : la danse. Quatre fonctions se joignirent: les fonctions sinus verse (versin), cosinus verse (vercos), sinus coverse (cvs) et cosinus coverse (cvcs).
Il existe donc dix fonctions trigonométriques. Mais c'est en oubliant le jour où Sec et Csc et voulu fuguer. Ils revinrent en compagnie des fonctions exsécante (exsec) et excosécante (excsc).
Il existe donc douze fonctions trigonométriques. Mais il faut aussi évoquer ces temps sombres où le moral de Cos et de Sin était au plus bas. Ainsi apparurent les fonctions corde (crd) et cocorde (ccrd).
Il existe donc quatorze fonctions trigonométriques. La famille commençait à se déchirer, il fallait réagir. C'est pourquoi ils inventèrent le Réciprocator, une machine qui devait permettre à chaque fonction de retrouver son identité... Le Réciprocator ne fonctionna pas comme prévu, et chaque fonction se dédoubla. Apparurent les fonctions arcsinus (arcsin), arccosinus (arccos), arctangente (arctan), arcsécante (arcsec), arccosécante (arccsc), arccotangente (arccot), arcsinus verse, arccosinus verse, arcsinus coverse, arccosinus coverse, arcexsécante, arcexcosécante, arccorde et arccocorde !
Il existe donc vingt-huit fonctions trigonométriques. Jusqu'à ce jour où le fils unique de la famille Exponentielle est venu se moquer de leur maniaco-dépression. Vexés, ils avalèrent une plaquette de comprimés exponentiels à valeurs complexes. La réaction fut immédiate : chaque membre se dédoubla en son double maléfique hyperbolique.
Il existe donc cinquante-six fonctions trigonométriques : sinus, cosinus, tangente, secante, cosécante, cotangente, sinus verse, cosinus verse, sinus coverse, cosinus coverse, exsécante, excosécante, corde, cocorde, arcsinus, arccosinus, arctangente, arcsécante, arccosécante, arccotangente, arcsinus verse, arccosinus verse, arcsinus coverse, arccosinus coverse, arcexsécante, arcexcosécante, arccorde, arccocorde, sinus hyperbolique, cosinus hyperbolique, tangente hyperbolique, sécante hyperbolique, cosécante hyperbolique, cotangente hyperbolique, sinus verse hyperbolique, cosinus verse hyperbolique, sinus coverse hyperbolique, cosinus coverse hyperbolique, exsécante hyperbolique, excosécante hyperbolique, corde hyperbolique, cocorde hyperbolique, arcsinus hyperbolique, arccosinus hyperbolique, arctangente hyperbolique, arcsécante hyperbolique, arccosécante hyperbolique, arccotangente hyperbolique, arcsinus verse hyperbolique, arccosinus verse hyperbolique, arcsinus coverse hyperbolique, arccosinus coverse hyperbolique, arcexsécante hyperbolique, arcexcosécante hyperbolique, arccorde hyperbolique et arccocorde hyperbolique.
C'est tout ce que j'avais à dire.
18 novembre 2012
[#] Plat comme un tore
Au début des années 50, John Nash annonce qu'il a résolu le problème du plongement isométrique des variétés riemanniennes. Devant l'engouement provoqué par cette annonce, il se met au travail pour résoudre réellement le problème en question. Il revient en 1954 avec la solution, Nash est un génie, on lui remet le prix Nobel. Fin de l'histoire.
Enfin, pas tout à fait. On avait la théorie, mais pas encore d'exemple. Depuis mars dernier, c'est chose faite ! Non seulement, l'exploit est français, mais en plus, il est particulièrement joli !
Nash l'a rêvé, Borrelli l'a fait !
Tore plat vs tore pas plat
Un tore, on a tous une vague idée de ce que c'est : un tube refermé sur lui-même, la forme d'un beignet, d'une chambre à air ou d'une bouée.
Un tore. Bleu.
Pour un topologue, le tore n'a pas besoin d'être en volume pour exister. On le représente le plus souvent par un carré où les côtés opposés sont identifiés. Quand on sort du côté droit du carré, on se retrouve du côté gauche, quand on sort par le haut, on arrive en bas, etc. C'est typiquement le genre d'espace où progresse le vaisseau de Asteroids. On parle souvent de Pac Man comme le symbole d'un personnage évoluant dans un univers torique, mais il n'en est rien : il évolue dans un monde cylindrique !
Un astéroïde qui disparaît sur la droite réapparaîtra à gauche. Telles sont les lois des mondes toriques.
On peut passer de la représentation plate à la représentation en volume par l'opération qu'un mathématicien appellerait un "plongement". Dans le cas du tore, on commence par plier le carré en cylindre, puis on le replie sur lui-même (ce qui demande une certaine élasticité au papier).
Les deux représentations les plus communes d'un tore.
Le parallèle rose et le méridien rouge du tore 3D correspondent aux paires de flèches du tore carré.
Un soucis subsiste : quand on passe de cette façon d'un tore plat à un tore en volume, on doit mettre de côté l'aspect géométrique. Si le plongement s'était mieux passé, les cercles rose et rouge auraient été de longueur identique. L'idéal, ça serait un plongement qui respecte les longueurs. Mais existe-t-il vraiment un moyen de représenter un tore en 3D tout en gardant les longueurs de départ ? Autrement dit, existe-t-il un plongement isométrique ?
En fait, il existe un argument assez simple qui montre qu'un tel plongement ne peut pas exister ! Un tore carré, par essence, c'est plat (courbure nulle), contrairement à un objet tridimensionnel qui peut difficilement être plat partout (courbure non nulle). Quand on sait qu'une transformation (deux fois dérivable) qui ne touche pas aux longueurs ne peut pas toucher à la courbure, on en déduit l'inexistence de plongements isométriques. A moins que...
Flashback
Revenons en 1854. Bernhard Riemann, préparant sa thèse, met le doigt sur ce qui deviendra plus tard la "géométrie Riemannienne". En introduisant le concept de variété (une surface de dimension quelconque pouvant exister ailleurs que dans ℝn, c'est le cas de notre tore plat carré), il montre qu'en topologie, il n'y a pas que la forme qui compte, il y a aussi les distances. Du coup, il trouve le moyen de définir la longueur d'une courbe sur une sphère, un tore ou n'importe quoi d'autre (même de dimensions supérieures).
Riemann bloque tout de même sur une question : peut-on représenter ce tore dans un espace quadridimensionnel (ou plus) sans toucher aux longueurs ? (Enfin, la question portait plutôt sur les variétés riemanniennes de manière générale, mais le problème est le même).
Cent ans plus tard, John Nash rentre en jeu. Incarné au cinéma par Russell Crowe (Un homme d'exception, 2001), il est surtout célèbre pour être l'un des rares mathématiciens récompensé d'un prix Nobel, en 1994. D'accord, le prix d'économie n'est pas vraiment un prix Nobel, mais ça y ressemble beaucoup. Le fait qu'il ait été diagnostiqué schizophrène en 1959 entretient la légende du génie à la frontière de la folie.
En 1954, après avoir révolutionné la théorie des jeux (d'où le Nobel), il s'intéresse au problème de Riemann. En créant des méthodes inédite en géométrie, Nash montre que les plongements isométriques existent bel et bien. Et ils sont même très nombreux. En particulier, il est possible de transformer un carré plat en un tore tridimensionnel sans toucher aux distances, ce qui a de quoi choquer l'intuition. Évidemment, il ne faut pas être trop regardant sur la régularité de ce plongement, mais c'est le prix à payer pour toucher du doigt l'impossible.
Si ces plongements n'avaient pas été découvert plus tôt, c'est parce que leur nature défie complètement l'entendement. Du coup, pour réellement saisir la forme d'un tore qui conserverait la géométrie d'un carré, le mieux serait de le visualiser.
Oui, mais les travaux de Nash ne permettent pas de manipuler ces objets, et encore moins de les représenter. La situation est frustrante : on sait qu'ils existent, mais on ne peut pas les imaginer ! Il faudra attendre les travaux de Mikhaïl Gromov dans les années 80, qui propose de nouveaux outils pour appréhender ces plongements isométrique : "l'intégration convexe" et le "h-principe" (qui lui rapporteront le prix Abel en 2009). Étonnamment, personne à l'époque n'a pensé à utiliser cette mécanique pour les visualiser...
Ce n'est qu'en ce début d'année 2012 que l'on a pu voir pour la première fois un tore plat. C'est en fait la finalité du projet Hévéa ("H-principe, visualisation et applications"), monté par des mathématiciens et informaticiens français de Lyon et de Grenoble. L'objectif aujourd'hui accompli du projet était de traduire algorithmiquement l'intégration convexe, ce qui a tout de même nécessité plusieurs années de travail.
Dessine-moi un tore plat
Finalement, comment fait-on pour réaliser un tore plat en 3D ? Pour cela, on commence par plonger toriquement notre carré dans ℝ3 comme on le fait d'habitude. Ce plongement n'a rien d'isométrique, bien au contraire.
Flat torus : 0 % done
Du coup, il faut corriger ce défaut d'isométrie. En particulier, il faut augmenter la longueur des méridiens pour qu'elle s'approche de celle d'un parallèle (on s'occupera dans un deuxième temps de normaliser ces parallèles). Pour cela, il faut générer une série de vagues à la surface du tore, les "corrugations" (ici au nombre de 12).
Flat torus : 50 % done
En poursuivant le processus en choisissant intelligemment les directions et la fréquence des oscillations, on réduit les défauts d'isométrie. Après un nombre infini d'étapes, on obtiendra un tore plat parfaitement isométrique. Les corrugations diminuant en amplitude au fil des itérations, les transformations finissent par devenir imperceptibles. On peut en fait s'arrêter après la cinquième étape.
Flat torus : 75 % done
Mais nos vaillant chercheurs français ne comptent pas s'arrêter à ce fractale lisse (!). Il leur reste tout un bestiaire de curiosités topologiques sans représentation graphique à affronter. On peut citer par exemple la sphère de Nash-Kuiper (une sphère isométriquement déformée qui tient dans une sphère plus petite) ou le plongement isométrique d'espaces hyperboliques. Mais l'intégration convexe de Gromov, et donc les travaux de l'équipe de Borrelli, trouvent aussi des applications dans la résolution d'équations aux dérivées partielles. C'est en fait plusieurs domaines des mathématiques qui peuvent maintenant passer dans le domaine des mathématiques appliquées !
Le tore plat, vu de l'intérieur
Sources :
Le site du projet Hévéa, d'où proviennent la majorité des illustrations de cet article.
28 octobre 2012
[#] Évoluez-les tous !
Dans le numéro de Juillet-Août de Annals of Improbable Research (le journal des organisateurs des prix IgNobel), une équipe composée de trois entomologistes américains et du très célèbre Professeur Chen s'intéresse à l'épineux problème... de la phylogénie des Pokémon. En étudiant minutieusement leurs aptitudes, les 4 chercheurs ont réussi à recréer l'arbre évolutif des célèbres monstres de Nintendo.
Le clade des Pokémon électriques, extrait de l'arbre évolutif des Pokémon
Un arbre phylogénique est une représentation graphique des liens de parentées entres des espèces
Plus une branche est longue, plus les Pokémon sont éloignés.
On découvre sans surprise que Posipi et Négapi sont évolutivement proches, tout comme Boréas et Fulguris. La proximité entre Emolga et Electhor est un peu plus étonnante !
Phylogénie des Pokemon
L'équipe menée par le professeur Chen s'est en fait servi des méthodes de reconstruction classiques en taxinomie. Bien que celles-ci soient plus souvent utilisées pour mettre en ordre Animalia ou Platae, rien n'empêche de les employer pour ranger les Pokémon ! Dans la pratique, ils ont été définis par leur caractéristiques dans le jeu : leurs types (108 possibles), leur groupe d'œufs (16 possibles), la forme de leur corps (14 possibles) et leurs attaques (559 possibles). Une fois les données rassemblées, l'arbre final des 646 Pokémon (regroupés par familles : Pichu, Pikachu et Raichu forment un même taxon, représenté par la créature la plus évoluée) est érigé par analyse bayésienne de type MCMC.
Cette étude a mis en évidence de nombreux faits cachés par Nintendo. Par exemple :
- Le plus "évolué" des Pokémon est M.Mime ! (Se dire qu'un Pokémon mime est le summum de l'évolution est profondément désespérant)
- La vie Pokémon a commencé dans l'eau, puis est devenue terrestre de trois façons indépendantes : l'ancêtre de Locklass a donné naissance à la clade des Pokémon de glace, l'ancêtre de Marill a engendré la famille des Pokémon vol et psy (dont M.Mime) et tous les autres Pokémon dérivent d'un ancêtre proche de Kaïminus.
- Les types spéciaux (feu, plante, glace, poison, psy...) forment des clades monophylétique. Ainsi, l'ensemble des Pokémon feu descendent d'un même ancêtre aux traits canins, alors que les Pokémon plante descendent d'un ancêtre proche de Bulbizarre.
- La plupart des groupes d'oeufs forment des clades polyphylétiques : ils sont répartis à tous les coins de l'arbre. Même remarque sur la forme des corps.
Méthodes de reconstructions
Avant les années 60, la classification des espèces se basait essentiellement sur des caractères observables à l'oeil nu : morphologie, comportement... Les méthodes avaient leurs limites, un même caractère pouvant apparaître à deux endroits différent de l'arbre évolutif. C'est d'ailleurs cette classification qui a donné le regroupement des reptiles, qui n'a plus lieu d'être aujourd'hui (bien que des arguments morphologiques permettent également de réfuter l'existence d'un tel groupe). Avec l'arrivée du séquençage de l'ADN et des protéines, le domaine a évolué, donnant naissance à la phylogénie moléculaire. Pour comparer plusieurs espèces, ce sont maintenant des régions clés de l'ADN que l'on compare ; une proximité entre ces molécules implique un ancêtre commun proche (les séquences ayant muté depuis une même séquence plus ancienne).
Pour reconstituer un arbre phylogénétique, les plus simples des méthodes consistent à mesurer la proximité entre les espèces qui nous intéressent (on peut par exemple mesurer le degré de différence entre une même protéine). On consrtuit alors une matrice des distances, qui servira de base à l'élaboration de l'arbre. De nombreux algorithmes de reconstructions existent, et, grâce à la recherche, deviennent meilleurs au fil des années. Voyons dans le détail ces différentes méthodes.
L'algorithme UPGMA
Le plus simple est l'algorithme UPGMA ("Unweight Pair Group Method with Arithmetic mean") : à chaque étape, on cherche les deux OTUs ("operationnal taxonomic units", les entités que l'on cherche à classer ; ici, ce sont des Pokémon) les plus proches et on les regroupe. On transforme alors la matrice des distances M entre prenant les moyenne des deux OTUs considérées. Dans le contexte de la phylogénie, cette méthode permet de reconstruire l'arbre des espèces.
Testons plutôt sur un exemple. Nous allons prendre ce qui se fait de plus kawaï en matière de Pokémon : Rondoudou, Nanméouïe, Leveinard, Mélofée et Togepi. Les distances ont été reccueillies sur l'arbre de l'équipe de Chen. Dans la pratique, ces distances peuvent se calculer à partir du degré de ressemblance morphologique de deux espèces, ou à partir de la proximité de séquence Adn SIMILAIRES;
Les deux Pokémon les plus proches sont Mélofée et Togepi (distance de 16). Dans la matrice des distances, on remplace les valeurs par la moyenne des deux colonnes. La nouvelle matrice indique alors que les plus proches sont Nanméouïe et Leveinard (distance 19) :
Troisième étape : on raccroche {Nanméouïe, Leveinard} avec {Mélofée, Togepi} (distance 24), puis on raccroche le tout avec Rondoudou (distance 38)
Cette méthode présente un inconvénient majeur, chaque OTU est à la même distance de la racine de l'arbre. Puisqu'il n'y a aucune raison pour que les branches aient exactement le même taux de mutation, il faut améliorer cet algorithme.
L'algorithme NJ
L'algorithme NJ (Neighbor-Joining) améliore ce point : il permet des branches de différentes tailles. Cependant, le résultat est un arbre sans racine. Pour mettre en place l'algorithme, on part d'un graphe étoilé comme celui-ci.
Le principe de NJ reste grosso le même que UPGMA, mais on change un peu la métrique pour prendre en compte l'ensemble des OTU. Pour cela, on construit une nouvelle matrice de distances Q de la façon suivante:
Q(i,j)=d(i,j)-[r(i)+r(j)]/(N-2)
où N est le nombre d'OTU, d(i,j) est la distance entre i et j, et r(i)=∑d(i,k). En fait, Q(i,j) représente l'éloignement moyen du couple (i,j) des autres OTU.
Les deux OTU les plus proches (disons i et j) selon cette nouvelle matrice sont liés par un nouveau noeud. Pour tenir compte des éventuelles longueurs de branches différentes, la distance entre ce noeud n et l'extrémité i est donné par :
d(n,i)=d(i,j)/2+[r(i)-r(j)]/2(N-2)
Reprenons l'exemple précédent. La matrice des distances M donne une nouvelle matrice Q. Celle-ci montre que Nanméouïe et Leveinard sont les plus proche. Selon la formule, le noeud intermédiaire sera placé à une distance de 7.5 de Leveinard :
On recommence alors avec une nouvelle matrice de distances M. Dans celle-ci, i et j sont remplacées par le nouveu noeud n, sa distance avec un autre noeud k étant:
d(k,n)=(d(k,i)+d(k,j)-d(i,j))/2
Nouvelle matrice de distance
On continue alors l'algorithme avec la nouvelle matrice, ce qui donne l'arbre final :
Toutes les boules roses ne se valent pas.
Et ce ne sont là que les deux principales manières d'interpréter graphiquement un tableau de distance. Mais dans la pratique, le domaine de la phylogénie n'utilise ces méthodes basées sur les distances qu'en première approche. Bien qu'elles soient rapides à utiliser, la construction des matrices de distance entraînent une grande perte d'informations.
Les méthodes de MP
Du coup, pour ne pas perdre de vue les séquences ADN, il faut les garder dans le calcul. Les méthodes les plus simples restent les méthodes MP (Maximum de Parcimonie), qui cherchent parmi tous les arbres celui qui implique le minimum de changements. Les résultats sont bien meilleurs que les méthodes basées sur le calcul des distances, mais sont bien plus coûteuses en temps de calcul.
L'idée principale de MP est de construire toutes les topologies d'arbres possibles et, pour chacun de ces arbres, calculer le nombre de mutations qu'il implique (oublions ici que les séquences d'ADN peuvent muter autrement que par substitution). On part alors de l'hypothèse que le meilleur des arbres est celui qui est le plus économe en transformations.
Le mieux, c'est de prendre un exemple. Avec quatre Pokémon (Nanméouïe, Togepi, Leveinard et Mélofée), il faut tester 3 arbres différents (avec cinq, il aurait fallu en tester 15, et la croissance est plus qu'exponentielle [OEIS : A001147]). En guise d'ADN, on va prendre la suite des 100 CT de la génération V : 1 si le Pokémon peut apprendre la CT, 0 sinon.
N : 0011010001101111111111011011110110100100010110011000000110100000001001001000100000101110010110000000
T : 0010010001100001111111000010110110100100010110011000000100100000000001001000100000101110010001000000
L : 0001011001101111110111011110111100101110010110011000000110100000001101001000110100101110010011000000
M : 0011010001101101111111011011111110100100010110011000000110100000001001001000100000101110010001000000
ADN de Nanméouïe, Togepi, Leveinard et Mélofée
Par soucis de visibilité, on va éliminer les sites n'apportant pas d'informations. En effet, si le caractère est partagé (ou non partagé) par les quatre espèce étudiées, pas la peine de s'y intéresser. On ne garde donc que 23 CT intéressantes :
N : 11011111101010011000110
T : 10000010000010000000001
L : 01111101110101111111011
M : 11011011101110011000001
ADN épuré de Nanméouïe, Togepi, Leveinard et Mélofée
Maintenant, il est temps d'évaluer le poids d'un arbre donné. Prenons celui qui relie Nanméouïe-Togepi à Leveinard-Mélofée :
Il faut maintenant recréer le code génétique des deux ancêtres communs. Pour cela, on procède caractère par caractère.
- Le 1er caractère (CT3) par exemple, est partagé entre Nanméouie, Togepi et Mélofée : on compte donc une mutation, sur la branche e. (on pourrait aussi supposer trois mutations indépendantes sur les branches b, c et d, mais cette hypothèse est moinsprobable).
- Le 6ème caractère (CT15) est partagé entre Nanméouïe et Leveinard : deux mutations ont eu lieu indépendemment sur les branches b et e.
- Le 12e caractère (CT31) est partagé entre Mélofée et Leveinard : une seule mutation s'est produite, sur la branche a.
Au total, cet arbre implique 26 mutations.
Pour déterminer ce nombre de mutation, on peut en fait restreindre davantage le nombre de CT à analyser. Un caractère partagé entre 3 Pokémon sur 4 impliquera une seule mutation, quel que soit l'arbre. On peut donc finalement se limiter à l'étude de 4 CT :
N : 1 1 0 1
T : 0 0 0 0
L : 1 0 1 1
M : 0 1 1 0
ADN très épuré de Nanméouïe, Togepi, Leveinard et Mélofée
En faisant les compte, on peut conclure que l'arbre le plus parcimonieux est celui mettant d'un côté le couple Nanméouïe-Leveinard et de l'autre le couple Togepi-Mélofée. Tout concorde ! Tout comme la méthode NJ, l'algorithme ne permet malheureusement pas de d'obtenir un arbre.
Trois arbres possibles, un seul vainqueur.
L'approche Bayésienne
Bien que de nombreux algorithmes basés sur le principe de parcimonie existent, les reconstructions phylogéniques se servent surtout de méthodes empruntées aux statistiques et aux probabilités, à base d'inférence bayésienne (estimation de la vraisemblance d'un résultat par des arguments probabilistes). L'idée d'utiliser en phylogénie les probabilités pour estimer la vraisemblance d'un résultat n'est pas nouvelle, mais l'approche bayésienne mise au point à la fin des années 90 est aujourd'hui incontournables. C'est d'ailleurs celles-ci qui ont été utilisées par les 4 chercheurs dans leur étude des Pokémon.
L'idée générale est d'estimer, grâce à la formule de Bayes, les probabilités que chaque arbre correspondent aux données. Le problème, c'est que le nombre trop important d'arbre rend impossible ce calcul. Pour cela, on utilise une marche aléatoire (MCMC : Markov Chain Monte-Carlo) : on se promène sur l'ensemble des arbres de manière à visiter le plus souvent les arbres les plus probables. Après un très grand nombre de pas, il suffit de regarder par où l'on est passé : les arbres les plus visités seront les meilleurs.
La clade des pokémon trop mignons, autre extrait de l'arbre évolutif des Pokémon. Celui-ci est construit par inférence bayésienne.
L'analyse phylogénétique est un domaine qui continue de progresser. Outre ses applications de généalogie d'espèces, ces méthodes peuvent aussi être employées en médecine, pour retracer l'histoire d'une contamination par un virus. Les algorithmes bayésiens n'ont d'ailleurs pas encore révélés tous leur secrets, plusieurs problèmes dans ce domaine sont encore ouverts...
Sources
Annals of Improbable Research, juillet-août 2012, volume 18, n°4
Les méthodes probabilistes en phylogénie moléculaire, Frédéric Delsuc et Emmanuel J. P. Douzery.
Génétique, phylogénie et évolution, cours du réseau Génet.
07 octobre 2012
[#] Hexahexaflexagones et cie
Dans sa dernière vidéo, l'excellente Vi Hart présente une merveille des mathématiques récréatives : les (hexa)flexagones. Obtenu à partir d'une simple bande de papier, le flexagone est plus qu'un bout de papier plié mais un objet artistico-topologique défiant l'entendement. Le mieux, c'est d'essayer.
"J'aime le passage où elle parle vite"
Trihexaflexagones
Avant toute chose, sortez papier, ciseaux et scotch: aujourd'hui, c'est travaux manuels !
Commençons avec le flexagone de base, le "trihexaflexagone" ("tri" pour ses trois faces, "hexa" pour sa forme hexagonale et "flexagone" parce que c'est un flexagone). Pour cela, on part d'une bande de papier composée de 9 triangles équilatéraux (on peut ajouter un dixième triangle à la place du bout de Scotch qui sera recollé au premier). Pour les fâchés du compas, on peut obtenir ces triangles par origami (cf la vidéo de Vi Hart).
Recto et verso de la bande.
Les triangles d'une même face du flexagone sont marqués de la même couleur,
Le bout de scotch représenté de part et d'autre est le même.
Après un astucieux pliage (topologiquement, le résultat est un ruban de Möbius), on obtient le flexagone hexagonal :
Première étape : replier les trois derniers triangle devant la bande (vert sur vert)
Deuxième étape : replier les trois premiers derrière la bande, le premier triangle recouvrira le dernier (vert sur vert).
On obtient alors un hexagone bleu, le recto étant rouge.
Ce flexagone se transforme par "pin flex" : pour changer la face du flexagone, on doit replier vers l'extérieur les marques de pliage (en pointillé), et vers l'intérieur les marques de chevauchement (en trait pleins). En répétant la même opération, on peut obtenir chacune des trois faces.
Un seul hexagone, trois faces : là est la merveille des flexagones !
Ce premier modèle a été découvert par hasard en 1939 par Arthur Stone (celui qui résoudra un an plus tard la quadrature du carré), alors étudiant à l'Université de Princeton. S'amusant à plier dans tous les sens des bandes de papier, il est intrigué par l'hexagone qu'il vient de fabriquer. Devant la somptuosité de ce qu'il vient de créer, il fonde avec ses collègues le comité des flexagones de Princeton. Parmi ces collègues figure Bryant Tuckerman, qui étudiera le problème sous toutes ses coutures. Ces pliages seront popularisés en décembre 1956 par Martin Gardner dans le premier article qu'il écrit dans le Scientific American.
Tétrahexaflexagones
Trois faces impliquent 18 triangles équilatéraux, soit 9 par faces sur la bande de papier originale. Et avec 12 triangles, peut-on obtenir un hexaflexagone à quatre faces... Oui ! Et on l'appelle "tétrahexaflexagone". De manière générale, un hexaflexagone à n faces s'obtient avec 3n triangles.
Première subtilité, il ne se construit pas à partir d'une bande de papier rectiligne :
Plan de l'hexaflexagone à 4 faces (pour le montage, commencez par replier l'une sur l'autre les faces bleues)
Deuxième subtilité : à partir de la position Vert/Jaune (Recto/verso), on peut atteindre, suivant la façon dont on plie, la position Jaune/Bleue ou la position Jaune/Rouge.
Diagramme (de Tuckerman) des différentes positions possibles.
Hexahexaflexagones
De la même façon, il existe des pentahexagones, des hexahexaflexagones ou des dotetracontahexaflexagones...
Plan de l'hexaflexagone à 5 faces.
Pour plier ce flexagone, on commence par replier l'une sur l'autre les faces cyans, ce qui ramène au cas du tétrahexaflexagone.
A partir de six faces, trois modèles existent : la bande droite, l'hexagone et le trèfle, menant à des flexagones bien différents (au sens topologique du terme : on ne peut passer de l'un à l'autre par rotation ou pliage. En particulier, leur diagramme n'est pas équivalent.).
Les trois modèles d'hexahexaflexagones
(pour les construire, on commence par se ramener au pentahexagone en pliant intelligement)
Des modèles supérieurs peuvent également être construit, grâce à l'opération de "reflecto-cloning", qui consiste à ajouter une nouvelle face au flexagone précédent en le déconstruisant intelligement. Cette opération est en fait le contraire de ce que l'on fait lorsque l'on monte le flexagone (plier le n-ième flexagone pour arriver au (n-1)-ième flexagone).
On découvre alors qu'il existe 4 heptahexaflexagones, 12 octahexaflexagones ou 27 énnéhexaflexagones (OEIS:A000207), ce qui correspond au nombre de façons de trianguler un polygone régulier à n côtés.
Tétratétraflexagones
Mais les flexagones, ce ne sont pas que des hexagones, il en existe aussi des versions carrées : les tétraflexagones. Encore une fois, il en existe à 3 faces, à 4 faces, à 6 faces ou même à 7 faces)...
Plans des tétraflexagones à 3 faces et 4 faces.
Hexaénnéaflexagones
Et les autres polygones ?... Oui oui, c'est possible ! On peut réaliser des flexagones dont chaque face est un polygone régulier à n côtés, composés de n triangles isocèles. Avec 9 côtés par exemple, l'énnéaflexagone est composé de 9 triangles (70°+70°+40°). En lui imposant six faces, le résultat est... ultra claaasse !
Sources :
[1] Flexagons, de Scott Sherman, avec un bestiaire hallucinant de flexagones exotiques (En particulier, retrouvez la construction de l'énnéaflexagone)
[2] Flexagon.net, un peu moins complet, mais avec beaucoup de flexagones à imprimer.
[3] Flexagon theory, pour constuire un hexaflexagone d'ordre n, entre autres.
16 septembre 2012
[#] La conjecture ABC, aussi facile que 123 ?
La communauté mathématique est en effervescence ! En août dernier, Shinichi Mochizuki a prépublié un papier sobrement intitulé "Inter-universal Teichmüller theory IV : Log-volume computations and set-theoric foundations", l'ultime volet d'une quadrilogie de papiers consacrés à la théorie de Teichmüller inter-universelle. Soyons honnête : la seule personne qui comprend réellement le fond de ces articles est Mochizuki lui-même. Mais un détail change la donne : le mathématicien japonais y annonce la démonstration de l'une des plus importantes conjecture de l'arithmétique : la conjecture d'Oesterlé-Masser, bien plus célèbre sous le nom de conjecture ABC !
La conjecture ABC ne dit rien de la spirale d'Ulam, mais quand même, c'est joli.
Malgré un nom traduisant un manque d'inspiration lors de son baptême en 1985, cette conjecture permet de démontrer en deux coups de crayons un nombre impressionnant de problèmes diophantiens (les équations sur les nombres entiers). Parmi eux, le trop célèbre théorème de Fermat, mais aussi la conjecture de Fermat-Catalan ou le problème de Brocard.
Attendons tout de même encore un peu avant de sauter de joie, la démonstration n'a pas encore été validée. Mais la réputation de Mochizuki le précède, il n'est pas le genre de gaillard à faire des annonces dans le vide. Et même si sa démonstration n'est pas validée, les nouvelles méthodes qu'il a mis en place apportent un vent de fraicheur inespéré. Et ça, c'est réellement réjouissant !
Mais au fait, cette conjecture, elle parle de quoi ?
La conjecture ABC
En quelques mots, la conjecture ABC stipule que lorsque trois nombres sont liés additivement, alors leurs facteurs premiers ne peuvent pas tous être petits. La conséquence, c'est que les équations compliquées sur les nombres entiers ont rarement beaucoup de solutions. Précisons tout cela.
Pour cette conjecture, on a besoin de deux nombres (sans facteurs communs) a et b, ainsi que de leur somme a+b=c. On a aussi besoin de radical : le radical d'un nombre (ou la partie sans facteur carrés), c'est le produit de ses diviseurs premiers (sans multiplicité). Par exemple, le radical de 252 (=22×32×7) est le produit 2×3×7, soit 42. Dans la conjecture ABC, on va s'intéresser au radical du produit abc.
Bien souvent, r(abc) est largement plus grand que c. Par exemple, avec, a=15, b=4 et c=19, on a r(15×4×19) = r(3×5 × 2×2 × 19) = 2×3×5×19 = 570, qui est largement plus grand que 19. Dit autrement, le ratio r(abc)/c est plus grand que 1.
Mais parfois, les facteurs premiers sont plus petits et moins nombreux. Prenons a=1, b=8 et c=9. On calcule alors que rad(1×8×9) = r(1×2×2×2×3×3) = 6. Ici, le ratio r(abc)/c vaut 2/3, plus petit que 1, donc.
On peut faire mieux : a=1 et b=80 donnent r(abc)/c=0.38 ; a=1 et b=512 donnent r(abc)/c=0.22... On peut en fait montrer que ce rapport peut être arbitrairement proche de zéro (en prenant par exemple a=32^n-1 et b=1 - exercice : démontrez-le !).
Le soucis, c'est quand on perturbe un peu ce ratio en considérant cette fois-ci r(abc)1+ε/c (avec ε>0). Même avec ε très petit (par exemple, ε=0.00000001), rad(abc)1.00000001/c ne peut pas être aussi proche de 0 que l'on voudrait. Il semble qu'il y a toujours une barrière infranchissable.
Autrement dit :
Soit ε>0. Alors, il existe K (grand) tel que, pour tous nombres a, b, c (positifs) premiers entre eux vérifiant a+b=c, on a r(abc)1+ε/c ≥ 1/K [que l'on voit plus souvent écrit c ≤ K. r(abc)1+ε ]
Enfin, ça, c'est si la conjecture ABC est vraie, ce qui reste encore à prouver.
Et alors ?
La conjecture ABC, quand elle sera définitivement validée (un peu d'optimisme !) sera l'avancée la plus spectaculaire en analyse diophantienne (et en mathématiques de manière générale) depuis la démonstration du grand théorème de Fermat à la fin du siècle dernier (en 1994, en fait).
Parlons-en, justement, du théorème du Fermat (ou théorème de Wiles), qui cherche à généraliser les triplets de Pythagore (comme 32+42=52) avec des puissances plus grandes. Il énonce donc que si n>2, alors l'équation xn+yn=zn n'admet aucune solution entière non triviale. La démonstration de ce théorème par Wiles a demandé plusieurs centaines de pages.
Maintenant, admettons que la conjecture ABC est vraie, et supposons l'existence de trois entiers x, y et z (sans perte de généralité, on peut supposer qu'ils sont premiers entre eux, que z est le plus grand et que z≥2) vérifiant xn+yn=zn. On pose alors a=xn, b=yn et c=zn, ce qui donne r(abc) = r(xnynzn) = r(xyz). Par définition r(xyz)≤xyz, et, puisque l'on a supposé x,y≤z, on a xyz≤z3. Bref : r(abc)≤z3.
D'après la conjecture ABC, en prenant ε=1, on a K=1 (ou un peu moins, la valeur exacte importe peu), si bien que 1 ≤ r(abc)2/c . D'après l'inégalité ci-dessus, 1 ≤ (z3)2/zn = z6-n. Pour que cette dernière inégalité soit vraie, il faut n≤6. Donc l'équation xn+yn=zn n'admet aucune solution entière non triviale pour n>6. Avec un peu de bidouillages, on peut abaisser n jusqu'à 2.
Bref : avec la conjecture ABC, pas besoin de cent pages pour démontrer le grand théorème de Fermat, une simple marge de livre peut suffir! (Moyennant la démonstration d'un lemme de 500 pages...)
Sources :
Inter-universal Teichmüller theory IV : Log-volume computations and set-theoric foundations, de Shinichi Mochizuki, le papier qui v changer la face de l'analyse diophantienne.
Beyond the Last Theorem, par Dorian Goldfeld
The Amazing ABC Conjecture, par Ivars Peterson
Image : Ulam_Spiral_Divisors
26 août 2012
[#] Mignonne, allons voir si Newroz...
Ils l'ont fait ! La question était ouverte depuis les années 60, et pourtant, ils sont parvenus à le débusquer ! Les diagrammes de Venn symétriques et simples à 11 ensembles existent bel et bien ! Les deux mathématiciens canadiens Khalegh Mamakani et Frank Ruskey sont très fiers de vous présenter leur bébé. Voici Newroz :
Newroz, 11 pétales, 2046 intersections, né le 27 juillet 2012
Au commencement
Les diagrammes de Venn, tout le monde connaît : deux patates (ou plus) qui s'entrecroisent pour représenter l'intersection d'ensembles. En théorie, on devrait l'utiliser pour se représenter mentalement les lois de De Morgan, mais dans la pratique, on s'en sert surtout pour asseoir la supériorité de l'humour à base de mathématiques.
Exemple de diagramme de Venn à 2 ensembles
Exemple de diagramme de Venn à 3 ensembles
Leonhard Euler n'avait pas tout ça en tête quand il a utilisé pour la première fois au XVIIIe siècle des patates pour étudier systématiquement les syllogismes. Un syllogisme c'est, par exemple :
Toute bonne comédie romantique est anglaise
Or tout bon film anglais met en vedette Hugh Grant
Donc toute bonne comédie romantique met en vedette Hugh Grant
A gauche, le diagramme d'Euler correspondant au syllogisme
A droite, le diagramme de Venn du même syllogisme
Il faudra attendre un siècle pour que l'anglais John Venn modernise les diagrammes d'Euler. Avec lui, les patates ne sont jamais imbriquées ou disjointes, toutes les possibilités apparaissant a priori. Les cas impossibles sont simplement grisés (dans le cas précédent, on a grisé la partie correspondant aux bonnes comédies romantiques sans Hugh Grant, puisqu'elles n'existent pas).
Il faut aussi citer Lewis Caroll (celui qui a écrit Alice au Pays des Merveilles), qui a lui aussi mis son grain de sel dans les représentations graphiques des syllogismes.
Ensuite
Pour faire un bon diagramme de Venn, il faut donc n patates (une région du plan délimitée par une courbe fermée sans point double) qui s'entrecroisent et
- qui forment 2n régions (connexes)
- que toutes les intersections envisageables soient présentes.
Pour 0, 1, 2 ou 3 patates, on a les diagrammes en tête. A partir de 4, les choses se compliquent. Plusieurs écoles s'affrontent :
D'un côté, on peut suivre la méthode de Venn : on construit le diagramme à n+1 ensembles à partir de celui à n ensembles en traçant une courbe qui coupe en deux chacune des régions. La méthode fonctionne plutôt bien (peut-être existe-t-il un diagramme de Venn dont le graphe dual n'est pas hamiltonien ?), mais conduit à des résultats un peu brouillons...
Diagrammes de Venn à respectivement 3, 4 et 5 ensembles. Les courbes ajoutées coupent chacune des régions du diagramme précédent.
L'autre méthode, avec bien plus de symétries, est celle de Anthony Edwards. On part d'un plan coupé par deux axes perpendiculaires (diagramme de Venn à 2 ensembles), puis on ajoute un cercle (diagramme à 3 ensembles). Chaque nouvelle courbe serpente autour de ce cercle, en le traversant à chaque nouvelle région. Cette fois-ci, la méthode est universelle, et produit des résultats visuellement intéressants.
Diagrammes de Venn à 3, 4, 5 et 6 ensembles. Point positif : il y a un peu plus de symétrie.
Après
Il y a quand même quelque chose de gênant dans les diagrammes ayant plus de 3 ensembles : toutes les courbes ne sont pas identiques ! Or, un bon diagramme de Venn est un diagramme symétrique. Il faudrait pour cela que chaque courbe soit l'image de la précédente par une rotation. Avec n=1, n=2 ou n=3, il n'y a pas de soucis, mais les choses se gâtent pour n=4. Cela dit, avec 5 ellipses, on obtient assez facilement un diagramme symétrique :
Diagramme de Venn (simple) symétrique pour n=5
Et pour n=4 ? Quand on essaye, on tombe toujours sur un diagramme de la forme ci-dessous. Un tel diagramme n'est pas de Venn, puisque certaines régions sont manquantes (par exemple, il n'y a pas de région seulement rouge et verte).
Raisonnons autrement. Dans un diagramme de Venn symétrique à n patates, il y a 2n régions. Parmi elles, il y en a C(n,k) correspondant à l'intersection de k patates, réparties équitablement sur les n patates. Il faut donc que C(n,k) soit divisible par n, ce qui n'arrive que lorsque n est un nombre premier.
Bref : si un diagramme de Venn à n ensembles est symétrique, alors n est premier. (Et on oublie les diagrammes symétriques à 4 ou 42 ensembles)
Maintenant que l'on sait que des diagrammes symétriques à 7, 11, 13 ou 17 pétales peuvent exister, il faut les trouver. C'est ce qui a été fait par Edward en 1996 (7 pétales), par Hamburger, Petruska et Sali en 2004 (11 pétales) et par Killian, Ruskey, Savage et Weston en 2006 (généralisation).
Adelaide, l'un des 23 diagrammes symétriques à 7 pétales
Un diagramme symétrique pour n=11.
Finalement
Il reste tout de même un soucis majeur : ce dernier diagramme est affreusement laid, la faute à sa non simplicité. Le problème, c'est que lorsque deux courbes se croisent, elles sont rarement les seules. Un diagramme de Venn à 11 ensembles devrait avoir 2046 (211-2) intersections, celui-ci n'en a que 1837.
On dit qu'un diagramme de Venn est simple quand les intersections ne se font jamais entre plus de deux courbes. Avant le mois de juillet, personne ne savait si un diagramme simple existait pour n=11. C'est désormais chose faite : il existe !
Désormais, la question se pose pour n=13...
Sources :
A New Rose : The First Simple Symmetric 11-Venn Diagram, l'article original de Ruskey et Mamakani.
A New Rose : The First Simple Symmetric 11-Venn Diagram, la version simplifiée de l'article, avec plus d'images et moins d'équations (d'où provient l'image de Newroz)
A Survey of Venn Diagrams, le site de très complet de Ruskey et Weston (d'où proviennent les deux derniers diagrammes)
Le tag "venn-diagram" sur tumblr, le plein d'humour à base de diagrammes de Venn
Autres images : xkcd, xkcd, wikicommons
12 août 2012
[#] Erreur des probabilités en votre faveur
"Tiens, et si on se faisait une partie de Monopoly, comme au bon vieux temps ? " Vous ne le savez pas encore, mais en prononçant cette phrase, vous venez d'ouvrir la boîte de Pandore. Ce jeu est de ceux qui font ressortir tout le mauvais enfoui en vous : avidité, manipulation, mauvaise foi... Une seule partie de Monopoly suffit à comprendre les causes de la crise économique.
Mais le Monopoly n'est pas qu'une métaphore du capitalisme, c'est aussi un jeu de société mêlant hasard et stratégie. Mais pour parfaire cette stratégie, il est important de connaître les rouages du jeu. Faut-il tout miser sur les cases bleues, ou s'assurer avec les cases oranges ? Vais-je réellement gagner si je ne possède que la compagnie des eaux ? Mais pourquoi personne ne passe sur les Champs Elysées alors que je passe mon temps sur ton boulevard Henri Martin ?
Bref : sur quelles cases du Monopoly passe-t-on le plus souvent ?
Jouons !
Que l'on joue à l'édition française, à l'édition européenne, à l'édition Montcuq ou à l'édition AC/DC, le plateau reste toujours le même. Quarante cases disposées en carrés, dont 22 propriétés, 4 gares, 2 services publics, 4 chances/caisses de communautés et 7 autres cases plus ou moins heureuses. Pour dépouiller ses adversaires, l'objectif est d'acquérir un maximum de propriétés, sachant qu'un groupe d'une même couleur rapporte plus que des propriétés isolées.
Dans le détail, les 40 cases de l'édition classique française sont les suivantes :
Pour commencer, tous les joueurs se placent sur la case départ, puis on jette les deux dés. On ne s'intéresse qu'au parcours d'un seul jouer, les probas étant indépendantes, et les mêmes pour chaque joueur. Où va arriver le premier joueur ? On calcule facilement que la probabilité que la somme des dés soit 2 ou 12 (resp 3 ou 11, 4 ou 10, 5 ou 9, 6 ou 8, 7) est de 1/36 (resp 2/36, 3/36, 4/36, 5/36, 6/36) ; au premier tour de jeu, le plus probable est donc de tomber sur la case n°8 (chance), puis sur les cases n°7 ou n°9 (bleu clair), etc. (cf les diagrammes un peu plus bas)
Pour le deuxième lancé de dé, on procède de la même façon. Calculons par exemple la probabilité de tomber sur la case n°6 (Gare Montparnasse). On peut arriver sur cette case en faisant 2 (proba : 1/36) depuis la case n°4 (proba : 2/36) ou en faisant 3 (proba : 2/36) depuis la case n°3 (proba : 1/36). On pourrait aussi arriver sur cette case en faisant 4 (proba : 3/36) depuis la case n°1, mais cette dernière a une proba nulle. Finalement, au deuxième tour, la probabilité d'arriver sur la case n°6 est de 1/36×2/36 + 2/36×1/36, ce qui donne 0.3%. (cf les diagrammes un peu plus bas)
De manière générale, pour connaître la probabilité de tomber sur la n-ième case après k lancés, il faut chercher les différentes façons d'atteindre cette case. Dans le cas général, il y a 11 façons d'y arriver : en faisant 2 (proba : 1/36) depuis la case n-2, en faisant 3 (proba : 2/36) depuis la case n-3, etc. La probabilité de tomber sur la case n°n au k-ième lancé de dé est donc de 1/36×pn-2 + 2/36×pn-3 + ... + 1/36×pn-12, où pj désigne la probabilité d'atteindre sur la j-ième case lors du lancé précédent (le (k-1)-ième).
Les calculs deviennent très vite impossibles à faire à la main. Heureusement, l'être humain a inventé l'informatique. Et les matrices stochastiques.
Pour rendre compte de la situation, on utilise la matrice 40x40 suivante :
Le nombre Pi,j (i-ème ligne, j-ième colonne) indique la probabilité d'atteindre la j-ième case depuis la i-ème. Par exemple, la première ligne signifie que, depuis la case n°1, on peut atteindre la case n°3 avec une proba de 1/36, la case n°4 avec une proba de 2/36, etc.
En notant uk le vecteur donnant la probabilité des 40 cases d'être atteintes après k lancés, le vecteur u.P donnera les probabilités des cases au lancé suivant.
Par exemple, la distribution des probas au début du jeu est u0 = [1, 0, 0, ..., 0] (tout le monde est au départ). Au premier lancé, la distribution devient u1 = u0.P. Au k-ième lancé, elle est alors uk = u0.Pk.
En programmant tout ça, on peut calculer ce qu'il se passe après 1, 2, 10 ou 50 lancés :
Distribution des probabilités après 1, 2, 10 ou 50 lancés de dés.
Moralité : plus la partie dure, plus les différentes cases deviennent équiprobables (et se rapprochent de 2,5 %). Autrement dit, aucun groupe de propriétés ne semble meilleur qu'un autre...
En poursuivant les calculs, on se rend compte que les probabilités se stabilisent autour de la distribution équiprobable : c'est la seule distribution qui vérifie u=u.P. (tips : ce vecteur u est le générateur du noyau de t(P-I) )
Ne passez pas par la case départ, ne touchez pas 20 000 F
Mais les déplacements du Monopoly ne sont pas si simples que ça ! Déjà, il y a la case "Allez en prison" (n°31), sur lequel il est impossible de se poser, et qui emmène directement à la case n°11.
De plus, lorsque l'on fait trois doubles de suite (ce qui a 1 chance sur 216 de se produire) , on fait un excès de vitesse : direction la prison !
L'existence de cette case prison change totalement la donne ! Il va falloir refaire tous les calculs. Pas de panique, il suffit juste de modifier la matrice de transition P, et le tour est joué.
Dans les faits : Pour cette histoire de case "aller en prison", il suffit simplement de reporter la colonne n°31 (qui devient nulle) sur la colonne n°11. Pour les excès de vitesse, on supposera qu'il a une chance sur 216 de se produire : dans 215 cas sur 216, on se déplacera à la case normalement (multiplier chaque case par 215/216), sinon, on est amené à la case n°11 (ajouter 1/216 dans la colonne n°11).
Pour connaître les distributions après k lancés, les mêmes calculs que précédement sont à faire :
Distribution des probabilités après 2, 10, 50 ou ∞ lancés de dés, en prenant en compte la case "prison"
Finalement, la case prison/visite devient un passage obligé du plateau, les cases suivantes gagnent tout de suite en popularité. Les différentes couleurs ne se valent plus tout à fait, ce qui donne un léger avantage à l'orange, au jaune et au rouge :
Probabilités de tomber sur les différentes couleurs du jeu, en prenant en compte la case "prison"
Rendez-vous Rue de la Paix
Pour que le modèle soit parfait, il reste deux détails à prendre en compte :
- Les modalités de sortie de prison. En effet, pour retrouver la liberté, il faut impérativement faire un double (au moins pendant deux tours). Du coup, on sort plus souvent de prison en faisant 8 qu'en faisant 7. Dans le modèle, on supposera que l'on sort de prison en faisant un double dans 11 cas sur 36 (probabilité de faire au moins un double en deux lancés), et que l'on sort normalement dans les autres cas.
- Les cartes chances et caisse de communauté. Celles-ci ont tendance à nous emmener en prison, à la case départ ou ailleurs. Dans le détail, sur les 16 cartes chances et les 16 cartes Caisse de communauté, les cartes qui téléportent sont les suivantes :
Cartes chance (cases n°8, n°23 et n°37) :
Allez à la case départ (n°1)
Allez boulevard de la Villette (n°12)
Allez gare de Lyon (n°16)
Allez avenue Henri-Martin (n°25)
Allez en prison (n°31)
Allez rue de la Paix (n°40)
Reculez de trois cases (n°5, n°20 ou n°34)
Cartes caisse de communauté(cases n°3, n°18 et n°34) :
Allez à la case départ (n°1)
Allez Boulevard de Belleville (n°2)
Allez en prison (n°31)
Payez une amende ou piochez une carte chance
La matrice P est à transformer en conséquence. En particulier, il faut prendre en compte le cas où l'on recule sur la case n°34, ce qui a pour effet de piocher une carte Caisse de Communauté. Dans ce modèle on supposera que l'on paye l'amende plutôt que de piocher une carte chance (ça ne change pas grand-chose aux résultats, et j'ai un peu la flemme de le programmer).
Dans les graphiques suivants, on distinguera la case Visite de la prison (n°11) de la case prison (n°31).
Probabilité de visiter les différentes cases du Monopoly, en prenant en compte toutes les règles
Au final, les cases chances sont les cases sur lesquelles on s'arrête le moins, tandis que la prison reste toujours la plus fréquentée. Du côté des propriétés, seul le boulevard Henri-Martin (n°25) dépasse les 4%, suivi du boulevard Saint-Michel (n°19) et de la place Pigalle (n°20). La propriété la moins fréquentée est alors - et c'est décevant - l'avenue des Champs Elysées (n°38). Les groupes oranges et rouges creusent davantage l'écart, les rendant inévitable pour gagner (surtout que ces rues sont relativement abordables).
Probabilité de visiter les différentes cases du Monopoly, en prenant en compte toutes les règles
Moralité : on oublie le bleu, et on mise tout sur le orange, le rouge et le jaune. Les probabilités sont de votre côté !
Sources :
Trop monopoly pour être honnête - Ian Stewart - Pour la science n°224 Juin 1996
Comment gagner au monopoly ? - Mémoire de maîtrise, apportant toutes les bases théoriques (chaîne de Markov, etc.)
Si vous voulez analyser les résultats plus en profondeur, et améliorer les usines à gaz que sont mes algorithmes Matlab, voilà de quoi faire : fichier 1, fichier 2 et fichier 42.
Images : Monopoly board
05 août 2012
[#] Les deux font le pair
L'arithmétique est un domaine très particulier des mathématiques : ses concepts sont simples (pgcd, nombres premiers...) mais ses théorèmes sont rares et peu puissants. Du coup, dès qu'une conjecture résiste un peu, elle devient très vite incassable. La conjecture de Goldbach fait partie de ces problèmes insolubles.
A l'occasion des avancées récentes du médaillé Fields Terrence Tao, aujourd'hui est l'occasion de revenir sur ce problème, à travers une reconstitution historique.
Sources :
Goldbach sur WIMS - Cherchez des contre-exemples !
On Snirel'man's constant - L'article de Olivier Ramaré.
Every odd number greater than 1 is the sum of at most five primes - L'article de Terrence Tao (prépublication)
Goldbach conjecture verification - la page de Tomás Oliveira e Silva