Choux romanesco, Vache qui rit et intégrales curvilignes

03 janvier 2016

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

Une nouvelle année débute ! Je n'ai pas réellement abandonné ce blog, je suis simplement sur un projet plutôt chronophage... Mais je ne vais pas abandonner ma tradition annuelle : zieuter l'OEIS à la recherche des propriétés du nombre correspondant à l'année commençante.

Chaque année, je revêts donc mes plus beaux habits d'arithmomancien, afin de donner mes prédictions sur l'année qui arrive. Au contraire d'une Elisabeth Tessier affirmant que "la Vénus de la France, à 3° Balance [...] est en dissonance avec le thème de Daech, créé le 28 juin 2014, dans le premier décan du Cancer" pour expliquer les attentats de novembre, l'arithmomancie est une pratique divinatoire sans risque, puisqu'elle ne se risque à aucune prédiction concrète. En janvier dernier, j'affirmais sur ce blog que l'année 2015 allait être intéressante, et elle l'a été [référence nécessaire] . Qu'en est-il de 2016 ? Ouvrons pour cela l'encyclopédie en ligne des suites entières (OEIS).
Rappelons tout de même que si une suite de nombres (entiers) est intéressante, elle sera présente dans cette encyclopédie. Ainsi, plus un nombre possède des propriétés intéressantes, plus il apparaît dans l'OEIS.

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

2016 OEIS
2016 possède 783 propriétés intéressantes !

C'est absolument indubitable : l'année 2016 sera intéressante ! C'est même l'année la plus intéressante depuis (au moins) 100 ans, et pour les 100 ans à venir (à l'exception de 2048, mais j'en reparlerai dans 32 ans) ! Voyons un peu quelques raisons.

2016 est un nombre triangulaire [A000217]
Premier point important, 2016 est un nombre triangulaire, ce qui signifie que 2016 points peuvent être représentés comme ça :

2016 Triangle2016 fera mal aux yeux.

Plus précisément, on dit qu'un nombre est triangulaire si on peut l'écrire sous la forme 1+2+3+4+...+N (la forme triangulaire vient du fait que la 1ere ligne compte 1 point, la seconde 2 points, etc.). Les premiers nombres triangulaires sont donc 1, 3, 6, 10, 15, ....
Avec N=63, cela correspond à l'égalité 1+2+3+...+63 = 2016.

Puisqu'il est question de nombre triangulaire, il convient de rappeller la légende autour de l'enfance du mathématicien Carl Friedrich Gauss. Alors qu'il était âgé de 9 ans, son professeur lui aurait demandé de calculer de tête la somme 1+2+3+...+100, pensant avoir la paix durant de nombreuses minutes. Ce n'est qu'après quelques secondes que le jeune Gauss aurait répondu 5050. En fait, avec un petit raisonnement, on peut retrouver très facilement ce résultat, en formant des paires de nombres. En effet, on peut voir que 1+100=101, 2+99=101, 3+98=101, et ainsi de suite, si bien que avec les nombres de 1 à 100, on peut former 50 paires de cette forme. Cela donne finalement 50×101=5050.
Il est assez amusant de découvrir que cette histoire a progressivement évolué de biographies en biographies de Gauss, l'histoire originale ne mentionnant jamais ces nombres de 1 à 100. Dans son article Gauss's Day of Reckoning, Brian Hayes recence plus d'une centaine de versions différentes de cette même histoire !

