Choux romanesco, Vache qui rit et intégrales curvilignes

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 : , ,
28 décembre 2014

Deux minutes pour le duc de Densmore

Cette vidéo ne contient aucun 42 et c'est une honte !

Ce sont les fêtes de Noël ! Quoi de mieux qu'une enquête policière sur fond de théorie des graphes ? !


Sources :
Qui a tué le duc de Densmore, Claude Berge, à lire à partir de la page 77

Posté par El Jj à 11:09 - Commentaires [0] - Permalien [#]
Tags : , ,


Fin »