Choux romanesco, Vache qui rit et intégrales curvilignes

29 mars 2015

Deux hommes d'exception

Le 25 mars dernier, le lauréat du prix Abel a été révélé et, pour une fois, ce n'est pas un mathématicien qui est récompensé du "prix Nobel des maths", mais deux : il s'agit de la rockstar John Nash, et du un peu moins célèbre Louis Nirenberg. Les deux ont été récompensés pour « leur contribution importante et fondamentale à la théorie des équations aux dérivées partielles non linéaires et leurs applications en analyse géométrique. »

John_Forbes_Nash,_Jr  Louis_Nirenberg
John Forbes Nash Jr et Louis Nirenberg

D'un côté, il y a l'américain John Russell Crowe Nash, essentiellement célèbre pour avoir été l'un des rares mathématiciens récompensé d'un prix Nobel (même si le Nobel d'économie n'en est pas vraiment un...) pour ses travaux en théorie des jeux. Mais sa célébrité vient surtout de Hollywood, qui lui a consacré un biopic un brin romancé et multi oscarisé en 2001, avec Un homme d'exception (A beautiful mind). Le film met en scène ses années à Princeton, où il met au point le concept d'équilibre dans les jeux non-coopératifs, appelé aujourd'hui "équilibre de Nash" (faudrait que j'écrive un article là-dessus un de ces jours...). Mais ce que Hollywood met surtout en scène, ce sont les 30 années (de 1959 à 1990) où il est dans l'incapacité de faire des mathématiques à cause de la schizophrénie paranoïque qui lui a été diagnostiqué. Le film passe cependant à côté de ce qui fait sa renommée dans le monde des mathématiques, ses travaux en analyse géométrique, qui lui vaut aujourd'hui l'une des deux récompenses suprêmes pour un mathématicien.

De l'autre côté, il y a le canado-américain Louis Nirenberg, avec un parcours forcément un peu plus classique. Il fait sa thèse à l'Université de New York (NYU) à partir de 1947 sous la direction de James Stocker qui lui propose un problème de géométrie ouvert depuis 30 ans, le problème de Weyl. Ce problème qui traite de sphère, il l'attaque sous l'angle original des équations aux dérivées partielles (EDP) elliptiques, sujet qu'il traitera sous toutes ses formes jusqu'à sa retraite en 1999, et toujours au NYU. Bien que 90% des papiers qu'il ait rédigé soient en collaboration avec d'autres mathématiciens, il n'en a jamais cosigné avec John Nash. Il se sont cependant rencontrés à la fin des années 50, où Nirenberg lui a exposé un problème concernant les EDP qui deviendra quelques années plus tard le théorème de De Giorgi-Nash-Moser.