On peut tout de même appliquer cette méthode de Gauss pour prouver que 1+2+3+...+63 = 2016. En effet, on a 1+63=64, 2+62=64, et ainsi de suite. Dans la somme 1+2+3+...+63, on peut retrouver 31 paires dont la somme vaut 64, ce qui donne 31×64=1984. Il reste à ajouter 32, le terme central de la somme (qui n'a pas été pris en compte lors des paires), ce qui donne finalement 1984+32=2016.

En généralisant le raisonnement, on peut prouver que 1+2+3+4+...+N = N/2×(1+N). Une démonstration assez classique "sans mot" de cette formule repose sur la figure suivante :

Preuve sans mots

Une autre façon de retrouver les nombres triangulaires est de passer par le triangle de Pascal, un triangle formé de nombres contruit de façon à ce que chaque terme soit la somme des deux au-dessus. Par construction, on retrouve sur la troisième diagonale la suite des nombres triangulaires.

Triangle de pascal
Le triangle de Pascal, construit de façon à ce que chaque nombre soit la somme des deux juste au-dessus (à titre d'exemple, 15+6=21, en rose)
La troisième diagonale, en bleue, correspond donc à des nombres de la forme 1+2+3+4+...+N : les nombres triangulaires.
On retrouvera donc 2016 dans la 64e ligne du triangle de Pascal.

Les nombres que l'on retrouve dans le triangle de Pascal peuvent être interpréteés d'une façon combinatoire : le nombre que l'on retrouve sur la n-ème ligne et k-ième colonne est le nombre de façons de choisir k objets parmi n possibles. Ainsi, 2016 est le nombre de façons de choisir 2 objets parmi 64.

On peut alors interpréter ce résultat en disant que 2016 est :

  • Le nombre de façons de placer deux cavaliers sur un échiquier (cela correspond à choisir 2 cases parmi les 64)

Echiquier

  • Le nombre d'arêtes d'un graphe complet à 64 sommets (chaque arête correspond au choix de 2 sommets parmi les 64), ce qui donne visuellement ceci :

G64

 

2016 est un nombre hexagonal [A000384]
Mais 2016, c'est aussi un nombre hexagonal, ce qui visuellement donne ceci :

Hexagone 2016
2016 fera vraiment mal aux yeux.

Chose intéressante : les nombres hexagonaux sont toujours des nombres triangulaires. On peut bien sûr le prouver algébriquement, mais j'espère que cette petite animation saura être plus parlante :

triangle

A noter que tous les nombres triangulaires ne sont pas pour autant hexagonaux.

On peut aussi dire que 2016 est un nombre icosikaitetragonal, puisqu'il peut être représenté sous la forme de polygone à 24 côtés [A051876] ...

2016 est un nombre presque parfait [A006516]
2016 peut s'écrire sous la forme 2016 = 25(26-1). Grâce à cette propriété, cela fait de 2016 le nombre de diagonales d'un hypercube de dimension 6. Mais ce qui est encore beaucoup plus intéressant avec cette écriture, c'est que cela correspond parfois à des nombres parfaits.

Un nombre parfait, c'est un nombre égal à la somme de ses diviseurs propres. Le nombre 28 en est un bon exemple : ses diviseurs (propres) sont 1, 2, 4, 7 et 14, et on a l'égalité 1+2+4+7+14=28.
On sait facilement construire des nombres parfaits (relaté par Euclide dès le IIIe siècle avant JC) : si le nombre 2p-1 est un nombre premier, alors le nombre 2p-1(2p-1) sera un nombre parfait. Pour obtenir 28, il suffit de voir que 23-1=7 est premier, et donc que 22 (23-1) = 28 est parfait. Réciproquement, on peut prouver que dès qu'un nombre pair est parfait, alors on pourra l'écrire sous la forme 2p-1(2p-1) avec 2p-1 premier.

Des nombres premiers de la forme 2p-1, on en connaît pas mal : 3, 7, 31, 127... Depuis 2013, on connaît 48 nombres premiers de cette forme, si bien que l'on connaît aujourd'hui 48 nombres parfaits. Ces nombres premiers de la forme 2p-1 sont ce que l'on appelle les nombres premiers de Mersenne : ils ont un intérêt tout particulier en maths, puisqu'ils fournissent les plus grands exemples de nombres dont on peut être sûr et certain qu'ils sont bien des nombres premiers. Le plus grand d'entre eux est 257 885 161-1, et compte tout de même 17 425 170 chiffres (voir là). [Mise à jour du 07/01 : on compte en fait 49 nombres parfaits, puisqu'un nouveau nombre de Mersenne premier vient d'être découvert, il s'agit de 274,207,281-1, qui compte 22 338 618 chiffres]

Les nombres parfaits gardent encore pas mal de mystères. A l'heure actuelle, on ne peut aucunement connaître le nombre de nombres parfaits qui existent.
D'un côté, il y a les nombres parfaits pairs, liés aux nombres premiers de Mersenne. Puisqu'on ne sait pas s'il existe ou non un nombre infini de nombres premiers de Mersenne, on ne peut rien dire non plus pour les nombres parfaits pairs.
De l'autre côté, il y a les nombres parfaits impairs. Là, c'est encore pire : on peut dire de nombreuses choses à leur sujet (un nombre parfait impair doit avoir plus de 1500 chiffres ou ne pas être divisible par 105, par exemple), mais le principal reste à démontrer, puisqu'on ne sait pas si des nombres parfaits impairs existent bel et bien.

Bon, par contre, 2016 peut s'écrire sous la forme 2016=25(26-1). Or, 26-1=63, ce qui n'est pas un nombre premier, donc 2016 n'est pas un nombre parfait...

2016 appartient à la "suite des cabines téléphoniques" [A192008]
En cherchant un peu, on trouve aussi des propriétés beaucoup moins utiles. Cette situation, par exemple : 

Imaginons la salle d'attente d'une administration quelconque où sont disponibles seulement 8 chaises, toutes les unes à côté des autres. Successivement, 8 personnes vont arriver dans cette pièce (et aucune ne partira avant que la pièce ne soit remplie). Lorsqu'une personne entre dans la pièce pour venir s'asseoir, elle veillera toujours à maximiser son confort personnel. Pour cela, elle ne s'installera jamais à côté d'une place déjà occupée, sauf si ces places sont les seules disponibles (dans ce cas, une place ne possédant qu'un seul voisin sera toujours préféré à une place à 2 voisins).

Salle d attente 0

Ainsi, le premier arrivant aura le choix entre 8 chaises. Imaginons qu'il prenne la troisième.

Salle d attente 1

Les chaises 2 et 4 sont maintenant indisponibles (trop proche d'une place occupée), la deuxième personne à entrer pourra choisir entre la chaise 1, 5, 6, 7 et 8. Disons qu'elle prend la 7eme.

Salle d attente 2

A présent, seules deux chaises sont encore disponibles (la 1 et la 5). Les deux prochains qui entreront choisiront donc ces deux chaises.

Salle d attente 3-4

Une cinquième personne arrive. Parmi les 4 chaises restantes, toutes ont deux voisins, sauf la dernière. C'est donc vers cette dernière que le nouvel arrivant se dirigera.

Salle d attente 5

Les trois derniers qui arriveront n'auront plus la possibilité d'obtenir des places tranquilles. Ils se partageront donc les trois dernières places restantes.

Salle d attente 6-7-8

Les chaises ont donc été choisies selon l'ordre 3, 7, 1, 5, 8, 2, 4, 6, ce qui ne représente en fait que l'une des 2016 façons de remplir toutes ces places !

 

Mais aussi...

  • Un carré magique de taille 8×8 composé uniquement de nombres premiers a au minimum 2016 comme constante magique. [A073520]

Carré magique

  • Il existe 2016 matrices 2×2 inversibles dans ℤ/7ℤ. [A000252]
  • On peut compter 2016 cellules 5D dans un hypercube de dimension 9. [A054849]
  • Le déterminant de la matrice suivante est -2016. [A092415]

matrice_det_2016

En fait, la principale raison pour laquelle 2016 possède autant de propriétés, c'est que 2016 possède énormément de diviseurs (il en possède 36 : 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 18, 21, 24, 28, 32, 36, 42, 48, 56, 63, 72, 84, 96, 112, 126, 144, 168, 224, 252, 288, 336, 504, 672, 1008, 2016). Des nombres avec autant de diviseurs, c'est plutôt rare, et cela explique sa surreprésentation dans l'OEIS. Puisque, en plus, c'est un nombre triangulaire, cela lui rajoute de nombreuses propriétés dérivées.

Bref : que cette année 2016 soit la plus intéressante pour vous.
Et surtout, la santé !

Posté par El Jj à 10:06 - Commentaires [7] - Permalien [#]
Tags : , , ,
25 octobre 2015

Pierre, feuille, ciseaux... Et après ?

Il y a de cela 8 ans, j'avais codé une version un peu trop modernisée du chifoumi, et ça ressemblait à ceci.

Ce chifoumi à 10 symboles présente un désavantage majeur : il n'est pas équitable, puisque certains symboles sont en moyenne plus forts que les autres. C'est le cas par exemple de la feuille qui gagne contre 5 des 9 autres symboles, alors que la pierre ne gagne que contre 4 des 9 autres symboles.

On peut le voir sur la matrice des gains du jeu : certaines lignes ont davantage de "1" que les autres.

Matrice gains
Matrice des gains : les "1" correspondent à la victoire du joueur, les "-1" à la victoire de l'adversaire et les "0" à une égalité.

Il n'y a qu'une seule façon de régler le problème, c'est d'ajouter un nouveau symbole qui égalise chacune des lignes et colonnes. On peut, par exemple, ajouter le lapin, qui gagnera contre la feuille, les ciseaux, le puits, le pistolet et le sataniste (les justifications sont laissées en exercice au lecteur).

Matrice gains 2
Nouvelle matrice de gain : le jeu est équilibré, puisque chaque ligne contient à présent autant de "1" que de "-1".

Mais au fait, peut-on fabriquer un jeu de Pierre-Feuille-Ciseaux avec autant de symboles que l'on veut ?

Pierre - Feuille - Ciseaux - (...) - (...)
La plus connue des variantes à 4 symboles du chifoumi est celle du "Pierre-Feuille-Ciseaux-Puits". L'ajout du symbole supplémentaire donne cependant un jeu bancal, puisque la pierre devient un symbole stratégiquement inutile (On peut même démontrer que la stratégie optimale au "Pierre-Feuille-Ciseaux-Puits" est de joueur au hasard les symboles, excepté la pierre. Un jour, promis, je ferai un article sur la théorie des jeux...).
Plutôt que de représenter les chifoumis par leur matrice de gains, utilisons plutôt la représentation sous forme de graphe. Dans un graphe de chifoumi ("graphe de tournoi équilibré"), le nombre de flèches pointant sur un sommet doit être égal au nombre de flèches qui en partent. Le graphe du "Pierre-Feuille-Ciseaux-Puits" n'est donc pas un graphe de chifoumi :

PFCP

La pierre casse les ciseaux ;
La feuille recouvre la pierre et le puits ;
Les ciseaux coupent la feuille ;
Dans le puits tombent la pierre et les ciseaux.

En fait, on peut voir facilement qu'un chifoumi ayant un nombre pair de symboles ne pourra jamais être équitable. En effet, si un nombre pair de symboles est en présence, chaque symbole pourra se battre contre un nombre impair de symboles ; impossible dans ce cas d'avoir autant de victoires que de défaites.

L'autre variante classique du chifoumi, popularisée par la série "The Big Bang Theory" est celle où l'on ajoute les deux symboles "Lézard" et "Spock". Cela produit une version à 5 symboles, qui cette fois-ci est équilibrée.

PFCLS
La pierre casse les ciseaux et écrase le lézard ;
Les ciseaux décapitent le lézard et coupent la feuille ;
Le lézard mange la feuille et empoisonne Spock ;
La feuille désapprouve Spock et recouvre la pierre ;
Spock vaporise la pierre et écrabouille les ciseaux.

Existe-t-il d'autres variantes de chifoumi à 5 symboles qui seraient radicalement différentes du Pierre-Feuille-Ciseaux-Lézard-Spock ? Eh bien... non ! On peut prendre par exemple la variante Singe-Pirate-Robot-Ninja-Zombie.

mprnz-game

Le robot écrase le zombie et électrocute le ninja ;
Le zombie attaque le singe et mange le pirate ;
Le singe trompe le ninja et débranche le robot ;
Le ninja attaque le pirate et décapite le zombie ;
Le pirate coule le robot et embroche le singe.

En procédant à un simple changement de nom, on peut voir que ces deux variantes sont en fait exactement les mêmes. On dit alors que les graphes sont isomorphes.

Isomorphisme

Isomorphisme entre les deux graphes : on commence par renommer les sommets, puis on les déplace en préservant le sens des flèches.

On peut même prouver que si on a un chifoumi équilibré à 5 symboles, il sera forcément isomorphe au pierre-feuille-ciseaux-lézard-Spock. Pour cela, prenons un chifoumi ayant 5 symboles A, B, C, D et E.
La première chose à voir, c'est que le graphe possèdera forcément un 5-cycle, de type A → B → C → D → E → A.
Dans le cas contraire, c'est que l'on a seulement  un 4-cycle A→B→C→D→A. Dans ce cas, on aura (A→C ou C→A) et (B→D ou D→B). Sans perte de généralité, supposons que l'on a A→C et B→D. Pour que le chifoumi soit équitable, il faut nécéssairement E→B et C→E, ce qui fait apparaître le 5-cycle A→C→E→B→D→A.
Bref, il y a un 5-cycle. On peut supposer sans perte de généralité que ce 5-cycle est A→B→C→D→E→A. On a alors deux possibilités : soit A→C, soit A→D. On peut alors compléter les graphes en veillant à le construire équilibré, ce qui donne les deux graphes suivants :

ABCDE

Ces deux éventualités donnent deux graphes qui semblent au premier abord différents, mais qui sont bien isomorphes, puisque le premier est isomorphe au Pierre-Feuille-Ciseaux-Lézard-Spock, et que le second l'est au Singe-Pirate-Robot-Ninja-Zombie.

Pierre - Feuille - Ciseaux - (...) - (...) - (...) - (...)
La construction précédente a le mérite de fournir une première méthode générale pour fabriquer un graphe de chifoumi avec n-symboles : il suffit de partir de n symboles disposés en cercle, et de compléter ensuite le graphe. La façon la plus simple de le compléter, c'est de relier chaque symbole aux (n-1)/2 suivants.

C'est ce qu'a fait David C. Lovelace en 2005, en fabriquant un Pierre-Feuille-Ciseaux à 7 symboles (un "7-chifoumi") ;

hands

La pierre éteint le feu, écrase les ciseaux et l'éponge ;
Le feu fait fondre les ciseaux, brûle l'éponge et le papier ;
Les ciseaux coupent l'éponge, le papier et son claquement résonne dans l'air ;
L'éponge mouille le papier, contient des trous d'air et absorbe l'eau ;
Le papier évente l'air, flotte sur l'eau et recouvre la pierre ;
L'air évapore l'eau, érode la pierre et éteint le feu ;
L'eau érode la pierre, éteint le feu et rouille les ciseaux.
Sur le cercle, chaque symbole est relié aux (7-1)/2 = 3 symboles suivants.

... puis à 9 symboles, puis à 11 symboles, puis à 15 symboles, puis à 25 symboles, et même jusqu'à... 101 symboles ! Toutes ces variantes sont créées de la même façon : les n symboles sont disposés en un cercle, ce qui forme un n-cycle, et chaque symbole bat les (n-1)/2 suivants sur ce cercle.

Autre méthode de construction. On peut fabriquer son chifoumi au fur et à mesure, en ajoutant de nouveaux symboles 2 par 2, de façon à ce que le premier symbole ajouté batte la moitié (arrondi à l'entier supérieur) des symboles préexistants, et que l'autre symbole batte la seconde moitié des symboles préexistants, ainsi que le premier symbole ajouté.

Par exemple, partons du classique Pierre, Feuille, Ciseaux. On commence par ajouter deux symboles, l'arbre et le sac plastique.

L'arbre
+ ne craint rien des ciseaux ;
+ domine la pierre ;
- n'est rien sans feuilles ;
(- est pollué par le sac plastique).
Le sac plastique
+ ramasse la feuille ;
- se fait découper par les ciseaux ;
- cède sous le poids de la pierre ;
+ pollue l'arbre.

On peut continuer, en ajoutant deux autres symboles. Disons, la hache et l'homme.

La hache :
+ déchire le sac plastique ;
+ casse les ciseaux ;
+ abat l'arbre ;
- se fait emballer par la feuille ;
- se brise sur la pierre ;
(- est manipulé par l'homme).
L'homme :
+ écrit sur la feuille ;
+ marche sur la pierre ;
- se fait étouffer par le sac plastique ;
-  se fait cisailler par les ciseaux ;
- tombe de l'arbre ;
+ manipule la hache.

PFC_7
Le graphe de mon 7-chifoumi.

Et ainsi de suite, pour fabriquer des chifoumis avec toujours plus de symboles !

On peut alors se poser la même question que précédemment. Le 7-chifoumi de Lovelace "Pierre-Feuille-Ciseaux-Air-Eau-Feu-Éponge" est-il équivalent à mon 7-chifoumi "Pierre-Feuille-Ciseaux-Homme-Hache-Arbre-Sac" ?
Cette fois-ci, non ! Et on peut même le prouver, mais il va falloir pour cela compter consciencieusement les différents 5-cycles qui apparaissent dans la structure.

Dans la première, on ne peut compter que 28 5-cycles :

PFG_2
4 des 28 5-cycles du graphe du 7-Chifoumi de Lovelace.
Les 24 autres 5-cycles se retrouvent par rotation (d'angle 360°/7).

Tandis que la deuxième, on peut en compter jusqu'à 36 :

 

PFG_1

12 des 36 5-cycles du graphe du 7-Chifoumi personnalisé.
Les 24 autres 5-cycles se retrouvent par rotation (d'angle 360°/3)

Les deux graphes n'ont pas le même nombre de 5-cycles, ils sont donc fondamentalement différents, ce qui montre qu'il existe donc au moins deux façons distinctes de construire un 7-chifoumi. Et il en existe même une troisième, celle ayant la structure du plan de Fano (évoquée déjà ici). Cette structure-ci ne peut cependant pas être obtenue par la méthode de construction itérative décrite précédemment.

Plan de Fano
Le plan de chifoumi-Fano (qui contient 42 5-cycles)

En existe-t-il davantage ? Cette fois-ci, non. Pour le prouver, il faudrait cependant montrer que chacun des 2640 graphes de 7-chifoumi est isomorphe à l'un des trois graphes précédents...

Pierre - Feuille - Ciseaux - (...) - (...) - (...) - (...) - (...) - (...) - ...
À mesure que n augmente, le nombre de graphes de chifoumi à n symboles augmente de façon drastique :

n = 1 → 1 configuration
n = 3 → 1 configuration
n = 5 → 1 configuration
n = 7 → 3 configurations
n = 9 → 15 configurations
n = 11 → 1223 configurations
n = 13 → 1495297 configurations

Pour déterminer ces valeurs, Marc Chamberland et Eugene Herman n'ont pas cherché à calculer l'ensemble des graphes de chifoumi, le temps de calcul aurait été suicidaire (à titre indicatif, il y a 9 307 700 611 292 160 graphes de chifoumi à 13 symboles, analyser chacun d'entre eux aurait demandé des temps de calculs monstrueux). Pour le prouver, ils ont plutôt tenté de déterminer les différents "profils" possibles existants pour les graphes (la façon dont les 3-cycles sont disposés les uns par rapport aux autres), ce qui leur a permis de dénombrer efficacement toutes ces configurations. On ne connaît pas aujourd'hui le nombre de chifoumi distincts à 15 symboles, mais ce qui est sûr, c'est qu'ils sont particulièrement nombreux.

Bref : si vous voulez fabriquer un chifoumi complètement inédit, il vous faudra au minimum 7 symboles !

alex_the_kidd_hamburger


Sources :
Rock-Paper-Scissors meets Borromean Rings, Marc Chamberland, Eugene A. Herman

Posté par El Jj à 10:00 - Commentaires [6] - Permalien [#]
Tags : ,
18 octobre 2015

Deux (deux ?) minutes pour Newroz

Une nouvelle fois, j'ai adapté en vidéo un ancien article. Il est aujourd'hui question de diagramme de Venn :

Vignette

 

Transcription :

En juillet 2012, Mamakani et Ruskey, deux mathématiciens canadiens, ont représenté Newroz, le premier diagramme de Venn symétrique simple à 11 pétales. Cette découverte vient poursuivre un idéal initié par John Venn en 1880 : comment représenter élégamment les situations de la théorie des ensembles à l’aide de patates. Ça tombe bien, j’ai deux minutes pour en parler !


L’histoire débute dans la deuxième moitié du 18e siècle, lorsque le génial Leonard Euler a tenté d’étudier systématiquement les syllogismes. Un syllogisme, c’est un raisonnement logique en trois temps, du style :
- Tous les Pokémon électrique peuvent apprendre l’attaque Tonnerre
- Or, certains Pokémon électriques sont aussi de type vol
- Donc, certains Pokémon de type vol peuvent apprendre l’attaque Tonnerre

Pour étudier ces syllogismes, Euler a eu l’idée brillante d’utiliser des cercles. Et quand bien même l’idée ne serait pas réellement de Euler, elle n’en reste pas moins brillante. Chaque cercle correspond à l’un des ensembles de l’énoncé. Dans l’exemple précédent, on a le cercle des Pokémon électriques, le cercle des Pokémon apprenant l’attaque Tonnerre, et le cercle des Pokémon de type vol. Si un élément est à l’intérieur d’un cercle, c’est qu’il appartient à l’ensemble, et réciproquement. La première hypothèse, qui énonce que tout Pokémon électrique apprend l’attaque Tonnerre, se traduit par deux cercles imbriqués. La deuxième hypothèse, qui nous dit qu’il existe des Pokémon à la fois de type électrique et vol, se traduit par deux cercles qui se coupent. On constate alors que le cercle des Pokémon de type vol et celui des Pokémon qui apprenant Tonnerre se coupent, ce qui explique la conclusion : certains Pokémon de type vol apprennent l’attaque Tonnerre.

Bref : les diagrammes d’Euler permettent de représenter des syllogismes avec trois cercles qui se coupent, ou pas.

Cent ans plus tard, le logicien John Venn met un coup de pied dans la fourmilière, et réinvente complètement l’idée d’Euler :
- la première révolution, c’est que les ensembles ne seront plus forcément représentés par des cercles, mais pourront prendre n’importe quelle forme patatoïde ;
- la deuxième révolution, c’est qu’on pourra se permettre d’utiliser plus que 3 ensembles ;
- mais surtout, la dernière révolution, c’est que tous les cas imaginables doivent être envisagés.

Avec les diagrammes de Venn, l’exemple précédent se traduira donc par trois ensembles qui s’entrecroisent en formant 8 zones distinctes, correspondant à l’intersection de 0, 1, 2 et 3 ensembles.

Pour illustrer le syllogisme par un diagramme de Venn, on va devoir griser les zones impossibles. Ainsi, puisque tout les Pokémon électriques peuvent apprendre l'attaque Tonnerre, on peut griser les deux zones correspondant aux ensembles uniquement électriques. La deuxième hypothèse nous donne l’existence d’un élément appartenant à la fois à l’ensemble vol et à l’ensemble électrique. La conclusion, c’est bien que cet élément appartient à l’ensemble Tonnerre.

Bref : les diagrammes de Venn permettent de représenter les syllogismes avec trois patates ou plus, mais qui se coupent tous les uns les autres en formant toutes les intersections possibles.
Soyons honnêtes, les diagrammes de Venn c’est sympa pour illustrer les syllogismes, mais c’est surtout très pratique pour illustrer des histoires d’intersections d’ensembles. Et du coup, il faut aller plus loin que 3 ensembles. On en veut 4, 5, 6 et plus ! Mais déjà, à partir de 4 ensembles, les problèmes commencent à arriver.

La première idée, c’est de placer ses 4 patates de façon symétrique, ce qui ressemble à ça.

Venn 4

Le soucis, c’est que si on compte les zones délimitées, on ne pourra en dénombrer que 14, alors que 4 ensembles donnent au maximum 16 regroupements possibles. Pour qu’un diagramme de Venn puisse être qualifié comme tel, il faut que toutes les combinaisons d’ensembles soient représentées, et il manque ici les zones correspondant à l’intersection de seulement A et B, et celle à l’intersection de seulement C et D…
Bon, en déplaçant un peu les ellipses, John Venn est parvenu à obtenir un diagramme parfait, ou chacune des 16 zones est représentée.
Pour ce qui est d’un diagramme à 5 ensembles et donc, 32 zones, Venn a proposé l’ajout d’un anneau central. Il l’a lui même reconnu, le résultat est loin d’être satisfaisant…

Venn 4 +Venn 5
Solutions de diagrammes à 4 et 5 ensembles proposés par Venn

Notons tout de même une chose : un diagramme de Venn à n ensembles présente toujours 2ⁿ zones. On peut voir ça sur l’exemple du diagramme de Venn à 5 ensembles, qui contient 1 zone extérieure, 5 zones n’appartenant qu’à 1 ensemble, 10 zones appartenant à 2 ensembles, 10 appartenant à 3 ensembles, 5 appartenant à 4 et une dernière appartenant à tous les ensembles. On a bien 2⁵, c’est à dire, 32 zones.

Il existe pourtant des méthodes pour construire des diagrammes de Venn avec autant d’ensembles que l’on veut.
La première méthode est un peu braque : on part d’un diagramme à 3 ensembles, et on y trace un chemin qui entre et sort une fois de chacune des zones alors délimitée. En procédant ainsi, on délimite un nouvel ensemble, ce qui donne bien un diagramme de Venn à 4 ensemble.
On peut alors tracer un chemin qui passe par chacune des 16 zones, et on obtient un diagramme de Venn à 5 ensembles. Ce n’est d’ailleurs que depuis avril 2015 que l’on a démontré que la méthode fonctionne toujours, mais elle fournit vraiment ce qu’il y a de pire en terme de diagramme de Venn.

On doit sinon à Anthony Edward une autre méthode particulièrement esthétique pour construire des diagrammes de Venn, en partant de deux droites perpendiculaires et d’un cercle, ce qui forme alors un diagramme de Venn à trois ensembles. Ensuite, on fabrique chaque nouvel ensemble en faisant serpenter une courbe de part et d’autre du cercle central. Cette méthode fabriquera des diagrammes de Venn avec autant d’ensembles que l’on veut.

Venn_Edward

Solution de diagramme de Venn à n ensembles proposé par Edward

Il manque un petit quelque chose à toutes ces constructions, et ce petit quelque chose, c’est que tous les ensembles ne sont pas équivalents. Ce qu’il faudrait, c’est qu’ils soient tous identiques, mais surtout, qu’ils présentent davantage de symétrie, en se regroupant en formant une fleur. On peut fabriquer des fleurs de Venn avec 2 pétales, avec 3 ou même avec 5 : pourquoi ça ne marcherait pas avec davantage ?
On dit alors que ces diagrammes sont symétriques : chaque pétale se déduit des autres à partir d’une même rotation.
Il existe d’ailleurs des diagrammes symétriques à 7 pétales, comme par exemple celui obtenu à partir de cet ensemble là, répété 7 fois par rotation.
Ce sont ces diagrammes-là, les symétriques, qui sont à mon humble avis les plus beaux !

Et des diagrammes de Venn symétriques à 4 ou 6 pétales, alors ? On en a trouvé ? Eh bien… non ! Mais pour une raison assez simple : les diagrammes de Venn symétriques ne peuvent exister que lorsque leur nombre de pétales est un nombre premier.
Pour comprendre ça, essayons de construire un diagramme de Venn symétrique avec 4 ensembles. Un tel diagramme de Venn présente forcément 2⁴ zones. On peut même détailler : il possède 1 zone n’appartenant à aucun ensemble, 4 zones correspondant à un ensemble seul, 6 zones correspondant à l’intersection de deux ensembles, 4 zones correspondant à l'intersection de trois , et enfin, une dernière zone correspondant à l’intersection des 4 ensembles.
Le problème, c’est que dès que l’on fait un diagramme symétrique avec 4 ensembles, chaque zone apparaît soit une fois, soit 4 fois. Les zones qui apparaissent une seule fois sont la zone extérieure et la zone intérieure, tandis que toutes les autres zones apparaîtront, à cause de la symétrie, toujours par paquet de 4.
Pour les zones correspondant à l’intersection de 1 ou 3 ensembles, il n’y a pas de problème, puisqu’elles sont chacune au nombre de 4. Le soucis viendra forcément des 6 zones correspondant à l’intersection de 2 ensembles : soit il manquera deux zones, soit il y en aura 2 de trop. Le problème vient donc du fait que 6 n’est pas divisible par 4.

Ces nombres 1, 4, 6, 4 et 1 sont ce qu’on appelle des coefficients binomiaux, c’est à dire, les nombres qui apparaissent dans le triangle de Pascal, un triangle composé de nombres où chacun est égal à la somme des deux nombres juste au-dessus. En l’occurrence, 1, 4, 6, 4 et 1 apparaissent sur la 4e ligne du triangle, ce qui donne la décomposition en zones du diagramme de Venn correspondant.
Une des propriétés du triangle de Pascal, c’est que sa n-ième ligne ne contient que des multiples de n dans le seul cas où n est un nombre premier. Ainsi, puisque 5 est un nombre premier, la 5eme ligne ne contient que des multiples de 5, de même que la 7e ligne ne contient que des multiples de 7. Cette condition est nécessaire à l’existence de diagramme de Venn symétrique, ce qui explique l’existence de ces diagrammes avec 5 ou 7 ensembles.
Par contre, la 4e, la 6e ou la 8e ligne contient des nombres non multiples de 4, 6 ou 8 : il est donc parfaitement inutile d’espérer pouvoir construire de beaux diagrammes de Venn avec 4, 6 ou 8 ensembles.

Bref : si un diagramme de Venn est symétrique, il contiendra forcément un nombre premier de pétales.
Rien ne dit cependant comment on peut les construire. Ce n’est d’ailleurs qu’en 1992 que le premier diagramme symétrique à 7 pétales a été découvert, par Branko Grünbaum, qui a d’ailleurs longtemps pensé qu’ils n’existaient pas. Aujourd’hui, cependant, on en connaît beaucoup plus.

Pour 11 ensembles, ça se complique encore. Le premier exemple de diagramme de Venn symétrique à 11 pétales a été découvert en 2002 par Peter Hamburger, et il ressemble à ça !

GKSentire
Diagramme de Venn symétrique à 11 ensembles

Ce diagramme a un soucis majeur : il n’est pas simple. On dit qu’un diagramme est simple quand il n’existe aucun point où plus de deux courbes se croisent en même temps. Dans le diagramme de Hamburger, on trouve des points où les 11 courbes se croisent en même temps !

Existe-t-il un diagramme symétrique simple à 11 ensembles ? Eh bien, oui, mais il a fallu attendre juillet 2012 pour le voir arriver, grâce à Kaleygh Mamakani et Frank Ruskey.

VD_11_Filled
Diagramme de Venn symétrique simple à 11 ensembles

Le résultat est superbe, mais il ouvre évidemment une nouvelle question : existe-t-il un diagramme de Venn symétrique et simple avec 13 ensembles ? Plusieurs mathématiciens sont à sa recherche, mais la question demeure aujourd’hui toujours ouverte !...


Sources :
A note on the historical development of logic diagrams : Leibniz, Euler and Venn, Margaret E. Baron
Les diagrammes de Venn, Ernest Coumet
A New Rose : The First Simple Symmetric 11-Venn Diagram, Khalegh Mamakani, Frank Ruskey,
A Survey of Venn Diagrams, Frank Ruskey, Mark Weston

13 septembre 2015

J'ai toujours rêvé d'être pentocarreleur

L'été dernier, un pavé est tombé dans la marre des pavages pentagonaux. Et le pavé en question, le voici :

Un pavé dans la mare
Oh, pavé de classe 15, tu as éclairé notre rentrée !

Ce pavé vient s'ajouter à la liste des classes de pavés convexes pentagonaux, qui en compte donc désormais 15. Peut-être en existe-t-il encore davantage, personne ne le sait, et personne n'ose vraiment se risquer à annoncer que la liste est complète... Il faut dire que l'histoire des pavages pentagonaux regorge de mathématiciens persuadés à tort d'avoir complété la liste !

Mais de quoi parle-t-on exactement ? Eh bien, de ça :

Pavage 15
Et il y en a encore qui carrellent leur salle de bain avec des tuiles carrées...

La question qui se pose est celle des pentagones qui pavent le plan : peut-on trouver des pentagones tous identiques qui peuvent recouvrir l'ensemble du plan. Bien sûr, les pentagones ne doivent pas se chevaucher (sinon, c'est trop facile) et doivent être évidemment tous de même taille.

Par soucis de simplification, on supposera aussi que les pentagones sont convexes (toutes les diagonales du polygone sont à l'intérieur de celui-ci) :

Pavage Non Convexe 1 Pavage Non Convexe 2
Exemples de pavages avec un des pentagones non convexes.
Jusqu'à présent, aucune classification des pavés pentagonaux non convexes n'a été tentée.

Le plus ancien exemple de pavé pentagonal convexe pavant le plan est le pavé du Caire : un pentagone dont les angles valent 120°, 90°, 120°, 90° et 120°. Assez étonnamment, il n'usurpe pas son nom, puisqu'on retrouve réellement des exemplaires de ce pavé dans les rues de la capitale égyptienne. Avec 4 exemplaires de ce pavé, on peut fabriquer un hexagone qui, après répétition par translations, peut paver l'ensemble du plan.

Pavages du Caire - On raconte que Ramsès II, Cléopatre, Dalida et Nagui auraient foulé ces tuiles pentagonales.
En haut à gauche : le pavé du Caire
En haut à droite : assemblage de 4 tuiles formant un motif hexagonal
En bas à gauche : le pavage du Caire
En bas à droite : pavage d'une zone résidentielle du Caire.

On s'est donc très vite posé la question : quels sont les pentagones convexes qui pavent le plan ? En fait, il en existe une infinité. Par exemple, dès qu'un pentagone a deux côtés parallèles, on peut toujours en faire un pavage.

Pavage 1 a Pavage 1 b Pavage 1 c
Plusieurs variantes du même même pavage, construit à partir d'un pavé possédant deux côtés parallèles.

Il faut donc plutôt parler de classes de pavés. Ainsi, un pavé possédant deux côtés parallèles sera rangé dans la classe #1.
La deuxième subtilité, c'est que la classification des pavés pentagonaux n'a rien à voir avec la classification des groupes de papier peint (a.k.a. "groupes cristallographiques du plan"), qui sont définitivement au nombre de 17 (démontré en 1891).
En particulier, une classe de pavé donné peut fournir des pavages appartenant à divers groupes de papier peint. Par exemple, les pavés de classe #1 peuvent aboutir à 8 types de pavages différents.

Pavage 1 pgg Pavage 1 p2Pavage 1 cm Pavage 1 pmg
D'autres exemples de pavages construits à l'aide de pavés de classe #1. 
Ces différents pavages sont sensiblement différents, puisqu'ils ne présentent pas les mêmes symétries, qui sont, respectivement, pgg, p2, cm et pmg.

La classification des pavés pentagonaux : de tempêtes en naufrages
Le premier à s'être attaqué à la classification des pavés pentagonaux est l'allemand Karl Reinhardt. Il découvre en 1918 les 5 premières classes de pentagones, et conjecture qu'il n'y en a pas d'autre ( "croyez-moi, j'ai cherché au moins une heure, et ce sont les seuls, j'en suis sûr et certain" ).

Pavé 1 Pavé 2 Pavé 3 Pavé 4 Pavé 5

Pavage 1 Pavage 2 Pavage 3 Pavage 4 Pavage 5

Les 5 premières classes de pavés pentagonaux, découvertes par Reinhardt
A noter que le pavé du Caire rentre à la fois dans la classe #2 et #4

Pendant 50 ans, le problème est resté en suspens, puisque tout le monde a fait confiance à Reinhardt. Jusqu'à ce que l'américain Richard Kershner ne découvre en 1968 trois nouvelles classes de pavés pentagonaux. Cette fois-ci, il en est sûr : il n'existe que 8 classes de pavés pentagonaux, pas une de plus ! Mais il manque de place pour le démontrer soigneusement...

Pavé 6 Pavé 7 Pavé 8

Pavage 6 Pavage 7 Pavage 8
Les classes #6, #7 et #8, découvertes par Kershner.

En 1975, Martin Gardner publie dans le Scientific American un article relatant les résultats de Kershner. Cela inspirera Richard James, qui découvre alors un nouveau type de pavé pentagonal. Pour une fois, il ne cherche pas à prouver qu'il n'en existe aucun autre.

Pavé 10  Pavage 10

La classe #10, découverte par James

En 1977, Gardner publie à nouveau un article sur les pavages pentagonaux pour évoquer la découverte de James. C'est alors que Marjorie Rice, femme au foyer sans aucune formation mathématique, tombe sur l'article, et commence à chercher de nouveaux types de pavages. Triomphe des mathématiques amateurs : elle trouvera 4 nouvelles classes !

Pavé 9 Pavé 11 Pavé 12 Pavé 13

Pavage 9 Pavage 11 Pavage 12 Pavage 13
Les classes #9, #11, #12 et #13, découvertes par Rice

En 1985, l'allemand Rolf Stein découvre un 14e type de pavage, et démontre formellement que sa liste est exhaustive... Jusqu'à ce que l'on découvre une faille dans son raisonnement...

Pavé 14  Pavage 14

La classe #14, découverte par Stein

Enfin, durant l'été 2015, un 15e pavé est découverte (avec surprise) par Casey Mann, Jennifer McLoud, et David Von Derau, une équipe de mathématiciens américains à l'aide d'une rigoureuse recherche informatique. Personne n'ose désormais se risquer à dire que la classification est terminée...

Pavé 15Pavage 15

La classe #15, découverte par Casey, McLoud et Von Derau

D'autres classifications
Ça, c'est pour la classification des pavés pentagonaux convexes. Elle n'est pas terminée, mais elle est l'objet de nombreuses recherches. On peut cependant citer d'autres théorèmes, qui permettent d'affirmer que la recherche cherche et trouve.

Par exemple, la classification des pavés pentagonaux aboutissant à des pavages "côté contre côté" (deux pavés qui se touchent partagent nécessairement une arête commune) est terminée. Ce résultat a été trouvé indépendemment en 2011 et 2012 par la russe Olga Bagina et par le japonais Teruhisa Sugimoto, et annonce qu'il n'en existe que 8 classes (les classes #1, #2,  #4, #5, #6, #7, #8 et #9).

Outre les pavés, on peut aussi classifier les pavages (un même pavé peut donner plusieurs pavages) en fonction du nombre de positions équivalentes différentes que peuvent prendre les pavés. On parle alors de pavages isoédraux, 2-isoédraux, etc.
Plus précisément, un pavage est isoédral si, quand une isométrie (rotation, translation ou symétrie) transforme un pavé en un autre pavé, elle en fait de même avec le pavage dans son ensemble. Ce sont tous les pavages unicolores des paragraphes précédents. On peut prouver qu'il existe 24 pavages pentagonaux isoédraux.

Pour les pavages 2-isoédraux (les pavés peuvent prendre deux familles de positions différentes, représentés par deux couleurs différentes), on compte aujourd'hui 97 familles différentes, mais cette liste n'a pas été démontrée comme étant complète.

Et les autres polygones ?
Mais au fait, pourquoi s'intéresse-t-on à la classification des pavés pentagonaux, et pas à celle des pavés triangulaires, quadrilatères ou hexagonaux ? Eh bien, parce que la classification des pentagones convexes est la seule qu'il reste à achever...

  • En ce qui concerne les pavés triangulaires : puisque deux triangles identiques forment toujours un parallélogramme et que les parallélogrammes pavent le plan, on peut donc conclure que tout triangle pave le plan.

Pavage Triangles
Le plus simple des pavages triangulaires, construit à partir d'un triangle quelconque.

  • Pour ce qui est des quadrilatères : là aussi, on peut prouver que n'importe quel quadrilatère (même non convexe) pave toujours le plan, et de façon périodique.

Pavage Quadrilatères
Exemple de pavage construit à partir d'un quadrilatère quelconque

  • Ensuite, on peut démontrer que les pavés hexagonaux convexes se divisent en seulement trois classes :

Pavé hexagonal 1 Pavé hexagonal 2Pavé hexagonal 3
Pavage hexagonal 1 Pavage hexagonal 2 Pavage hexagonal 3
Les trois classes de pavés hexagonaux

  • Enfin, pour les polygones convexes à 7 côtés ou plus, un théorème démontré par Niven en 1978 montre que ces polygones ne peuvent pas paver le plan.

Bref : les mathématiciens travaillent d'arrache-pied pour vous proposer un choix exhaustif en terme de carrellage de cuisine et de salle de bain. Voilà pourquoi toute avancée sur le sujet doit être accueilli à bras ouverts !


Sources :
Les pavages du Caire, A. El Kamici
Les pavages pentagonaux, une classification qui s'améliore, J.-P. Delahaye
L'énigme des pentagones, E. Ghys
Pentagonal tiling, Wikipédia

Images :
Toutes les illustrations des pavages proviennent de l'applet de Jaap
Les pavages du Caire

Posté par El Jj à 10:00 - Commentaires [2] - Permalien [#]
Tags : , , ,
05 septembre 2015

Deux (deux ?) minutes pour le IIIe problème de Hilbert

La mathématiciens adorent faire des découpages ! La preuve, avec ma dernière vidéo !

Vignette

Mes excuses par avance pour le sous-mixage de ma voix...

Transcription :
Durant l’été 1900, l’extraordinaire David Hilbert propose à la communauté mathématique une liste de 23 problèmes dans le but de diriger la recherche sur le siècle à venir.  Entre des problèmes très profonds sur le calcul variationnel ou sur la consistance des axiomes de l’arithmétique, on retrouve un semble-t-il innocent problème sur la géométrie des puzzles, le troisième problème de Hilbert. Ça tombe bien, j’ai deux minutes pour en parler.

Que l’on fasse des mathématiques en CM1 ou en master 2, tout calcul d’aire ou de superficie s’appuie sur la même formule de référence : la formule de l’aire d’un rectangle : longueur fois largeur.

À partir de cette simple formule et d’un peu de découpage, on peut retrouver les formules classiques de tous les autres polygones : triangles, parallélogrammes, trapèzes etc.
Par exemple, l’aire d’un triangle est la longueur b de sa base multipliée par sa hauteur h et le tout divisé par 2. Dit autrement, l’aire de deux triangles, c’est l’aire d’un rectangle de longueur b et de hauteur h, ce qu’un habile jeu de puzzle permet de confirmer.
De même, l’aire d’un parallélogramme est égal à sa base b multipliée par sa hauteur h. Un découpage particulièrement malin permet de le démontrer aussi.
On peut faire le même raisonnement puzzle pour montrer que l’aire d’un trapèze est égal à la somme des longueurs a et b des côtés parallèles, multiplié par la hauteur h et divisé par 2. En effet, en découpant deux trapèzes identiques, on peut parfaitement placer les morceaux dans un rectangle de longueur a+b et de largeur h.

Bref, le découpage semble une méthode particulièrement efficace pour retrouver l’aire d’un polygone. Mais on peut se poser la question contraire : peut-on toujours, par ce jeu de tangram, transformer n’importe quel polygone en rectangle ou, encore mieux, en carré ?
Transformer un objet mathématique en un carré de même aire, cela porte un nom : c’est ce que l’on appelle une quadrature. La question qui se pose donc ici est de savoir si il est possible de réaliser la quadrature de n’importe quel polygone par simple découpage.

Par exemple, un triangle équilatéral de côté 2 cm a pour aire √3 cm². Il a donc la même aire qu’un carré de côté √√3. La question que l’on en droit de se poser, c’est de savoir si il y a moyen de découper le triangle de façon à obtenir le carré ?
Et, bien sûr, moyen il y a, et en seulement 4 pièces. On attribue ce découpage à Henry Dudeney, que j’avais évoqué dans la vidéo sur l’énigme des 3 maisons.

Fort de ce succès, posons nous une autre question. Peut-on découper un hexagone régulier de façon à former un carré ? Pour cela, on peut partir d’un hexagone régulier de côté 2, et chercher à former donc un carré de côté √(6√3).

Encore une fois, c’est possible ! Et on peut le faire en seulement 5 morceaux, bien que le découpage est loin d’être évident.

On peut renouveler l’expérience avec un heptagone régulier, à 7 côtés. En seulement 7 pièces, il est aussi possible de le découper en un carré.

Des quadratures comme celles-ci, Gavin Theobald s’en est fait sur son site sa spécialité. On peut y trouver par exemple le découpage d’un polygone régulier à 54 côtés en un carré, et en seulement 24 pièces.

Mais tout ça, ce ne sont que des exemples ! Est-il possible de le faire de manière générale, sur n’importe quel polygone ? Eh bien… oui ! La question a été posée par Farkas Bolyai à la fin du 18e siècle, et William Wallace l’a démontré au début du 19e. Ignorant la démonstration de Wallace, Paul Gerwien l’a redémontré dans les années 1830. Dans tout ça, Bolyai finit par trouver tout seul une réponse à sa question dans les mêmes années 1830, ignorant que deux autres mathématiciens l’avaient fait avant lui. C’est ainsi que le théorème sera finalement baptisé théorème de Wallace-Bolyai-Gerwein.

Pour transformer un polygone en carré, la méthode est la suivante :
- on commence par trianguler le polygone, c’est à dire, le découper en plusieurs triangle.
- ensuite, on découpe chaque triangle de manière à former des rectangles
- on découpe ensuite chacun de ces rectangles de façon à obtenir un carré.
- Et enfin, on découpe deux à deux ces petits carrés de façon à recomposer un carré plus grand.
Toutes ces opérations peuvent être faites quelles que soient la forme des triangles initiaux, si bien que, en suivant pas à pas cette méthode, on peut transformer n’importe quel polygone, aussi tordi soit-il, en un carré de même aire. CQFD.

Le principal désavantage de cette méthode, c’est qu’elle produit des découpages avec un nombre de pièces qui peut être très grand. Mais la méthode fonctionne tout le temps, et c’est quand même la seule chose qu’on lui demande.

Dans toute cette histoire, il y a une quadrature dont je n’ai pas encore parlé : celle du cercle. Est-il possible de découper un disque de façon à obtenir un carré de même aire ? Contrairement à une rumeur particulièrement tenace, cette quadrature du cercle est parfaitement possible. Le premier soucis, c’est que le découpage découvert par Tarski demande environ 10^50 morceaux. Le deuxième soucis, c’est que ces morceaux ont des formes qui n’existent que dans le monde mathématique, et ne peuvent être réellement découpées avec de simples ciseaux. Une sombre affaire d’axiome du choix que j’évoquerai probablement dans une autre vidéo.
De toutes façons, un disque n’est pas un polygone, donc cette quadrature bordeline ne remet pas du tout en cause le théorème de Wallace Bolyai Gerwein.
Attention cependant à ne pas confondre cette quadrature du cercle par découpage, qui est possible sous certaines hypothèses, avec la quadrature du cercle classique à la règle et au compas, qui, elle, effectivement, a été démontrée comme étant impossible.

Bref : tout polygone peut être ramené par découpage à un carré. Autrement dit, toutes les formules de calculs d’aire des polygones peuvent être démontrées par de simples découpages.

Bon, tout ça, c’était pour les polygones figures en dimension 2. Mais retrouve-t-on la même chose avec les polyèdres, c’est à dire, avec les formes géométriques en 3 dimensions ?

Revenons un peu sur les formules de volumes. Les polyèdres de base, ce sont le cube, dont le volume est égal à son côté, élevé au cube, et le pavé droit, dont le volume est le produit de ses 3 côtés. Il y a aussi les prismes, dont le volume est égal à l’aire de leur base, multipliée par leur hauteur.
Et puis, il y a les pyramides. Le volume d’une pyramide est donné par l’aire de sa base, multipliée par sa hauteur, le tout divisé par 3. Cette formule fonctionne sur tous les types de pyramides, qu’elles soient à base triangulaire, carré ou polygonale, qu’elles soient droites ou qu’elles soient obliques.

Ce que nous dit donc cette formule, c’est que le volume de trois pyramides est égal au volume d’un prisme droit de même base et de même hauteur

Prenons par exemple trois pyramides dont la base est un carré, et telles que deux de ses faces latérales soient des triangles rectangles isocèles. D’après la formule, chaque pyramide a pour volume le tiers du volume d’un cube de même base. Avec trois pyramides, on a donc le même volume que dans ce cube. Eh bien, cette propriété se retrouve par le découpage, puisque en assemblant ces trois pyramides de la bonne façon, on se retrouve avec notre cube.

Prenons maintenant une pyramide droite dont la base est une nouvelle fois un carré, et dont la hauteur est égale à son côté. D’après la formule, cette pyramide a exactement le même volume que la pyramide oblique de l’exemple précédent. Rien n’empêcherait donc a priori que l’on puisse découper la première pyramide de façon à obtenir la deuxième. Et pourtant, après de bien nombreux découpages infructueux, Gauss a fini par conjecturer dans la première moitié du 19e siècle que le problème était impossible, sans réussir à le démontrer.

La question donc que pose Hilbert en 1900 est la suivante : existe-t-il des polyèdres non congruents ? Quand Hilbert parle de polyèdres congruents, il en entend que l’un peut être découpé en petit polyèdres de façon à reformer l’autre.
Par exemple un prisme à base hexagonale et un cube sont congruents, dès lors qu’ils ont le même volume.
La réponse à la question de Hilbert ne se fera pas attendre très longtemps, puisque c’est l’un de ses étudiants, Max Dehn, qui donnera la réponse en 1901 : il existe bien des polyèdres non congruents, et les deux pyramides en sont un exemple.

Pour le prouver, Dehn a construit sur les polyèdres ce que l’on appelle un invariant.
En mathématiques, un invariant est une quantité qui ne change pas malgré des transformations. Ainsi, si deux objets n’ont pas le même invariant, c’est que l’un ne peut pas être transformé en l’autre.

Reprenons l’exemple des polygones, et la transformation qui consiste à découper puis recomposer un autre polygone. On peut imaginer plusieurs quantités qui peuvent prétendre au statut d’invariant, comme par exemple la somme des angles ou la somme des longueurs. Le problème, c’est que ces quantités sont modifiées lors d’un découpage: ce ne sont donc pas des invariants pour cette transformation. Au contraire, l’aire du polygone est une quantité qui ne change pas quel que soit le découpage que l’on fait : l’aire est bien un invariant.
On a même montré plus, avec le théorème de Wallace-Bolyai-Gerwien, cet invariant est caractéristique de la congruence des polygones. Si deux polygones ont la même aire, alors ils sont congruents, et réciproquement.

En 3 dimensions, le problème est un peu plus compliqué. La mesure du volume est bien un invariant, puisqu’après un découpage-recollage, un polyèdre garde bien entendu le même volume. Cependant, cet invariant n’est pas caractéristique, il est nécéssaire, mais pas suffisant. Rien ne prouve que si deux polyèdres ont le même volume alors ils sont congruents. Il faut donc trouver quelque chose de plus spécifique aux découpages 3D, et c’est que Dehn a découvert : ce sont les angles !
Alors, il est hors de question que je rentre dans les détails de la construction de Dehn, puisqu’elle utilise des structures algébriques qui sont très loin d’êtres triviales. On peut quand même dire dans les très grandes lignes que l’invariant caractéristique de la congruence, c’est la famille d’angles qui apparaît dans le polyèdre.

On parle pas ici des angles des faces, mais des angles dièdres, c’est à dire, les angles formés entre les différentes faces du polyèdre.
Par exemple, tous les angles dièdres du cube sont des angles droits.
Dans un prisme régulier à base triangulaire, les angles dièdres qui apparaissent mesurent, en radian, pi/2 et pi/3. Dans la première pyramide, oblique et à base carré, les angles dièdres qui apparaissent mesurent en radian pi/2, 2 pi/3 et pi/4. Dans tous ces cas, les angles appartiennent à la même famille, celle des angles qui sont en radians une fraction rationelle de l’angle pi.
D’après le théorème de Dehn, tous ces polyèdres ont le même invariant caractéristique, et sont donc congruents.

Par contre, les angles dièdres de la pyramide droite valent arctan(2) etarctan(4/3), des angles qui ne peuvent pas être écrits en radian comme une fraction de pi. Il s’agit donc ici d’une toute autre famille d’angles. Cette deuxième pyramide n’a donc pas le même invariant de Dehn que le cube ou que la première pyramide, il est donc rigoureusement impossible de former par puzzle un cube à partir de morceaux découpés dans cette pyramide.

Bref. Quand Euclide a démontré pour la première fois les formules d’aires et de volume dans les années 300 avant JC, il a utilisé essentiellement des méthodes de découpage pour déterminer les aires des polygones. Pour ce qui est du calcul des volumes des cônes, pyramides et autres cylindres, Euclide n’est pas parvenu à procéder par découpage, et a du utiliser la méthode d’exhaustion, qui, sans rentrer dans les détails, est un ancêtre du calcul intégral que l’on utilise aujourd’hui pour faire les calculs de volume. Ce n’est donc que 2200 ans plus tard que l’on a enfin pu démontrer une bonne fois pour toute que si Euclide a du procéder ainsi, c’est simplement parce qu’il n’avait pas eu d’autre choix.


Sources :
Geometric dissection - Le site de Gavin Theobald
Hilbert's third problem and Dehn's invariant - UMN Math Club
Dissections géométriques - Jean-Paul Delahaye

Posté par El Jj à 19:55 - Commentaires [3] - Permalien [#]
Tags : , , , ,
29 juin 2015

Deux (deux?) minutes pour la suite de Conway

C'est un sujet que j'ai déjà abordé au moins deux fois sur le blog, mais j'adore cette suite ! Voici donc la suite de Conway, en vidéo !

Vignette

Transcription augmentée :
En 1992, Bernard Werber publie "le jour des fourmis", deuxième épisode de sa célèbre trilogie des fourmis. Dans ce roman, il met en scène l’énigme suivante : complétez la suite 1, 11, 21, 1211…
En fait, cette suite a été inventée et étudiée 10 ans plus tôt par le génial John Conway et regorge de surprises mathématiques insoupçonnées.
Ça tombe bien, j’ai deux minutes pour en parler.

Donnons tout de même la clé de l’énigme : comment est-on sensé compléter la suite 1, 11, 21, 1211 ? Eh bien, dans cette suite, chaque terme s’obtient en regardant puis en lisant à voix haute le terme précédent, en débutant par le terme 1. En regardant ce premier terme, on voit donc une fois le chiffre 1, ce qui se lit donc “un 1”. Maintenant, en regardant le nombre 11, on voit deux fois le chiffre 1. On lit donc “deux 1”. On continue de la même façon en lisant “un 2" puis "un 1”. Pour compléter cette suite, il faut donc dire “un 1, un 2 et deux 1”.
Pour générer la suite, il suffit de la regarder et de la lire, c’est pourquoi Conway l’a baptisé la suite “Look and say”. Cette suite entretient des liens très métaphoriques avec les éléments chimiques et leur désintégration naturelle, si bien qu’elle porte aussi le nom de “suite audioactive”.

On pourrait s’arrêter à cette simple devinette, mais ça serait passer à côté de ce qui fait tout son charme mathématique. Tiens, par exemple, peut-on trouver le chiffre 3 dans la suite ?
Eh bien, oui, et il ne suffit pas d’aller chercher plus loin, puisque le chiffre 3 apparaît pour la première fois lors du 6eme terme, puis ne disparaît plus jamais après.
Et le chiffre 4, alors, peut-il apparaître ? Là, il faut réfléchir un peu plus. Pour apparaitre, il faudrait que le terme précédent possède 4 chiffres identiques consécutifs, comme 1111, 2222 ou 3333.
Mais pour que la chaîne 1111 apparaisse, il faudrait que la ligne précédente soit 11. Sauf que 11 ne se lit pas 1111, mais 21. Bref, la chaîne 1111 ne peut pas apparaître !

[Petit apparté : pour démontrer complètement, il faut également penser à l’enventualité où 1111 apparaîtrait sous la forme (x1) (11) (1y). Mais on peut facilement voir que c’est aussi impossible.]

On peut faire le même raisonnement pour 2222 et 3333, ce qui explique que le chiffre 4 ne peut pas apparaître naturellement dans la suite.  C’est ce que Conway appelle le “théorème du jour 1”, qui permet de dire que quatre chiffres consécutifs ne peuvent pas apparaître dans la suite, et que l’on est donc restreint à utiliser les chiffres 1, 2 et 3.

Bien sûr, on peut toujours s’arranger pour faire apparaître un peu ce que l’on veut dans la suite, il suffit pour cela de changer la graine de la suite, c’est à dire, son terme initial. Si je pars de la graine 42, je vais forcément trimballer ce chiffre 4 tout au long de la suite. Mais malgré la possibilité de choisir la graine que l’on veut, 4 chiffres identiques n’apparaîtront jamais consécutivement. Jamais !

Mais les motifs 1111, 2222 ou 3333 ne sont pas les seuls motifs qui n’apparaissent jamais. On peut aussi citer le motif 333 ou 313… John Conway a catégorisé ces motifs impossible sous le nom de théorème du jour 1 et théorème du jour 2.  Mais ce qui est encore plus intéressant que les motifs qui n'apparaissent pas, ce sont les motifs qui apparaissent effectivement. Le théorème qui régit ces motifs possibles porte le nom de théorème du jour 24, ou un peu moins prosaiquement, le théorème cosmologique !

Pour comprendre ça, reprenons la suite de graine 1. A partir de la septième étape, on obtient 11 13 21 32 11. Ce qui est intéressant, c’est que à partir de cet instant, la suite va se scinder en deux parties indépendantes, entre le chiffre 2 et le chiffre 1. Si on ne s’intéresse qu’à la partie de gauche, on peut voir que le dernier chiffre sera toujours le chiffre 2. Du côté de la partie droite, la suite commence par 13. A l’étape suivante, elle commencera donc par 1113, puis 3113, puis retombe à nouveau sur quelque chose qui commencera par 13. La boucle est bouclée, et le chiffre 2 n’apparaîtra donc jamais au début de cette suite de droite, empêchant toute possibilité de raccorder les deux parties. Bref : à partir de cette septième étape, la suite de Conway se scinde en deux sous-parties indépendantes. En poussant un peu plus loin les investigations, on peut voir que quelques étapes plus tard, c’est en 3 sous parties que la partie de gauche se scinde, et ainsi de suite.

Mais ce phénomène ne fonctionne pas seulement pour la suite débutant par 1, mais pour n’importe quelle graine. En partant de 2, la scission apparaîtra à partir de la 7e étape. En partant de la graine 3, il faut attendre seulement 6 étapes.
On peut alors regarder les différentes sous-parties qui peuvent se former après chaque scission. En observant attentivement, on peut s’apercevoir que ce sont toujours les mêmes motifs qui apparaissent et qui s’enchaînent.

Ces motifs se dénombrent, et on peut montrer qu’il en existe exactement 94 ; et c’est d’ailleurs parce qu’il y en a 94 que Conway a appelé chaque motif par le nom d’un des 94 éléments chimiques naturels. C’est ainsi que le motif 32 11 2 est appelé Cobalt, ou que le motif 11 12 est baptisé Potassium. Certains éléments sont cependant un peu plus complexes que d’autres…

Tableau périodiqeLe tableau périodique des 94 éléments audioactifs de Conway (clic doit / ouvrir dans un nouvel onglet, pour voir en encore plus grand !)

[Petit apparté : comment ont été associé chaque élément à chaque séquence ?
En analysant les différentes séquences indécomposable de la suite comme 22 ou 13, Conway s'est aperçu qu'il y en avait 94. Du coup, il a simplement associé de manière arbitraire chaque séquence à chaque élément chimique.
En fait, ce n'est pas fait de manière totalement arbitraire : le tableau est construit de telle façon que dans la décomposition de chaque atome, on retrouve l'atome qui lui précède. Ainsi, l'atome n°92 (U) devient le n°91 (Pa), qui devient le n°90 (Th), et ainsi de suite. Le n° 86 (Rn) se décompose en deux atomes différents. Il a été décidé que l'un d'entre eux serait le n°85.

Notons quand même que Wikipédia indique seulement 92 éléments dans le tableau de Conway. Il y en a pourtant 94, qui comprennent 92 éléments communs, auxquels s'ajoutent deux éléments transuraniens, seuls élément qui contiennent d'autres chiffres que 1, 2 ou 3. Du coup, ces deux derniers éléments n'apparaissent que lorsque la graine contient un 4, un 5 ou autres.]

Ainsi, si on reprend la suite de graine 1, on peut voir qu’au moment de sa scission à la septième étape, la suite devient un alliage de Hafnium (11 13 2) et d’Etain (1 32 11). A l’étape suivante, le Hafnium se désintègre en Lutécium (31 13 12) tandis que l’étain devient de l’Indium (11 13 12 21). A l’étape suivante, on obtient un alliage Ytterbium - Cadmium, puis un alliage Thulium - Argent, et enfin, un impressionnant composé Erbium - Calcium - Cobalt - Palladium. Après 37 étapes, chaque élément du tableau périodique de Conway est apparu au moins une fois dans la suite, et après seulement 44 étapes, la chaîne est composé de quasiment 31 000 éléments, où chaque élément commun apparaît au moins une fois.
A noter tout de même que, avant d’atteindre sa septième étape, la graine passe par une phase où les termes de la suite ne sont composés d’aucun élément du tableau périodique : ces éléments que sont 1, 11, 21 ou 1211 sont appelés des éléments exotiques, et il en existe une infinité, puisqu’ils dépendent du choix de la graine initiale. Heureusement, quelle que soit la complexité de la graine initiale choisie, ces éléments exotiques sont toujours condamnés à la disparition, au profit d’un assemblage des 94 éléments naturels.

C’est cette propriété que Conway appellera le “théorème cosmologique” :
quelle que soit la graine que l’on choisit au départ, elle finira tôt ou tard par être composée uniquement d’éléments naturels qui n’interagisse pas les uns avec les autres. Exceptée bien sûr cette inutile suite débutant par 22.
Il semble même que l’on peut prouver qu’il faut au maximum 24 étapes avant qu’une graine se soit complètement transformé en un alliage d’éléments naturels, et 44 étapes supplémentaires avant que chaque élément commun n’apparaisse quelque part dans l’alliage.

Une conséquence du théorème cosmologique est l’existence d’une constante d’expansion : à chaque étape, le nombre de chiffres est, en moyenne, multiplié par 1.3(03577)…. Ce nombre correspond à l’unique racine d’un polynôme de degré 71. C’est peut-être un détail pour vous, mais l’existence d’un problème où la solution est la racine d’un polynôme de degré 71, pour les mathématiciens, ça veut dire beaucoup.

Le théorème cosmologique a été prouvé pour la première fois en 1987 par John Conway. Malheureusement, sa démonstration manuscrite a été perdue. Heureusement, Mike Guy, qui travaillait avec lui, l’a lui aussi démontré, prouvant au passage que toute graine devient un alliage d’éléments naturels en moins de 24 étapes. Malheureusement, cette démonstration manuscrite a elle aussi été perdue. La malédiction sera levée par Ekhad et Zeilberger, qui prouvent une bonne fois pour toute le théorème cosmologique en 1997.
Mais le type de démonstration utilisé pour ce théorème a longtemps fait débat dans la communauté mathématique, puisqu’une énorme partie de la démonstration passe par l’énumération exhaustive de tout un tas de suites. Une telle énumération serait particulièrement laborieuse à faire à la main, si bien que cette partie du travail a été confiée à un ordinateur.
Pour beaucoup de mathématiciens, laisser un ordinateur faire une démonstration mathématique peut être considéré comme une hérésie. C’est d’ailleurs pour cela que Thomas Hales, après avoir démontré la conjecture de Kepler en 1998 à l’aide de l’outil informatique a passé 16 ans supplémentaires à démontrer formellement que sa preuve est bien correcte.
On ne compte plus aujourd’hui les théorèmes qui s’appuient sur l’ordinateur, comme le théorème des 4 couleurs, la solution optimale d’un Rubik’s cube ou la non existence de plan projectif fini d’ordre 10. Aujourd’hui, ces démonstrations à forte teneur informatique font l’objet d’un consensus, et sont davantage acceptées. Surtout quand, à côté de ça, des démonstrations comme celle de la classification des groupes finis pèse plusieurs milliers de pages, et demande des années pour être complètement validée.

Bref : le théorème cosmologique explique finalement que dans un univers régit uniquement par la suite audioactive, n’importe quelle graine finit par engendrer la création de l’Univers tout entier. Ça a quand même plus de gueule qu’une théorie des Bogdanov !


Testez la suite de Conway avec la graine de votre choix (attention : l'algorithme ne fonctionne pas de manière optimale avec des chiffres supérieurs à 4, et n'est pas à l'abri de bugs pour cause de programmation faite à la va-vite).

Graine :
Nombre d'étapes :




Sources 
Oscar Martin, Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA, dont l'introduction est très complète
Henry Bottomley, Seven complete sequences for the Conway Look and Say elements
Nathaniel Johnston, A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial
John Conway, Weird and wonderful chemistry of audioactive decay

Posté par El Jj à 12:28 - Commentaires [5] - Permalien [#]
Tags : , ,