Analyse géométrique
L'analyse géométrique, c'est donc la branche des mathématiques qui s'occupe de traiter les problèmes de géométrie (sur la forme et la mesure d'objets comme des courbes ou des surfaces) avec les outils des analystes, notamment les EDP (sans rentrer dans les détails, une EDP est une équation où les inconnues sont des fonctions à plusieurs variables -- le simple fait de montrer qu'une telle équation admet une solution est en général particulièrement difficile...)
Le problème récurrent de ce domaine est celui des plongements, et plus particulièrement celui des plongements isométriques. Comme son nom l'indique, un plongement est l'opération qui consiste à placer un objet géométrique dans un espace donné.

Prenons l'exemple du tore. Sa représentation habituelle est celle de la surface d'un donut's ou d'une bouée, une représentation qui n'existe donc que dans un espace à trois dimensions. L'image que l'on se fait d'un tore est donc le plongement de celui-ci dans l'espace R3.

Tore_pas_plat

Plongement d'un tore dans l'espace euclidien R3

Mais le tore est une surface, un objet à seulement deux dimensions : il n'a a priori pas besoin d'un espace à 3 dimensions pour exister. Et c'est bien le cas, on peut se représenter un tore à l'extérieur d'un espace tridimentionnel, en prenant l'image du jeu vidéo Asteroids : un carré où les côtés opposés sont identifiés, c'est à dire que, lorsque l'on quitte ce carré du côté droit, on réapparait du gauche, et réciproquement ; même chose pour les bords hauts et bas.

 

Toretore

Les deux représentations les plus communes d'un tore.
Sur le carré-tore de droite, les flèches bleues et vertes se correspondent.
Le parallèle rose et le méridien rouge du 3D correspondent aux paires de flèches du tore carré.

Pour ce tore carré, le plongement dans l'espace 3D le plus simple est de procéder par origami. On commence par enrouler le carré pour faire correspondre les côtés droit et gauche (on obtient un cylindre), puis, on enroule ce cylindre de façon à faire correspondre les bords haut et bas (bon, il faut imaginer ce papier élastique pour pouvoir réaliser cette opération). 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 sur le carré-tore auraient été de longueurs identiques sur le beignet-tore. 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 ?
C'est ce que l'on appelle le problème du plongement isométrique, et c'est celui-ci que Nash a résolu en transformant ce problème de géométrie en problème d'analyse.

Problème du plongement isométrique (un théorème de Nash)
En fait, la question ne porte pas exclusivement sur les tores, mais sur n'importe quelle courbe ou autres surfaces et espaces de dimension supérieur (plus particulièrement, les variétés riemaniennes). La question du simple plongement a été réglée depuis longtemps : il y a toujours moyen de se représenter ces objets dans l'espace euclidien auquel on est habitué.

Le problème, c'est que dans l'espace euclidien, on a une façon habituelle de mesurer les distances (mesure euclidienne avec une bonne vieille règle graduée, toussa), et qu'il est hors de question de changer notre façon de mesurer les distances sous prétexte que l'objet géométrique sur lequel on travaille vient d'un espace topologique exotique sur lequel on ne mesure pas les distances de la même façon. En fait, une variété riemanienne, c'est ça : un espace topologique (une courbe, une surface) qui dispose de sa propre façon d'y mesurer les distances. Et un plongement isométrique, c'est un plongement de cette variété dans l'espace euclidien où la distance euclidienne coïncide avec la distance propre à la variété.

Prenons l'exemple d'une variété riemanienne assez simple de dimension 1 : une route de campagne, rectiligne, sur lequel nous marchons. La particularité de cette route, c'est que plus on y progresse, plus elle devient boueuse, et donc, plus notre marche devient lente. Pour mesurer des distances entre deux points de cette route, la façon habituelle de mesurer ("il y a 5 km entre le point A et le point B") n'est pas adaptée, il serait plus logique de les mesurer en temps ("il y a une heure entre le point A et le point B").

Le problème, c'est que si on regarde cette route d'un point de vue extérieur, la mesure temporelle ne coïncide pas du tout avec la mesure à vol d'oiseau. Le plongement de cette route dans l'espace euclidien n'est donc pas isométrique. Y a-t-il moyen de représenter cette route sur un plan de façon à ce que la mesure temporelle et la mesure euclidienne soit la même ?

Route

Plongement de la variété "route boueuse" dans l'espace euclidien :
la distance intrinsèque de la variété (la distance temporelle) ne correspond pas à la distance euclidienne.

Une façon simple de contourner le problème est de représenter la route en la dilatant de façon à ce que 5km sur le plan correspondent toujours à une heure sur la route. Le problème, c'est que la représentation que l'on obtient au final est très éloignée de la route initiale.

Route_2
Plongement de la variété "route boueuse" dans l'espace euclidien :
la distance intrinsèque de la variété (la distance temporelle) correspond à la distance euclidienne.
Le résultat est cependant éloigné du plongement initial.

C'est ce principe que l'on utilise pour faire des cartes temporelles, où la distance euclidienne correspond à la distance temporelle :

SNCF

Oui, mais ce que l'on veut, c'est le beurre et l'argent du beurre : une représentation de cette route boueuse où la distance euclidienne soit égale au temps de parcours et qui, en plus, ne soit pas trop éloignée de la représentation initiale.
Aussi étonnant que cela puisse paraître, c'est parfaitement possible ! Et si personne n'y avait pensé avant Nash, c'est parce que le résultat défie l'intuition :

Route_3


En ajoutant des oscillations, les distances temporelles et euclidiennes se correspondent, et le résultat est proche de la représentation initiale. C'est le plongement parfait !

Imaginons un vélo où les pédales feraient tourner les deux roues en même temps, mais où l'une des roues tournerait plus vite que l'autre. Pour faire avancer ce vélo sans déraper, il faut nécéssairement que les trajectoires des roues soient proches l'une de l'autre, mais que l'une des deux trajectoires soit plus longue que l'autre. La trajectoire de la roue plus rapide sera nécéssairement pleine d'ondulations, pour compenser la différence de vitesse. C'est exactement la même chose qu'il s'est passé dans cette histoire de plongement isométrique de route boueuse.

On peut se poser la même question pour le tore carré présenté plus haut. A partir d'un carré de papier non élastique, peut-on le déformer sans plis ni déchirement de façon à obtenir un tore ?... D'après Nash, oui, un tel un plongement existe. Autant le raisonnement est a peu près accessible pour des objets à une seule dimension comme un route, autant la généralisation aux surfaces ou aux variétés riemaniennes de dimensions supérieures devient un casse-tête pour l'intuition. La complexité des arguments du théorème de Nash-Kuiper publié en 1954 fait qu'il a fallu attendre 2012 pour ce donner une idée de ce que cela pourrait donner (j'en avais parlé ici).

01_corrugations_bd (2)
Plongement isométrique d'un tore : forcément, il est plein d'ondulations

Problème de Minkovski (un théorème de Nirenberg)
Un petit mot sur un des premiers problèmes auquel Nirenberg s'est attaqué en 1953 : le problème de Minkovski.

Pour comprendre la question, il faut parler de courbure, qui permet de quantifier à quel point un objet est courbe.
Grosso modo, la courbure d'un arc correspond à l'inverse du rayon du cercle qui ajuste au mieux cette courbe (le cercle osculateur, littéralement, "qui donne un baiser"). Ainsi, si une courbe présente un virage dur, le cercle osculateur sera petit, et donc, sa courbure grande. Inversement, si une courbe présente un virage faible, le cercle osculateur sera grand, et donc la courbure faible. Une courbure nulle correspond à une courbe localement très plate.

Courbure

Une courbe et quelques cercles osculateurs.
La courbure en A est donc grande tandis que la courbure en C est faible (et intermédiaire en B)
Au point D, le cercle osculateur a un rayon infini, la courbure y est donc nulle.

On peut alors se demander à quoi ressemblerait une courbe dont la courbure en tout point serait fixée à l'avance.
Par exemple, à quoi ressemble une courbe dont la courbure serait en tout point égale à son abscisse curviligne (autrement dit, une courbe où, plus on avance dessus, plus la courbure devient grande). Eh bien, cela donne la clothoïde (du grec klothein : filer la laine), une courbe particulièrement utilisée dans le design des autoroutes ou des chemins de fer :

Clothoide
La clothoïde, courbe qui correspond à la trajectoire d'une voiture où le conducteur tourne le volant à vitesse constante.
En avançant à vitesse constante sur une telle courbe, la force centrifuge subie sera proportionelle au temps, d'où son utilisation dans les bretelles d'autoroute.

La même question se pose pour les surfaces où l'on peut aussi y définir une courbure particulière, la courbure de Gauss, dont la définition généralise celle de la courbure d'un arc.
Une sphère de rayon R a, en tout point, une courbure de Gauss égale à 1/R². Un plan, un cylindre ou un cône auront en tout point une courbure nulle (on peut toujours y trouver des plans de coupe rectiligne).

Bref. À quoi ressemblerait une surface dont la courbure en tout point serait une fonction (positive) définie à l'avance ? Tel est l'objet du problème posé en 1903 par Hermann Minkovski.
Prenons comme exemple la surface de la Terre. On peut prendre comme fonction la température moyenne en chaque point de la Terre (moyennant une renormalisation). On peut alors se demander à quoi ressemblerait cette Terre si en tout point, sa courbure était égale à la fonction. Cela donnerait donc un globe aplati au niveau des pôles (de courbure faible ) et bombés au niveau de l'équateur.

ObjectifTerre
Un exemple de fonction définie sur une sphère.

Nirenberg a donc réussi à prouver que, sous les bonnes conditions, cette surface de courbure imposée existe toujours. Dans le même papier, il balaie une autre conjecture ouverte depuis 1916, la conjecture de Weyl. Sa solution marque un point important dans l'histoire de la géométrie puisque, pour la première fois, des problèmes de géométrie sont résolus à l'aide d'EDP non linéaires.


Sources :
John F. Nash Jr. and Louis Nirenberg, sur le site officiel du prix Abel
Images : photo 1, photo 2


15 mars 2015

#LaPiHour

Hier, nous étions le 14 mars 2015. En notation anglaise, c'était donc le 3/14/15, soit une très bonne approximation du nombre π (dont la troncature à 5 décimales est effectivement 3,1415). Mais  le plus fort là-dedans, c'est que à 9h, 26 minutes, 53 secondes et 59 centièmes, nous avons pu célébrer un instant quasi unique de ce siècle, l'instant π !

f8565d2a-dacf-4c07-b543-42bd8c966adc-1024x768
Représentation due à Francisco Aragón des 100 milliards premières décimales de π en base 4, où les chiffres 0, 1, 2 et 3 sont représentées par un déplacement le nord / sud /est /ouest.

Pour fêter ça, j'ai profité de la journée d'hier pour poster tout un tas de trivia autour de cette constante reine des mathématiques, dont voici un petit florilège :

 

 

 

 

 

 

 

 

 

 

Tweet

 

 

 

 

 

 

Quelques autres formules hallucinantes que l'on doit à Ramanujan :

RamaOne 

RamaTwo

 

Posté par El Jj à 10:00 - Commentaires [3] - Permalien [#]
Tags : , , ,
07 mars 2015

Deux minutes pour l'escargot de Gardner

Un nouvel épisode de "deux minutes pour", où il est entre autres question d'escargot sur une corde élastique, et d'une course entre une tortue et un héros mythologique...

Vignette

 

Transcription :

En 1982, Martin Gardner publie "Aha : Gotcha", un recueil de paradoxes mathématiques allant des antiques paradoxes de Zénon jusqu'à celui de l'hôtel de Hilbert. Parmi eux figure le paradoxe de la corde élastique, une variante du paradoxe de Achille et de la Tortue, dont la solution est particulièrement contre-intuitive. Ce problème met en scène un vaillant escargot, une corde considérablement élastique et un géant facétieux. Ce qui tombe bien, c'est que j'ai justement deux (deux?) minutes pour en parler.

Cette histoire met en scène Léo, un escargot particulièrement obstiné qui voue sa vie à atteindre l'extrémité d'une corde sur laquelle il progresse.
Cette corde mesure 100 m, et Léo avance à la vitesse de 1 m/h. Si rien ne s'opposait à lui, il lui faudrait donc 100 heures, soit un peu plus de 4 jours pour arriver à son but.
Ce qu'il ne sait pas encore, c'est qu'au début de chaque heure, un géant infatigable viendra tirer sur cette corde, qui se trouve être en fait un élastique infiniment extensible. A chaque fois, la corde sera étendue de 100 mètres, et ce, de façon homogène.
Cela signifie que lorsque le géant tire sur la corde, la distance qu'il restera à parcourir pour Léo augmentera, mais aussi la distance déjà parcourue. Seul le pourcentage de progression de Léo restera le même.
Notre courageux escargot est-il condamné à errer sur cette corde pour l'éternité, ou bien pourra-t-il accomplir sa mission et, si oui, après combien d'heures atteindra-t-il son but ? Pour répondre à la question, le mieux est d'observer heure après heure le périple de notre gastéropode.

Au début de la première heure, l'escargot est dans les starting blocks, et la corde mesure 100 mètres. A l'issue de cette première heure, il aura parcouru 1 mètre, ce qui représente 1% du trajet total.
Puis, le géant tire sur la corde, qui passe alors à 200 mètres. Puisque la déformation est homogène et que la corde a ici doublé en taille, chaque distance est doublée : la distance qui sépare l'escargot de son point de départ est maintenant de 2 mètres. La proportion de trajet parcourue n'a quant à elle pas changée, elle est toujours de exactement 1 %.
Durant la deuxième heure, l'escargot parcourt à nouveau un mètre supplémentaire, il aura donc parcouru en tout 3 mètres sur un total de 200, ce qui représente 1,5 % du trajet.
A nouveau, le géant tire sur la corde, qui passe de 200 à 300 mètres. La proportion de trajet parcourue par l'escargot reste constante, ce sont donc maintenant 4,5 mètres qui séparent Léo du point de départ.
Durant la troisième heure, l'escargot avance de 1 m supplémentaire, soit 5,5 mètres en tout. Puisque la corde mesure 300 mètres, cela représente 1,83 %.

Regardons un peu plus précisément la proportion de trajet parcourue par l'escargot à chaque étape.

  • La première heure, la corde mesure 100 mètres. En avançant de 1m, Léo a donc progressé de 1 %.
  • La deuxième heure, la corde mesure 200 mètres. Puisque Léo avance toujours de 1m, il progressera durant cette deuxième heure de 1/2 %.
  • La troisième heure, la corde mesure 300 mètres. En avançant de 1m, il progressera donc de 1/3 % de trajet en plus.

On peut facilement généraliser en remarquant que, à la n-ième heure, la corde mesure 100*n mètres, et Léo progressera de 1/n % de trajet supplémentaire.
Finalement, après n heure, le pourcentage de corde parcourue par Léo sera de 1 + 1/2 + 1/3 + 1/4 + ... + 1/n %
Cette somme 1 + 1/2 + 1/3+ ... + 1/n porte le nom de série harmonique, et la question est donc de savoir si elle finira par dépasser le seuil des 100 %.

Cette histoire peut rappeler l'un des 8 paradoxes de Zénon que Aristote nous a rapporté, le paradoxe de Achille et de la tortue. Dans cette histoire, Achille, le héros légendaire de la guerre de Troie, cherche à battre à la course une modeste tortue. Cette tortue marche à la vitesse de 5 m/s, tandis que Achille court à 10m/s. Pour lui laisser une chance, Achille lui laissera 5 mètres d'avance.
Une demie-seconde après que la course ait démarrée, Achille atteint le point de départ de la tortue. Pendant ce même temps, la tortue a également avancé, elle garde donc toujours un peu d'avance. Le temps que Achille atteigne cette nouvelle position de la tortue, elle aura une nouvelle fois avancé.
Zénon conclut alors que Achille ne pourra jamais dépasser la tortue, puisque celle-ci maintiendra toujours de l'avance.
Pourtant, l'expérience montre que Achille finit bien par dépasser cette tortue, il y a donc ici un paradoxe !

En fait, dans cette histoire, Achille courra, avant de rattraper la tortue, une distance en mètres égale à 5 + 5/2 + 5/4 + 5/8 + ... . Cette somme possède un nombre infini de termes. La théorie des suites géométriques permet de montrer que cette somme, même si elle semble infinie, est exactement égale au nombre 10. Il faudra donc bien une infinité d'étapes à Achille pour rattraper la tortue, mais seulement au bout de 10 mètres.
Mais le temps intervient aussi dans cette histoire. Il lui faudra une demie-seconde pour parcourir la première portion, un quart de seconde pour la deuxième portion, un huitième de seconde pour la troisième, etc. Le temps demandé pour rattraper la tortue est donc, en secondes, égal à 1/2 + 1/4 + 1/8 + ..., ce qui est exactement égal à une seconde.
D'un point de vue strictement mathématique, Achille a bien effectué une infinité de mouvements, c'est à dire 10 mètres, en un temps qui est fini.
Le paradoxe est en fait un paradoxe de physique, puisqu'il semble impossible de diviser à l'infini les distances et les temps. Le paradoxe est lui aussi philosophique, puisqu'il semble inconcevable qu'un processus ayant un nombre infini d'étapes puisse se terminer. En fait, cela prouve surtout que cet outil mathématique n'est pas le meilleur pour représenter cette situation d'une course entre un reptile et un héros mythologique.

Ce paradoxe nous apprend cependant quelque chose : une somme, même si elle possède un nombre infini de termes, peut avoir un résultat parfaitement fini. Dans le cas présent, on avait 1 + 1/2 + 1/4 + 1/8 + ... = 1.
Mais est-ce le cas pour la série harmonique 1 + 1/2 + 1/3 + 1/4 + 1/5 + ... ? Eh bien en fait... non ! Cette somme qui possède un nombre infini de termes ne peut pas être égale à autre chose qu'à l'infini !
En fait, on peut le comprendre en regroupant ensemble certains termes de la somme.

  • Prenons les termes 1/3 et 1/4. Ces deux fractions sont toutes les deux supérieures à 1/4. A elles deux, elles sont donc plus grandes que 1/2.
  • Prenons maintenant les quatre termes suivants : 1/5, 1/6, 1/7 et 1/8. Ces quatre fractions sont toutes supérieures à 1/8. A elles 4, elles sont donc plus grandes que 1/2.
  • C'est la même chose pour les 8 fractions suivantes, dont la somme est elle aussi plus grande que 1/2.

Finalement, on peut dire que la série harmonique 1 + 1/2 + 1/3 + 1/4+ ... est plus grande que 1 + 1/2 + 1/2 + 1/2 + 1/2 + .., qui, si on mène cette somme jusqu'à l'infini, est intuitivement égale à l'infini.
La série harmonique est donc finalement supérieure à l'infini : elle est donc égale à l'infini !

Revenons à Léo l'escargot : on a vu que, après n heures, son pourcentage de progression sera de 1 + 1/2 + 1/3 + 1/4 + ... + 1/n %. En marchant un nombre infini d'heures, ce pourcentage de progression sera donc infini, il y a donc forcément un moment où il dépassera le seuil des 100 %. Oui, mais quand ?...
En fait, on peut calculer qu'il faut 4 termes pour que la somme dépasse 2 %, et qu'il en faut 27 de plus pour dépasser les 4 %. Pour que cette somme dépasse 10%, il faudra additionner 12 367 termes.
Et finalement, pour que cette somme dépasse le seuil des 100% demandé, eh bien, il en faudra environ 15 septillions de termes, c'est à dire que l'escargot devra avancer pendant 15 millions de milliards de milliards de milliards de milliards d'heures, ou, plus simplement, environ 15 ×1042 heures, c'est à dire 15 suivi de 42 autres chiffres (15 092 688 622 113 788 323 693 563 264 538 101 449 859 497, pour être précis).
En gros, cela correspond à 120 milliards de milliards de milliards de fois l'âge de l'Univers.

En fait, quelle que soit la vitesse de l'escargot et quelle que soit la longueur que le géant ajoute à chaque étape, l'escargot finira par atteindre son but, même si ce temps est ridiculement grand.
Par exemple, si le géant augmentait à chaque heure la corde de 1 km au lieu de seulement 100 m, il faudrait à notre escargot environ 10343 heures pour atteindre son but.
Certains trouveront probablement à dire qu'un escargot ne peut pas vivre assez longtemps pour atteindre le bout de la corde. Mais dans le monde mathématique où il existe des hôtels avec une infinité de chambres et des troupeaux de bétail grands comme l'Univers, certains gastéropodes vivent particulièrement vieux. En fait, si il y a une chose à retenir de ce problème, c'est qu'il ne faut jamais sous-estimer la persévérance des escargots...

Posté par El Jj à 14:33 - Commentaires [2] - Permalien [#]
Tags : , , ,
08 février 2015

Deux minutes pour l'hôtel de Hilbert

Vignette

J'en avais déjà parlé sûr ce blog il y a bien longtemps, mais cette histoire d'hôtel possédant une infinité de chambre est vraiment parfaite pour aborder la notion d'infini (et s'il le faut, j'en ferai un nouvel article dans 7 ans...)

Transcription :
En 1891, Georg Cantor défraye la chronique en annonçant au monde entier que tous les infinis ne se valent pas : certains infinis seraient plus grands que d'autres.
Trente ans plus tard, David Hilbert propose lors d'une conférence sa métaphore de l’hôtel, qui permet de comprendre pourquoi l'idée de Cantor, même si elle semble paradoxale, n'a absolument rien de stupide. Ça tombe bien, j'ai environ deux minutes pour en parler.

Sur la merveilleuse planète des mathématiques, il existe quelque part un hôtel très particulier : le grand hôtel de Hilbert. Cet hôtel possède un nombre infini de chambres, numérotées 0, 1, 2, 3, etc.

Ce soir là, il est 19h, et chaque chambre est occupée. malheureusement, un nouveau client se présente à l'accueil, et désire à tout prix une chambre pour la nuit. Puisque l’hôtel est complet, la situation semble impossible, et pourtant...
Après deux minutes de réflexion, le gérant répond « pas de problème », et annonce via les hauts-parleurs de l'hôtel que chacun des clients doit changer de chambre.
Le client de la chambre n°0 doit se déplacer dans la chambre n°1, celui de la chambre n°1 ira dans la chambre n°2, celui de la chambre n°2 ira dans la chambre n°3, et ainsi de suite : le client de la chambre n°n doit se rendre dans la chambre n° n+1.
La chambre n°0 est donc maintenant libre, et le nouveau client pourra donc y loger.
On peut donc finalement dire que ∞ +1 = ∞.

Malheureusement, à 21h, ce n'est pas un nouveau client qui se présente à l'accueil, mais un bus complet qui comporte une infinité de touristes. Dans ce bus, chaque siège est numéroté 0, 1, 2, …, et chacun de ces touristes veut sa chambre. Pour le gérant de l’hôtel, ce n'est encore une fois pas un problème.
Après deux minutes de réflexion, il se saisit de son micro, et annonce aux clients de l’hôtel les nouvelles directives à suivre.
Le client de la chambre n°1 doit se déplacer dans la chambre n°2, celui de la chambre n°2 ira dans la chambre n°4, celui de la chambre n°3 ira dans la chambre n°6, et ainsi de suite : le client de la chambre n°n ira ainsi dans la chambre n°2n.
Suite à ces déplacements, les chambres numérotées par des nombres pairs sont occupées, tandis que les chambres numérotées par des nombres impairs sont maintenant libres. Le touriste de la place 0 pourra donc loger dans la chambre n°1, celui du siège n°1 ira dans la chambre n°3, celui du siège n°2 se rendra dans la chambre n°5, et ainsi de suite : le touriste du siège n°y ira dans la chambre n°2y+1.
Finalement, on vient de démontrer que ∞ + ∞ = ∞.

Le lendemain, alors que l'hôtel s'est vidé, c'est une infinité de bus contenant un nombre infini de clients qui se présentent. Les bus sont numérotés 0, 1, 2, 3, etc, et dans chaque car, les places sont numérotées 0, 1, 2, 3, etc.
Encore une fois, cela ne va poser aucun problème au gérant de l'hotel, mais les clients devront respecter ses consignes.
Dans un premier temps, le 1er client du 1er bus (c'est à dire, le client du bus n°0 et du siège n°0) ira dans la chambre n°0.
Dans un second temps, le 1er client restant dans chacun des deux premiers bus (c'est à dire, le client du bus n°0 siège n°1, et le client du bus n°1 siège n°0) iront dans les deux chambres suivantes (chambre n°1 et n°2).
Dans un troisième temps, on logera dans les trois chambres suivantes le 1er client restant dans chacun des trois premiers bus, et ainsi de suite. En suivant cette procédure, chaque client se verra assigner une chambre pour la nuit. On peut même être plus précis, et prouver que le client du bus x et de la place y sera logé dans la place n° x + ½ [(y+x)²+y+x]. Chaque client a sa chambre, et chaque chambre a son client.
On vient donc de prouver que ∞ × ∞ = ∞.

Le lendemain, l’hôtel s'est une nouvelle fois vidé, mais c'est un bus d'un tout autre type qui se présente à l'accueil : dans ce bus, les clients sont infiniment serrés, puisque les sièges sont numérotés non pas par les nombres entiers, mais par tous les nombres réels de l'intervalle [0,1]. On pourra donc parler de la place 0,5, de la place 1/3, de la place π – 3 ou de la place √2/2.
Cette-fois-ci, il y a vraiment un problème. On pourrait trouver un moyen de loger tous les clients dont le numéro du siège est un nombre décimal. On pourrait même loger ceux dont le siège est une fraction rationnelle. Mais cette foule-ci est trop dense : cet infini des nombres réels est strictement plus grand que celui des nombres entiers, et c'est à Cantor que l'on doit cette découverte.

Essayons quand même de voir ce qu'il se passerait si on trouvait un moyen de loger chacun de ces clients.
Par exemple,

  • la chambre 0 accueillera le client de la place 1/3
  • le chambre 1 accueille celui de la place π – 3
  • la chambre 2 accueille celui de la place √2/2
  • la chambre 3 accueille celui de la place 0,5

et ainsi de suite, où chaque chambre accueillera un client différent de façon à ce que chaque client soit pris en compte.
Et pourtant, même si on voulait loger tout le monde on va se heurter à un impossible : certains clients ne trouveront pas de chambre, quel que soit la façon dont on s'y prendra.
Pour le comprendre, on va fabriquer un exemple de nombre qui ne peut pas se trouver dans la liste.
Prenons la 1ere décimale du premier client, la deuxième décimale du deuxième, la troisième du troisième et ainsi de suite. Dans notre exemple, on obtient le nombre 0,3470...
Maintenant, transformons chaque chiffre du nombre ainsi obtenu : on transforme les 0 en 1, les 1 en 2, les 2 en 3, et ainsi de suite, en transformant les 9 en 0.
Dans l'exemple, on obtient le nombre 0,4581...
On peut alors affirmer que le client dont le siège porte ce numéro ne trouvera pas de place dans l’hôtel, puisque si sa chambre est la chambre n°n, alors la (n+1)-ième décimale posera forcément problème. Et ce client n'est qu'un exemple parmi l'infinité de clients qui ne trouveront pas de chambre.

Bref : l'infini des nombres réels est strictement plus grand que l'infini des nombres entiers

Une question qui a longtemps perturbé les mathématiciens est de savoir si il existe un infini intermédiaire qui serait strictement plus grand que l'infini des nombres entiers (noté ℵ0) et strictement plus petit que celui de l'infini des nombres réels (noté, 2ℵ0).
Cette question, appelée hypothèse du continue, a trouvé sa réponse en 1963, lorsque Paul Cohen annonce qu'en fait, chacun peut choisir si oui ou non, il veut de cet infini intermédiaire, et que ça ne changera de toutes façons rien au reste des mathématiques. Mais ça, c'est une autre histoire...

 

Posté par El Jj à 10:10 - Commentaires [13] - Permalien [#]
Tags : , , ,
25 janvier 2015

Deux minutes pour le théorème de Futurama

Vignette

J'avais déjà parlé des références mathématiques dans la série Futurama (là-bas), mais je n'y avais qu'à peine développé LE théorème de futurama, celui qui parle de permutation. En environ deux minutes, voilà qui est maintenant fait :

 

Transcription :
Le 19 août 2010, la chaîne américaine Comedy Central diffuse "Le prisonnier de Benda", dixième épisode de la sixième saison de Futurama, la deuxième série de Matt Groening après les Simpsons. L'épisode est exceptionnel puisque, pour la première fois à la télévision, une intrigue est résolue à l'aide d'un théorème avancé de la théorie des groupes. Il faut dire que le producteur de la série est David X Cohen, diplomé en informatique théorique à l'Université de Californie, et que l'épisode en question a été écrit par Ken Keeler, diplomé à Harvard en mathématiques appliqué.
Ca tombe bien, j'ai deux minutes pour en parler !
Dans cet épisode, le professeur Farnsworth met au point une machine à échanger les corps qui, comme son nom l'indique, permet d'intervertir le corps et l'esprit entre deux personnes.
Pour le premier essai, le professeur échange son corps avec celui de son étudiante Amy.
Le problème, c'est que à cause des défenses imunitaires du cerveau, l'échange ne fonctionne que dans un seul sens : le professeur et Amy ne peuvent pas faire l'échange contraire.
Pour retrouver leurs corps d'origine, leur seule solution est d'utiliser un corps de transition : ça sera celui du robot Bender !
C'est donc naturellement que'il accepte d'échanger son corps avec celui de Amy. L'esprit du professeur se retrouve alors dans le corps de Bender, l'esprit de Bender est dans le corps de Amy et l'esprit Amy est dans le corps du professeur.
Maintenant, si l'on échange les corps de Bender et du professeur, le corps de Bender possèdera l'esprit de Amy, et le corps du professeur retrouvera son corps original. Oui, mais, les corps de Amy et Bender ont déjà été intervertis, l'échange retour est donc impossible !

Mais les échanges ne s'arrêtront pas là, puisque /

  • Amy, échange son corps de professeur avec celui de Leela
  • Bender échange son corps de Amy avec celui du seau robotique
  • Fry et Zoidberg s'échangent leur corps
  • Bender échange son corps de seau avec celui de l'empereur Nikolaï de l'empire robot-hongrois
  • Et enfin, Amy échange son corps de Leela avec celui de Hermès.

C'est donc une dizaine de corps et d'esprit qui sont mélangés. Comment vont-ils s'en sortir ?

Ce problème s'inscrit dans le domaine de l'algèbre appellé théorie des groupes et, plus particulièrement, dans celui des permutations.

Une permutation, c'est donc l'opération qui consiste à réarranger un certain nombre d'objets. Dans le cas présent : c'est la permutation de ces 9 corps qui nous intéresse.
Une propriété essentielle de cette théorie, c'est que n'importe quelle permutation correspond toujours à la composition de une ou plusieurs permutations circulaires disjointes. Pour le comprendre, il suffit de regarder dans quel corps se trouve chacun des espritS.
L'esprit du professeur se trouve dans le corps de Bender, l'esprit de Bender est dans le corps de Nikolaï, l'esprit de Nikolaï est dans le corps du robot de nettoyage, l'esprit de ce robot est dans le corps de Amy, l'esprit de Amy est dans le corps de Hermès, l'esprit de Hermès est dans le corps de Leela, et enfin, l'esprit de Leela est dans le corps de le corps du professeur. La boucle est bouclée. A côté de cela, il reste Fry et Zoidberg, qui ont échangé leur corps indépendament du reste du groupe.
La permutation de ces 9 personnages est donc composée de deux cycles :  un cycle de 7 personnages, appellé 7-cycle et un cycle de 2 personnages, appellé transposition.
C'est finalement une suite de transposition qui a engendré la permutation finale.
La question est donc de savoir quelle est la suite de transpositions à effectuer pour que tout rentre dans l'ordre, et le nombre minimal de corps de transition à apporter.

La réponse est donnée dans la série par Sweet Clyde et Bubble Gum Tate, deux basketteurs de l'équipe des Harlem Globtrotter. Il se trouve en effet que, dans le futur, cette équipe de basket n'est composéee que de scientifiques.
Ils démontrent donc dans l'épisode que deux corps de substitutions suffisent toujours, quel que soit la façon dont les autres membres auront été mélangés, et qu'il faudra a peu près autant d'échanges que de personnages présents. C'est ce théorème que l'on appelle aujourd'hui "théorème de Futurama", que l'on doit à Ken Keeler, le scénariste de l'épisode.

Démonstration :
Procédons dans le cas où la permutation n'est qu'un simple cycle. Pour simplifier, supposons qu'il contient 5 personnes, où l'esprit de 1 est dans le corps de 2, l'esprit de 2 est dans le corps de 3, etc., et ajoutons deux nouveaux corps X et Y, qui n'ont jamais permuté avec l'une de ces 5 personnes.
Dans un premier temps, on va permuter le corps additionnel Y avec le corps 1 et X avec le corps 2.
Dans un deuxième temps, on va remonter le corps Y jusqu'à l'esprit de X. Pour cela on échange les corps Y et 5, puis Y et 4, puis Y et 3, puis Y et 2.  
Il n'y a plus qu'à échanger les corps de X et de 1 pour que les 5 premiers esprits aient retrouvé leur corps original.
A ce point, les corps de X et Y sont échangés, il suffit d'une dernière transposition pour que tout rentre dans l'ordre.

Dans le cas général, une permutation est composée de plusieurs cycles.il suffit d'appliquer cette suite de transpositions sur chacun des cycles, et le tour est joué. CQFD

On peut maintenant appliquer le théorème à la permutation des personnages de Futurama, en ajoutant les nouveaux corps de Sweet Clyde et Bubblegum Tate.
Cette permutation est composée de deux cycles : le 2-cycle Fry-Zoidberg et le 7-cycle.
Commençons par remettre dans l'ordre Fry et Zoidberg :

  • On échange Tate et Fry
  • puis Clyde et Zoidberg
  • puis Tate  et Zoidberg
  • et enfin Clyde et Fry

Fry et Zoidberg ont retrouvé leur corps, tandis que Clyde et Tate l'ont échangé. Il n'y a plus qu'à s'occuper des 7 autres personnages :

  • On échange Tate et le professeur
  • puis Clyde et Bender
  • puis Tate et Leela
  • puis Tate et Hermès
  • puis Tate et Amy
  • et ainsi de suite jusqu'à l'échange entre Tate et Bender
  • et enfin, on échange Clyde et le professeur

Chacun a retrouvé son corps, en seulement 11 échanges !

Le théorème donne donc la marche à suivre pour que chaque esprit retrouve son corps, bien que la solution ne soit pas forcément optimale, puisque ce problème aurait pu être résolu en seulement 7 opérations. Cependant, le théorème s'adapte à n'importe quel problème similaire, et pourrait un jour vous servir si vous échangez par mégarde votre corps avec celui d'un ami...


Sources :
Futurama, le prisonnier de Benda - saison 5 & 6
Keeler’s Theorem and Products of Distinct Transpositions, Ron Evans, Lihua Huang, Tuan Nguyen

Posté par El Jj à 22:27 - Commentaires [0] - Permalien [#]
Tags : , , ,
04 janvier 2015

2014+1 (Cette nouvelle année est-elle intéressante ? Episode 06)

Une nouvelle année commence, avec son lot de bonnes résolutions qui ne seront pas tenues. Par exemple, j'ai décidé, en cette nouvelle année, d'écrire enfin un article sur Maryam Mirzakhani ! Vais-je tenir cette bonne résolution ?...
En tout cas, il y a une coutume à laquelle je ne résiste pas : éplucher l'OEIS à la recherche des propriétés intéressantes du nombre correspondant à l'année qui débute. Que peut-on dire de 2015 ? Je me tourne une nouvelle fois vers l'arbitre officiel de ce qui est intéressant : l'OEIS.

Rappelons que l'OEIS est l'encyclopédie en ligne des suites entières. Si une suite de nombres (entiers) est intéressante, elle sera présente dans cette encyclopédie. Du coup, si un nombre possède une propriété intéressante, elle sera dans une suite intéressante, et donc, dans l'OEIS. Ainsi, plus un nombre apparaît dans l'OEIS, plus il pourra être considéré comme intéressant.

Les nombres 2012, 2013 et 2014 possèdent donc (au moment où j'écris cet article) respectivement 131, 104 et 88 propriétés intéressantes. Et 2015, dans tout ça ?... Eh bien...

2015 possède 170 propriétés intéressantes !

2015 sera-t-elle enfin l'année où la courbe va s'inverser ? A en croire l'OEIS, oui !..

Inversion de la courbe
Nombre de propriétés pour chaque année, selon l'OEIS

Mais voyons dans le détail ce que l'OEIS nous dit de 2015...

Arbre de diamètre 5 [A189979]
Dans un graphe, le diamètre est la plus longue distance séparant deux sommets. Par exemple, les deux graphes suivants ont pour diamètre 5 :

Graphe_7s_d5
La distance séparant deux sommets dans un de ces graphe est toujours inférieure ou égale à 5.

Ces deux graphes ne sont pas simplement des graphes : ce sont des arbres (ils ne possèdent aucune boucle - ou cycle). Et on peut en fait vérifier que ce sont les deux seuls arbres de diamètre 5 possédant 7 sommets.

On peut aussi vérifier qu'il existe 7 graphes de diamètre 5 possédant 8 sommets :

Graphe_8s_d5

Et pour les graphes de diamètre 5 possédant 18 sommets, il y en a 2015 :

Graphe_18s_d5
Un exemple parmi les 2015 existants...

Sous-réseaux tridimentionnels [A001001]
Les points à coordonnées entières dans le repère d'un plan (infini) forment ce que l'on appelle un réseau carré.
En sélectionnant ces points de façon adéquate (en ne gardant que 1 sur 2, ou que 1 sur 3, toujours de la même façon), on forme un sous-réseau. On dira que le sous-réseau est d'ordre n si on en a gardé que 1 sur n.

Ainsi, on peut fabriquer exactement 7 sous-réseaux carrés d'ordre 4, suivant la façon dont on sélectionne "un point sur 4" :

Sreseau_1004     Sreseau_4001     Sreseau_4011     Sreseau_4031     
Sreseau_2002     Sreseau_2012     Sreseau_2102

On peut en fait démontrer que le nombre de sous-réseaux carrés d'ordre n est égal à σ(n), c'est à dire, la somme des diviseurs de n. Puisque les diviseurs de 4 sont 1, 2 et 4, σ(4) = 1+2+4 = 7, ce qui est bien le nombre de sous-réseaux carrés d'ordre 4. On peut ainsi vérifier qu'il y a 6 sous-réseaux carrés d'ordre 5, et 12 d'ordre 6. Mais tout ceci n'a rien a voir avec 2015.

On peut de la même façon chercher les sous-réseaux d'un réseau cubique, à 3 dimensions (les points à coordonnées entières dans un repère de l'espace). Pour ce qui est des sous-réseaux cubiques d'ordre 2, on en dénombre 7 différents :

Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06

Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06 Screen Shot 12-28-14 at 06

Le nombre de sous-réseaux cubiques d'ordre n est en fait donné par la formule 

sum_d_sigma_d

On peut ainsi vérifier que le nombre de sous-réseaux cubiques d'ordre 3 est 13, mais surtout, que le nombre de sous-réseaux cubiques d'ordre 24 est... 2015 !

Triangles rectangles distincts [A189979]
Prenons une grille 4x4 : combien peut-on y tracer de triangles rectangles différents, à une isométrie (translation, symétrie, rotation) près ?
La réponse en gif est 9 :

Triangles_Rectangles

Et sur une grille 40x40 ?... 2015, évidemment !

 

Mais 2015 possède d'autres propriétés intéressantes !

  • [A129868] 2015, quand on l'écrit en binaire, devient 11111011111 : c'est un palindrome ! (Voir l'article de Blogdemaths pour une étude détaillée de ces nombres palindromes)
  • [A006972] 2015 est un nombre de Lucas-Carmichael. Ces nombres ont une définition proche de celle des nombres de Carmichael, qui sont les nombres qui ont l'air premier au yeux du test de primalité de Fermat (le plus classique des tests de primalité), mais qui ne le sont en fait pas du tout. Mais comme ils n'ont pas la même définition, les nombres de Lucas-Carmichael n'ont en fait aucun intérêt (sinon celui d'exister, et ça, c'est cool)
    Un nombre n, donc, est appellé nombre de Lucas-Carmichael lorsque : si p est un facteur premier de n, alors p+1 divise n+1 (il faut en plus que n soit sans facteur carré)
    2015 possède 3 facteurs premiers, qui sont 5, 13 et 31. Puisque les nombres 6, 14 et 32 sont des diviseurs de 2016, alors 2015 est un nombre de Lucas-Carmichael.
  • [A001304] Il y a 2015 façons différentes de composer un bouquet fleurs à 45 € chez un fleuriste proposant 4 types de fleurs coûtant respectivement 1, 1, 2 et 5 €.
  • [A164576] 2015 est la moyenne des 77 premiers carrés : 2015 = (1²+2²+3²+...+77²) / 77
  • [A115160] 2015 ne peut pas être écrit comme la somme de deux nombres triangulaires et d'un nombre à la puissance 4.
  • [A124189] Le nombre 1 + 2015 + 2015+ 2015+ 2015+ 2015+ 201511 + ... + 201539 est un nombre premier ! (Un point à celui qui arrive à replacer ça dans une conversation)
  • [A120828] Le nombre 109876543210987...109876543210987 (qui compte 2015 chiffres) est un nombre premier ! (Un point bonus à celui qui arrive à replacer ça en plus dans la même conversation)

Et quelques autres propriétés glanées sur Twitter aux alentours du 1er janvier :

  • 2015 = 48×48-17×17 ! Mais si vous avez trop bu et que vous lisez à l'envers, 84×84-71×71, ça fait toujours 2015. (@MickaelLaunay)
  • 2015 = 13³-13²-13¹ (@brusicor02) [A152015]

Et la santé !

Posté par El Jj à 10:00 - Commentaires [3] - Permalien [#]
Tags : , ,