Choux romanesco, Vache qui rit et intégrales curvilignes

11 mai 2008

Vous n'y échaperez pas !

Les nombres premiers ! 25 000 ans après avoir été découvert, 2 300 ans après avoir été étudiés et 30 ans après leur avoir trouvé une utilité dans la vie de tous les jours (la fameuse "utilité" des mathématiques...), les nombres premiers sont une source inépuisable de conjectures et de théorèmes !
Très présents dans les recherches actuelles, les énoncés sur lesquels les mathématiciens se cassent la tête ont souvent la particularité d'être d'une simplicité déconcertante (Je ne classe pas l'hypothèse de Riemann comme un énoncé simple).

Aujourd'hui, donc, un petit article à propos de ces 26 nombres premiers que l'on ne peut pas rater, les "nombres premiers inévitables" !

Jeffrey Shallit (informaticien et théoricien des nombres) a introduit le concept des nombres inévitables. Dans le mot "CHOUXROMANESCO", on peut par exemple retrouver le mot "CRANE", lorsque l'on enlève certaines lettres. On peut dire que le mot "CRANE" est inclus dans le mot "CHOUXROMANESCO" (en ne touchant pas à l'ordre des lettres).
Si on peut le faire avec des lettres, on peut le faire avec des chiffres : par exemple, un nombre tel que 19843 contient (entre autres) les nombres 184, 983 ou 4.
Pour un nombre premier donné, on peut se poser la question des nombres premiers qui y sont inclus. Prenons 19843, qui est premier. Il contient les nombres 3, 13, 19, 43, 83, 193 et 983 qui sont premiers. Dans le nombre premier 946649, par contre, il n'y a aucun "sous-nombre" qui soit premier.

La question que s'est posé Shallit (en 1996) était de savoir si il existe une famille (finie) de nombres premiers tel que tout nombre premier contienne l'un des nombre de cette famille (ou en fasse partie). De manière équivalente, on peut se demander si il existe un nombre infini de nombre comme 946649 qui ne contiennent aucun autres nombres premiers.

La réponse fut apportée rapidement par Lothaire (en 1983, avant que Shallit ne se pose la question, en fait...), avec un théorème de la théorie des langages formels (la théorie mathématique qui étudie les ensembles de chaînes de caractères (ou "motifs")). Ce théorème dit que si on prend un ensemble infini de motifs, il existera toujours un de ces motifs qui sera inclus dans un autre.
Appliqué à la question de Shallit, (ici, les "motifs" sont les nombres écrits en base 10), on peut conclure qu'il existe bien un nombre fini de nombres premiers que l'on retrouve dans n'importe quel autre nombre premier. Ces nombres sont appelés "nombres premiers inévitables". (On peut dire la même chose de n'importe quel ensemble de nombres)

Nouvelle question alors : quels sont ces nombres ?
Un algorithme nous donne la solution : L'idée pour les trouver tous est de passer en revue tous les nombres premiers, et de ne garder que ceux qui n'en contiennent pas d'autre :

2 : on garde
3 : on garde
5 : on garde
7 : on garde
11 : on garde
13 : on ne garde pas, il contient 3
17 : on ne garde pas, il contient 7
19 : on garde
23 : on ne garde pas, il contient 2 et 3

Et ainsi de suite. On sait que l'ensemble des nombres que l'on va garder, les "nombres premiers inévitables" est fini, donc on devrait les avoir tous au bout d'un certain temps grâce à cet algorithme...
Reste à savoir quand il faut s'arrêter de tester les nombres de l'ensemble... En fait, on ne peut pas savoir quand l'arrêter : ce n'est pas parce que l'ordinateur ne trouve pas de nouveaux nombres inévitables qu'il n'en existe pas d'autres très grands.

Pour les trouver tous, il faut donc procéder autrement, et raisonner plutôt que de chercher à la brutale.
L'exemple simple est celui des nombres pairs : il est facile de voir que l'ensemble {0,2,4,6,8} est l'ensemble des nombres pairs inévitables, puisque tous les nombres pairs finissent par l'un de ces chiffres. En associant le raisonnement et la méthode algorithmique, on peut trouver les multiples de 4 inévitables : ils sont forcément inférieurs à 100 (un nombre est divisible par 4 si ses deux derniers chiffres forment un nombre divisible par 4), et l'algorithme permet de trouver que ces nombres sont {0, 4, 8, 12, 16, 32, 36, 52, 56, 72, 76, 92, 96}.

Le raisonnement est beaucoup plus compliqué pour celui des nombres premiers, mais Shallit l'a fait pour nous. On connait alors la liste des nombres premiers inévitables :

{2, 3, 5, 7,
11, 17, 19, 41, 61, 89,
409, 449, 499, 881, 991,
6469, 6949, 9001, 9049, 9649, 9949,
60649,
666649, 946649
,
60000049, 66000049, 66600049}

L'utilité de cette découverte à propos des nombres premiers reste essentiellement esthétique ! Ces 26 nombres premiers ressortent "miraculeusement" du lot de tous les nombres premiers (pour nous, qui voyons le monde en base 10).
On voit quand même qu'il n'y en a pas entre 1 000 000 et 60 000 000, on aurait pu oublier les 3 derniers avec la méthode algorithmique en l'arrêtant trop tôt !

Petit jeu !
Parmi les propositions suivantes, saurez-vous trouver celles que l'on ne sait pas démontrer ?
1 - L'ensemble des entiers inévitables est {0,1,2,3,4,5,6,7,8,9}
2 - L'ensemble des nombres premiers écrits en base 2 inévitables est {10, 11}
3 - L'ensemble des puissances de 2 inévitables est {1,2,4,8,65536}
4 - L'ensemble des nombres non-premiers inévitable est { 4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70 72, 75, 77, 111, 117, 171, 371, 711, 713, 731}
5 - L'ensemble des nombres divisibles par 3 inévitables est {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 42, 45, 48, 51, 54, 57, 72, 75, 78, 81, 84, 87, 111, 114, 117, 141, 144, 147, 171, 174, 177, 222, 225, 228, 252, 255, 258, 282, 285, 288, 411, 414, 417, 441, 444, 447, 471, 474, 477, 522, 525, 528, 552, 555, 558, 582, 585, 588, 711, 714, 717, 741, 744, 747, 751, 774, 777, 822, 825, 828, 852, 855, 858, 882, 885, 888}
6 - L'ensemble des nombres de la suite de Fibonacci inévitable est {0, 1, 2, 3, 5, 8}

Solution :
1 - Démontré ! Evident, en fait...
2 - Démontré ! Evident aussi : tout nombre supérieur à 2 écrit en base 2 commence par "10" ou "11". Ces deux nombres étant premiers, ils sont inévitables.
3 - Conjecture ! (encore par Shallit)
4 - Démontré ! (encore par le même)
5 - Démontré ! Il faut voir par le raisonnement qu'un inévitable ne peut être plus grand que 1000 (le raisonnement n'est pas compliqué - arithmétique de lycée)
6 - Conjecture de moi ! (Faut dire que j'ai pas vraiment cherché à le démontrer, en fait... Peut-être est-ce déjà un théorème ?)

---

Sources :
Pour la science - n°296 (Juin 2002) - Nombres premiers inévitables et pyramidaux (Contient la démonstration de la proposition n°5)

03 mai 2008

Une histoire de partie imaginaire

La spirale d'Ulam ou la spirale de Sacks, en plus d'un certain sens esthétique, donne quelques informations sur la distribution des nombres premiers. L'étude de ces nombres est importante pour élargir l'ensemble des connaissance mathématiques, mais importante aussi dans la sécurité bancaire.

L'hypothèse de Riemann est aussi un problème en relation avec la distribution des nombres premiers, donc avec la cryptographie, les transactions bancaires, les grandes entreprises et la bombe atomique.
Ce problème (insurmontable ?) récompensera d'un millions de dollars (par la Clay Mathematical Institute) quiconque parviendra à le démontrer !

Aujourd'hui, nous n'allons pas résoudre le problème, mais on va quand même essayer de le comprendre ! (le minimum requis est de connaitre les nombres complexes)

L'énoncé à démontrer est le suivant : "Les zéros non triviaux de la fonction zêta de Riemann ont tous pour partie réelle 1/2".
Il est vrai que dit comme ça, ça ne nous avance pas vraiment, tâchons d'y voir plus clair.

La fonction zêta de Riemann
La fonction zêta de Riemann (ou d'Euler) est une série (une somme infinie) qui ressemble à ça :

Pour s réel, cette série n'a de véritable sens que lorsque s>1.
Par exemple, on a :
(On retrouve la série harmonique pour s>1)
(Cette formule est la solution du problème de Bâle, loin d'être évident à montrer)

En fait, cette série a un sens pour s réel plus grand que 1, mais également lorsque s est un nombre complexe (de partie réelle >1). Il faut d'abord passer par la définition de la puissance d'un nombre complexe, mais c'est faisable !

Par une opération qui n'a pas lieu d'être expliqué sur ce blog (un prolongement analytique), on arrive à étendre la définition de notre fonction à tous les nombres complexes (sauf 1).

Représenter cette fonction sous forme de graphique n'est pas évident, puisqu'il s'agit d'une fonction complexe (deux dimensions) à valeurs complexes (2 dimensions) ; il nous faudrait 4 dimensions pour le représenter au mieux. On peut cependant représenter le module de ζ(s) en fonction de x+iy :

Plus c'est bleu, on on est proche de zéro... Où sont les zones bleues ?

Cette représentation permet de mettre en évidence le point 1, où la fonction tend vers l'infini (un pôle), ainsi que les points -2, -4, ½+i.14,13i et ½-i.14,13, où la fonction semble être égale à 0.
-2 et -4 sont des zéros triviaux : on montre que si s est un entier pair négatif, alors ζ(s)=0
et sont des zéros non triviaux. C'est de ces zéros que parle l'hypothèse de Riemann.

 

L'hypothèse de Riemann
La fonction zêta de Riemann est ce que l'on appelle une fonction "méromorphe", c'est à dire, une fonction à valeur complexe que l'on peut rapprocher d'une fonction rationnelle (un polynôme divisé par un autre). Pour de telles fonctions, connaitre les pôles (les points où la fonction tend vers l'infini) et ses zéros permet de connaitre entièrement la fonction (De la même façon que les racines d'un polynôme permet de le connaitre). Ceci explique pourquoi un tel intérêt pour les zéros de la fonction.

On connait bien une partie de ces zéros, les entiers pairs négatifs, appelés zéros triviaux :
ζ(-2)=ζ(-4)=ζ(-2n)=0 (n entier)
La fonction semble cependant s'annuler en d'autres points, et on suppose que ces points ont une partie réelle à ½. La question de l'hypothèse est là : montrer que tous les points où s'annule la fonction zêta ont une partie réelle égale à ½.
C'est à dire, si ζ(x+iy)=0, alors x=1/2 (ou x=-2n et y=0)

Ce que l'on sait, pour l'instant, c'est qu'il y a une infinité de zéros non triviaux, et que leur partie réelle est entre 0 et 1. On sait quand même que au moins un tiers des zéros non triviaux ont bien la partie réelle égale à 1/2.
Expérimentalement, il a été vérifié que l'hypothèse est vraie (aux erreurs de calcul près, un ordinateur ne peut représenter les nombres réels de manière exacte) pour les 1 500 000 000 premiers zéros non triviaux. Mais ça ne le justifie pas pour tous !

 

Bien que cette hypothèse ne soit toujours pas démontrée, beaucoup de théorème en sont une conséquence. En déduire un théorème que l'on sait faux serait une bonne façon d'infirmer l'hypothèse de Riemann, mais en attendant, tous ces théorèmes ne sont pas à 100% valides. (ce qui à un côté "dangereux", quand un théorème s'appuie sur un autre qui s'appuie sur un autre qui s'appuie sur l'hypothèse de Riemann...)

Et les nombres premiers, dans tout ça ?
J'y arrive ! C'est vrai que jusqu'à ici, on a vu apparaitre aucun nombre premiers, mais c'est Leonhard Euler qui découvre le rapport, grâce à l'égalité suivante :

Cette égalité permet de donner de bonnes indications sur la répartitions des nombres premiers ; ce n'est qu'une des conséquence de l'hypothèse de Riemann, parmi de nombreuses autres.

La fonction zêta est aussi la source d'un grand nombre d'autres problèmes. C'est bien d'avoir les zéros, mais combien valent t-ils ? Y a t'il des valeurs imaginaires rationnelles ? Et tout une ribambelle de questions sans réponses aujourd'hui !

---

Sources :
Wikipédia - d'où provient l'illustration (Et de nombreux endroits ailleurs)

27 avril 2008

Ennui & nombres premiers

Comment représenter les nombres premiers ? En voilà une bonne question qui, entre les mains de mathématiciens qui s'ennuient, peut révéler des choses intéressantes !

2, 3, 5, 7, 11, 13, 17, etc. Les nombres premiers, rappelons-le tout de même, sont les nombres entiers qui admettent exactement 2 diviseurs.
L'idée la plus simple pour les représenter, ça serait par exemple écrire dans un tableau tous les nombres de 1 à 100, et de colorier d'une couler les nombres premiers, et d'une autre couleur les non premiers.
Ca pourrait donner ça :

En prenant un peu plus que les 100 premiers nombres, les 10000 premiers par exemple, ça peut donner ça :

Ca a un petit côté Matrix, c'est joli... On voit surtout que certaines colonnes brillent par leur absence : les colonnes correspondant aux nombres pairs et nombre divisibles par 5. Il ne semble cependant pas y avoir plus de logique que ça.

Mais on peut trouver d'autre façon de ranger les nombres premiers. L'anecdote raconte qu'en 1963, le mathématicien Stanislaw Marcin Ulam fut contraint d'écouter un exposé très long et très ennuyeux. Il commença alors à écrire les entiers sous forme d'une spirale. Il entoura ensuite les nombres premiers...

Au premier abord, il n'y a rien à voir, mais si on pousse le dessin plus loin, on trouve cette spirale d'Ulam (ou "horloge d'Ulam") (200×200) :

Et, chose étonnante, on peut voir se dessiner des lignes en diagonal de nombres premiers ! Les nombres premiers semblent avoir une organisation ! En semble, seulement. La présence de ces diagonales montre que l'on peut trouver des polynômes de degré 2 (a.n²+b.n+c) donnant un grand nombre de nombres premiers (les diagonales sur la spirale de base ont de tels polynômes pour équation) !

Et quand on démarre par un autre nombre que 1 au centre de la spirale, on peut avoir de belles surprises ! En prenant pour nombre initial 41, on trouve la spirale d'Ulam représentée à gauche. On voit clairement une diagonale du carré se dessiner, diagonale correspondant au polynôme n²-n+41, bien connu par Euler au 18e siècle pour donner des nombres premiers lorsque n est compris entre 1 et 40.

Chose étonnante avec ce polynôme, c'est qu'il donne un nombre premier dans 47,5 % des cas, pour n inférieur à 10 000 000 (58% des cas pour n<1000).
Pour les polynômes de la forme n²-n+c, c'est lorsque c =41 que l'on trouve la meilleure densité de nombre premiers (au moins pour c<1000)

A noter que tout polynôme de degré 2 ne se traduit pas par une belle diagonale dans la spirale de Ulam. En marquant en rouge les nombres premiers de la forme n²-n+41, on voit se dessiner une sorte de spirale au milieu de la spirale de Ulam !

Et si, au lieu de prendre une spirale carrée, on prend une vraie spirale ? Une spirale d'Archimède, par exemple. En s'arrangeant pour que tous les carrés parfait soient alignés, et en mettant le 0 au milieu, on trouve la spirale de Sacks (1994), qui ressemble à ceci :

Et ce sont des courbes qui se dessinent parmi les nombres premiers ! Celle se terminant en bas légèrement à gauche n'est autre que n²-n+41 ! D'autres brillent toujours par leur absence : les n² (le rayon horizontal de droite) ne sont jamais premiers, tout comme les n²-1 (rayon juste en dessous - divisibles par n+1 et n-1) et les n²+n (le rayon horizontal de gauche - divisibles par n et n+1).

Tout ça pour dire que quand on s'ennuie au cours d'un exposé trop long sur un sujet qui ne vous intéresse pas forcément comme les droits successoraux du XVème siècle, il ne faut pas rester les bras croiser en espérant que le temps passe plus vite, mais plutôt gribouiller ce qui vous passe par la tête. Peut-être une révolution dans la façon de voir les nombres premiers va en résulter ?

---

Sources :
Essentiellement, wikipédia !

19 avril 2008

Goodstein contre l'Hydre

Précédemment sur ce blog :
    La suite de Goodstein (de graine 6), qui commence comme ça : 6, 29, 257, 3125, 46655, 98039, 187243, ... Mais comment est définie cette suite ?  On part d'un nombre [...] qui sera le premier terme de la suite. [...] On le décompose en base 2 itérée [...] On remplace ensuite tous les 2 par des 3. [...]On soustrait ensuite 1, et on obtient le deuxième terme de la suite. Pour obtenir le suivant, on décomposera ce nombre en base 3 itérée, et on remplacera les 3 par des 4, et ainsi de suite. [...] Toutes les suites de Goodstein se terminent par 0 ! [...]

==Générique== Palam palam pam pam ==/Générique==

Aujourd'hui, je vais tenter quelque chose de dingue : démontrer le théorème de Goodstein ! (Je vous renvois à l'article d'il y a 3 semaines pour le (re?)découvrir, et à celui de la semaine dernière pour toutes les histoires d'ordinaux). Si cette histoire ne vous plaît pas, vous pourrez redécouvrir le deuxième des douze travaux d'Hercule un peu plus bas...

Mais juste avant de commencer, une petite chose à ajouter à l'article de la semaine dernière à propos des ordinaux, indispensable pour la  démo de Goodstein : toute suite décroissante d'ordinaux parvient à 0 après un nombre fini d'étapes (comme c'est le cas pour les entiers)
Prenons par exemple une suite strictement décroissante d'ordinaux qui commence à ω+5. Après 5 étapes au maximum, on atteindra ω. Un nombre strictement plus petit que ω n'est pas ω-1 (qui n'a aucun sens) mais un nombre entier n. On doit obligatoirement faire un "saut". On arrive alors dans les nombres entiers, et la suite décroissante atteindra 0 après n étapes (au maximum).  On ne peut pas prévoir le nombre d'étape, mais on est sûr qu'il s'agira d'un nombre fini d'étapes.

L'idée de la démonstration est de faire correspondre à chaque élément de la suite de Goodstein un équivalent ordinal. Par la suite, on va prendre ces notations là:
u_n : n-ième terme de la suite de Goodstein
d_n->n+1 : transformation des n en n+1 dans l'écriture en base n itérée.

Le principe de la suite de Goodstein se résume essentiellement comme ça :

Maintenant, on va définir une super-transformation D_n sur le même principe que d_n->n+1, mais au lieu de transformer les n en n+1, on va transformer les n en ω !
Petit exemple :

(Bon, évidement, l'expression finale est vraiment tordue, mais elle représente bien un ordinal)

Trois choses à voir avec cette super-transformation :
* Appliquer D_n, c'est la même chose que appliquer d_n->n+1 puis D_n+1. En effet, la première transforme les n en ω, et la deuxième transforme les n en n+1 puis en ω.
* Cette transformation est strictement croissante : si on a u < v, on aura forcément D_n(u) < D_n(v).
* Si D_n(x)=0, c'est que x=0.

Il y a juste à remarquer que la suite U_n=D_n-1(u_n) est une suite strictement décroissante d'ordinal : elle tombera donc sur 0 après un nombre fini d'étapes, tout comme u_n ! CQFD comme on dit dans le métier.

---

Un autre problème dans le même style (qui demande aussi de passer par les ordinaux pour être démontré) est celui du deuxième des 12 travaux d'Hercule : tuer l'hydre de Lerne.

L'Hydre de Lerne est un serpent d'eau à corps de chien possédant de multiples têtes qui peuvent se régénérer, ainsi qu'une haleine empoisonnée pour corser un peu les choses.

Kirby et Paris ont bien étudié les hydres, et ils se trouvent qu'ils ressemblent tous plus ou moins à un arbre (dans le sens de graphe), comme on peut en voir un exemple juste à gauche.
Pour tuer un tel hydre, il faut lui couper ses têtes :
* Lorsque l'on coupe une tête directement reliée au corps, celle-ci ne repousse pas.
* Si elle n'est pas reliée au corps, l'ensemble des coups et têtes reliés à des nœuds inférieurs peuvent se dupliquer autant de fois que l'hydre le décide (Mais un nombre fini de fois).

Quelle stratégie doit prendre Hercule pour détruire toutes les têtes ?

Imaginons que Hercule décide de couper la tête la plus à droite (en rouge, ici). L'hydre va pouvoir dupliquer en deux temps ses têtes ; d'abord à partir du nœud le plus proche de la tête, l'hydre va se dupliquer en 4 exemplaires, et dans un deuxième temps, il va dupliquer toute la partie droite à partir du corps (ici, en deux exemplaires). Il ressemblera alors à ceci :

Hercule n'a plus qu'à choisir quelle tête il va couper, si possible, sans désespérer de le tuer un jour.

En fait, même si l'hydre fait preuve de vice (dans le nombre de duplications) et Hercule preuve d'une extrême stupidité (dans le choix des têtes qu'il va choisir de couper), Hercule finira un jour par anéantir totalement l'hydre. (Après un nombre fini de têtes tranchées)

De la même façon que pour la suite de Goodstein, on ne peut pas utiliser la simple récurrence pour montrer que Hercule terminera un jour son travail, mais on peut le démontrer en utilisant les ordinaux !

Le seul problème, c'est que l'Univers risque de se détruire avant que Hercule ait terminé le boulot, vu le temps qui sera nécéssaire... L'histoire raconte que Hercule appela son oncle à la rescousse, enflamma quelques arbres pour cautériser les moignons de cou...

---

Sources :
Pour la science - n°278 - décembre 2000
Le coq et l'Hydre [pdf] (pour la démo de cette histoire d'Hydre)

13 avril 2008

Plus grand que les plus petits des plus grand

A quoi sert un nombre entier ? La bonne réponse (pour les besoins de mon article) est "à compter" !
Un, deux, trois, quatre, cinq, six...
Si vous lisez ces lignes, c'est que vous avez normalement l'âge de savoir compter... Compter ! C'est quelque chose de beaucoup trop simple, il est temps de compliquer le concept !

Prenons un exemple connu de tout étudiant de faculté : le tarot ! Dans le cas le plus simple, pour savoir qui remporte un pli, il suffit de voir quelle carte a la plus grande valeur ; la façon la plus simple étant de dire que l'as est la plus basse des cartes (de valeur 1) jusqu'au roi (de valeur 14). Les nombres ici permettent simplement de comparer les cartes. À la fin de la partie, on compte les plis, et les nombres permettent alors de mesurer l'ampleur du désastre d'avoir prit sans bouts. Les nombres permettent alors de mesurer.

Dans le premier cas, les nombres permettent de donner la position dans une suite (l'as est le premier, le 2 la deuxième etc.), et dans le second cas, de décrire la taille d'un ensemble. En français, on distingue ainsi les adjectifs numéraux cardinaux (un, deux, trois...) des adjectifs numéraux ordinaux (premier deuxième, troisième...)

Les ordinaux
    Dans le cas des nombres finis, ça ne pose aucun problème de prendre l'un pour l'autre, mais dans le cas infini, c'est tout autre chose, qui a amené à différencier les nombres ordinaux des nombres cardinaux.
    Les nombres cardinaux peuvent être employés sur n'importe quel ensemble, et correspondent au nombre d'éléments de cet ensemble : s'il est fini, c'est un nombre entier, s'il est infini, il sera dénombrable comme ℕ, dans d'autre cas, il pourra avoir le cardinal de ℝ.
    Les nombres ordinaux sont reliés à la notion d'ordre, (et même de "bon ordre") ce qui permet de dire quel est le plus grand entre deux nombres. En général, pour comparer deux entiers, on appelle "plus petit" celui qui est le plus proche de 0, ce qui ne pose en fait aucun problème.
Mais tout joueur de tarot non borné d'esprit doit avoir quelques notions de belote, notamment de sa façon de classer les cartes non canonique (du genre 7<8<12<13<10<1<9<11). Il a d'autres façon de classer les entiers.

Par exemple, l'ordre de Sarkovskii (enfin, une variante plus simple) sur les entiers : on décompose d'abord notre nombre sous la forme 2ⁿ.p, avec p un entier impair ; pour comparer deux nombres, on compare la puissance de 2, et si elles sont égale, on compare la partie impaire.
Par exemple, on pourra écrire ici :15 <_S 12, car 15=2⁰.15 et 12=2².3, et 0 < 2.
Si on veut compter dans cet ordre, cela va donner quelque chose comme ça :

1 <_S 3 <_S 5 <_S 7 <_S 9 <_S ... <_S 2 <_S 6 <_S 10 <_S 14 <_S 18 <_S ... <_S 4 <_S 12 <_S 20 <_S 28 etc.

On peut alors dire que 1 est le premier (position 0), 3 le deuxième (position 1), 5 le troisième (position 2)... Mais quelle est la position de 2, qui arrive après l'infinité des nombres impairs ?
Il faut donc inventer quelque chose de nouveau (et c'est Cantor qui s'en ait chargé), un ordinal infini : 2 est en position ω.
6 est alors en position ω+1, 10 en position ω+2... Et 4 sera en position ω+ω, c'est à dire 2ω.
Tous les nombres ont bien une position : au nombre 2ⁿ.p correspond la position nω+p. Pour comparer deux nombres selon l'ordre de Sarkovskii, il suffit juste de comparer leur ordinal, en considérant que ω est un nombre plus grand que n'importe quel nombre entier fini.

Mais il y a moyen de faire plus compliqué !
Pour comparer deux nombres, on va d'abord les mettre sous la forme 3^m.2ⁿ.p, avec p non divisible par 2 ou 3.
Si a=3^m.2ⁿ.p et b=3^m'.2^n'.p', on écrit a <_R b si (m<m') ou (m=m' et n<n') ou (m=m' et n=n' et p<p'). (Pour simplifier, on regarde d'abord la puissance de 2, en cas d'égalité la puissance de 2, et en dernier recours, le reste). Ca va nous donner :

Tant que les nombres ne sont pas divisibles par 3, on les positionne de la même façon que pour l'exemple précédent, mais quelle est la position de 3? Il arrive après tous les nombres à la position nω+p, il portera donc logiquement le n° ω×ω, c'est à dire ω². On continue ensuite de compter la même façon. Le nombre 3^m.2ⁿ.p sera donc à la position ω^m+nω+p.

On pourrait facilement imaginer d'autre exemple demandant l'utilisation de ω^ω !

Les bons ordres

Toutes ces façon de comparer deux nombres, les "ordres", sont des "bons ordres" (qui ne s'opposent pas aux "mauvais ordres" mais simplement aux "ordres qui ne sont pas des bons ordres").
On parle d'"ensemble ordonné" quand on définit un ordre sur notre ensemble. Par exemple, ℕ peut être muni de l'ordre classique, de l'un des exemple vu plus haut ou de n'importe quel ordre sorti de votre imagination.

On dit qu'un ensemble ordonné est "bien ordonné" (muni d'un "bon ordre") si toute partie de cet ensemble admet un plus petit élément.
Dans nos exemples précédents, tous les ordres étaient des bons ordre. Par exemple, si je prend l'ensemble des nombres commençant par D : {2, 10, 12, 17, 18, 19, 200, ...}, le plus petit nombre de l'ensemble selon l'ordre de Sarkovskii est 17. En fait, n'importe quel sous-ensemble de ℕ admet un plus petit nombre selon cet ordre.

Mais ce n'est pas toujours le cas. Prenons ℝ avec son ordre classique. On peut voir tout de suite que ℝ n'a pas de plus petit élément (pour n'importe quel nombre réel, on peut toujours en trouver un plus petit). On va alors se limiter à ℝ⁺, l'ensemble des réels positifs. ℝ⁺ a bien un plus petit élément, c'est 0.
Mais si je considère l'ensemble des nombres strictement supérieurs à 0. Quel est le plus petit réel dans cet ensemble ? 0.1 ? 0.01 ? 0.00000001 ?... Impossible de trouver un tel nombre, cet ensemble n'admet pas de plus petit élément ! L'ordre naturel de ℝ n'est pas un bon ordre !

Et arrive Zermelo !
Le théorème de Zermelo dit qu'on peut donner un bon ordre à n'importe quel ensemble. Il existe donc une façon de bien ordonner ℝ ! (Et de lui associer un ordinal)
Petit détail tout de même : ce théorème nécéssite l'axiome du choix, ce qui veut dire que le bon ordre obtenu sur ℝ ne va pas être "bien" défini !

Et à quoi sert tout ça ? Au moins à 3 choses :
- Démontrer le théorème de Goodstein (je me réserve la joie de le faire dans le prochain article)
- Ajouter une belle pierre dans l'ensemble des théories mathématiques
- Dire que le tarot, n'empêche, c'est bien plus simple que la belote !

---

Sources :
Un habile mélange de Wikipédia et de Pour la science (n°278 - décembre 2000)

06 avril 2008

Sponsorisé par Nokia

Paul Erdõs ("un mathématicien est une machine qui transforme le café en théorèmes") est un mathématicien hongrois qui a la grande particularité d'avoir beaucoup d'amis. Du moins, il a co-signé un très grand nombre d'article de recherche avec d'autre mathématiciens plus ou moins célèbres. On lui dénombre aujourd'hui 511 co-auteurs, et à moins de retardataires, on suppose qu'il n'y en a pas d'autre.
En l'honneur d'Erdõs, on attribue aujourd'hui à chaque mathématicien (ou autre scientifiques) un nombre d'Erdõs de la façon suivante :
Si vous êtes Paul Erdõs, votre nombre d'Erdõs est 0 ;
Si vous avez cosigné un papier de recherche avec auteur de nombre d'Erdõs N, votre nombre d'Erdõs est N+1 ;
S'il n'y a pas de chaine pouvant vous relier à Erdõs, votre nombre d'Erdõs sera +∞.
Ainsi, un mathématicien a un nombre d'Erdõs égal à 0, 511 l'ont égal à 1 et 8162 l'ont égal à 2.

On peut remarquer qu'il n'y a pas que des mathématiciens qui ont un nombre d'Erdõs fini, puisque celui de Albert Einstein est de 2 (par le biais de Straus (et la conjetcure d'Erdõs-Straus)).
Si on s'intéresse aux médaille Fields (le prix Nobel des maths), on peut remarquer qu'ils ont tous un nombre d'Erdõs inférieur ou égal à 6 (Sauf le français Laurent Lafforgue, qui en a un infini). Les lauréats du prix Abel (autre récompense mathématique) l'on tous inférieur à 4
Pour les prix Nobels de physique, ils l'ont tous inférieurs à 8 (ça va de 2 pour Einstein jusqu'à 8 pour Schrodinger).

En l'honneur de Erdõs, le magazine Tangente a inventé pour la Saint-Valentin le nombre de Carla, qui est à Mme Sarkozy ce que le nombre d'Erdös est à Paul Erdõs. Il est défini de la même manière :
- Si vous êtes Carla Bruni, votre nombre est 0
- Si vous avez eu une relation avec quelqu'un ayant un nombre de Carla égal à N, le votre sera N+1.

Je doute que l'un de vous, lecteur, ait un nombre d'Erdõs fini, mais la probabilité que votre nombre de Carla soit fini est déjà plus grande...
Il n'existe cependant pas encore de base de données recensant les gens par nombre de Carla, mais on en connaît déjà quelques uns ayant un nombre de Carla égal à 1 : Nicolas, Mick, Eric, Donald... Pour ceux de nombre de Carla égal à 2, on trouve entre autres Cécilia... Je laisse le soin à Voici de découvrir à partir de qui les nombres pairs ne sont pas réservés aux femmes.

Toujours dans le même ordre d'idée, Kevin Bacon prend la place d'Erdõs pour le cinéma. Si vous êtes Kevin Bacon, votre nombre est 0 ; si vous avez joué dans le même film que Kevin Bacon, votre nombre est 1, et ainsi de suite. Fait étonnant : en apparaissant brièvement dans le film Will Hunting, Dan Kleitman, consultant mathématique du film, cumule un nombre de Bacon de 2 et un nombre d'Erdõs de 1. Son nombre d'Erdõs-Bacon est donc de 3 ! Paul Erdõs, quant à lui, a un nombre de Bacon égal à 4 !

Dans le monde des échecs, c'est Paul Morphy qui prend la place d'Erdõs. Il y a aussi la variante du nombre Kasparov, où cette fois-ci, le graphe est orienté : Kasparov a pour nombre 0, si vous avez battu Kasparov, votre nombre est 1, etc. Dans le monde des jouers de Go, c'est le nombre de Shusaku qui est utilisé.

Tout ça se rapproche de l'étude du petit monde de Stanley Milgram (le même qui a fait l'expérience de Milgram de soumission à l'autorité), qui a amené le concept de "six degrés de séparation". L'expérience  originale demandait à 60 habitants de d'Ohama dans le Nebraska de faire parvenir une lettre à une personne précise, vivant à Sharon dans le Massachusetts. Les volontaires de l'expérience ne pouvait donner la lettre que de mains à mains. Bien que peu de lettre arrivèrent à destination,  le nombre de 6 intermédiaire se dégagea. D'autres expériences, via internet, par exemple, donnent les même résultats, d'où le concept des six degrés de séparation.

Il semble donc que je connais quelqu'un qui connait quelqu'un qui connait quelqu'un qui connait quelqu'un qui connait quelqu'un qui connait Paul Erdõs !

---

Sources :
The Erdõs Number Project - Bases de données sur les nombre de Erdõs
Tangente n°120 - Janvier/Février 2008 : Calculez votre nombre de Carla
The Oracle of Bacon - A propos du nombre de Bacon
Your Morphy number is up [pdf] - A propos du nombre de Morphy
I beat Garry ! A propos du nombre de Kasparov
Le Journal du Net - L'expérience des 6 degrés (L'image provient de Wikipédia)

30 mars 2008

Ne pas croire ce qui croît

Une célèbre conjecture lycéenne dit que si une suite a l'air simple (1), à l'air de grimper vite au vu de sa définition (2) et a une croissance à peu près régulière sur ses premiers termes (3), alors cette suite est croissante ! Il est temps de vérifier la validité de cette étonnante conjecture !

Cette conjecture se vérifie bien avec des suites définies à base de fonctions puissances, du genre U_n=2ⁿ. La suite a l'air simple, elle a l'air de grimper vite au vu de sa définition (ya une puissance, quand même) et a une croissance régulière, et même de plus en plus rapide, sur ses premiers termes (2, 4, 8, 16, 32, 64, 128...). Cette suite est bien croissante !

Prenons un autre exemple, alors : la suite de Goodstein (de graine 6), qui commence comme ça :
6, 29, 257, 3125, 46655, 98039, 187243, ...
Avec un petit graphique, ça donne :

Sur ses 30 premiers termes, cette suite a l'air de grimper de plus en plus vite, on vérifie bien la troisième partie de notre conjecture.

---

Mais comment est définie cette suite ?

* On part d'un nombre, (la graine, ici 6) qui sera le premier terme de la suite.

* On le décompose en base 2 itérée. C'est comme décomposer le nombre en base 2 (En somme de puissances de 2), sauf qu'on décompose également les puissances en base 2, jusqu'à n'avoir que des nombres inférieurs ou égaux à 3.*
Exemple avec 303 :
En base 2, 303 s'écrit  1×2⁸+0×2⁷+0×2⁶+1×2⁵+0×2⁴+1×2³+1×2²+1×2¹+1×2⁰
(Qui s'écrit plus agréablement 2⁸+2⁵+2³+2²+2+1)
Ensuite, on remplace 8, 5 et 3 par leur décomposition en base 2, ce qui donne :
Il reste encore un 3, donc on le remplace par 2+1, ce qui donne la décomposition de 303 en base 2 itérée:

La décomposition de 6 en base 2 itérée est plus facile : 6=2²+2

* On remplace ensuite tous les 2 par des 3.
À partir de 303, on aurait (Ce qui vaut a peu près 4,43×10³⁸)
À partir de 6, on aurait 3³+3 (=30)

* On soustrait ensuite 1, et on obtient le deuxième terme de la suite. Pour obtenir le suivant, on décomposera ce nombre en base 3 itérée, et on remplacera les 3 par des 4, et ainsi de suite.

Voici un petit script permettant de voir ces suites (Qui bugue dès que les valeurs deviennent trop grandes, ce n'est que du javascript) (Si je savais mettre du LaTeX directement dans mes pages, il y en aurait dans ce script, mais en attendant, il n'y a que la synthaxe...)

Nombre à transformer :
  Nombre de pas :

En tout cas, cette suite a une définition, certes tordue, mais assez simple. Elle ne met en jeu que la décomposition d'un nombre en une certaine base, et des remplacements. Elle vérifie bien le critère 1 de simplicité.
Et à le regarder de loin, on a des puissances de plus en plus grandes, ya pas de raisons, d'après sa définition, elle a l'air de plus en plus grande.
D'après notre géniale conjecture qui simplifie grandement le travail des mathématiciens, cette suite est toujours croissante !

Et évidement, si je parle de cette suite ici, c'est parce qu'elle contredit notre conjecture stupide :
Toutes les suites de Goodstein se terminent par 0 ! Saperlipopette !

---

Expliquons quand même ce mystère, je suis là pour ça.

La suite qui commence par 2 n'est pas la plus intéressante :
(Le D_i->j désigne la transformation des i en j)
U₀ = 2
U₁ = D_2->3(2)-1 = 3-1 = 2
U₂ = D_3->4(2)-1 = 2-1 = 1
U₃ = D_4->5(1)-1 = 1-1 = 0

La suite qui commence par 3 n'est pas la plus intéressante non plus :
U₀ = 3
U₁ = D_2->3(2+1)-1 = (3+1)-1 = 3
U₂ = D_3->4(3)-1 = 4-1 = 3
U₃ = D_4->5(3)-1 = 3-1 = 2
U₄ = D_5->6(2)-1 = 2-1 = 1
U₅ = D_6->7(1)-1 = 1-1 = 0

Mais celle qui commence par 4  est déjà plus intéressante :
U₀ = 4
U₁ = D_2->3(2²)-1 = (3³)-1 = 26
U₂ = D_3->4(2.3²+2.3+2)-1 = 2.4²+2.4+1
U₃ =  2.5² + 2.5 + 0
U₄ = 2.6² + 6 + 5
U₅ = 2.7² + 7 + 4
U₆ = 2.8² + 8 + 3
etc.
Ce que l'on peut remarquer, c'est qu'à partir du deuxième terme, la décomposition est toujours de la forme a.p²+b.p+c. Le nombre p est la base dans laquelle est décomposé le nombre (qui vaut n+2, n étant l'indice de la suite). En effet, la décomposition itérée en base p (>2) n'affectera pas les puissances, les seuls nombres qui seront modifiés par le remplacement seront les p)
Ainsi, quand on ne s'intéresse qu'aux coefficients a, b et c, on peut voir la suite comme ça :

* Quand le coefficient c est différent de 0, il n'y a que lui qui sera atteint par le -1.
* Si c=0 et b≠0, le coefficient b sera décrémenté, et c prendra la valeur p-1.
En effet, à la base p, on aura U_n = a.p²+b.p et donc, U_n+1 = a.(p+1)²+b.(p+1)-1. (Ce qui n'est pas une décomposition acceptable, il nous la faut en somme) On la transforme alors :
U_n+1 = a.(p+1)²+b.(p+1)-1 = a.(p+1)²+(b-1).(p+1)+(p+1)-1 = a.(p+1)²+(b-1).(p+1)+p
* Si a≠0, b=0 et c=0, c'est a qui sera décrémenté ; b et c prendront les valeur courantes de la base.

En fait, les valeurs a b et c fonctionnent comme un compte à rebours. La différence, c'est qu'au lieu d'être en base 60 (1 h 00 min 00 sec -> 0h 59 min 59 sec...), c'est une base qui change en permanence, et qui est croissante.

Ainsi, les coefficients a b et c vont bien arriver à 0 à un moment ou un autre... Pour être précis, elle atteindra la valeur 0 lorsque p sera égal à (A peu près 120 millions de chiffres...)

Ca, c'est pour la suite qui commence par 4. Celle-ci a pour particularité de ne pas grandir si vite que ça... Si on commence par 18 ou 19, ça ira beaucoup plus vite au début ! Mais l'idée du compte à rebours reste à peu près valable.

---

 

Le théorème de Goodstein, qui dit que toute suite de Goodstein se termine par 0, est un théorème d'arithmétique. Il traite de nombre entier et n'utilise que des notions d'arithmétiques. Mais ce qui est fâcheux, c'est que c'est un théorème indémontrable... d'un point de vue arithmétique !

Kirby (La boule rose, pas le mathématicien)

Pour le démontrer, il faut passer utiliser des notions d'infinis (une sombre histoire d'ordinaux infinis) qui dépasse de loin le cadre de la théorie de l'arithmétique dans lequel le théorème est énoncé. Il est donc impossible de démontrer ce théorème par récurrence, même avec la meilleure imagination du monde, et ça, c'est Laurence Kirby (pas la boule rose, le mathématicien) et Jeffrey Paris qui le disent (Et ils l'ont rigoureusement démontré) !

---

Sources :
Pour la science n°278 Décembre 2000, L'infini est-il nécessaire ?

23 mars 2008

Plenty of room at the Hilbert hotel

(J'avais déjà parlé de ces histoires d'infinis, mais ça ne fait pas de mal d'y revenir)
Pour fêter Pâques, voici une petite histoire du monde idyllique des mathématiques, qui n'a en fait rien à voir avec les cloches ou les lapins.

Dans le monde parallèle merveilleux et utopique des mathématiques, il existe un hôtel possédant une infinité de chambres. C'est hôtel, c'est l'hôtel de Hilbert.

Ce jour là, l'hôtel était complet, toutes les chambres étaient occupées, mais un nouveau client arrive. "Pas de problèmes" lui annonce le gérant de l'hôtel. Grâce au téléphone interne de l'hôtel, il téléphone simultanément à tous les clients de l'hôtel en leur demandant de passer dans la chambre d'à-coté. Le client de la chambre n se verra donc attribué la chambre n+1. Le nouveau client peut alors prendre la chambre 0, alors vide. Tous les clients ont alors leur chambre pour la nuit.

Une heure plus tard, c'est un bus qui arrive dans le parking de l'hôtel. Infini, le car, évidement, et c'est une infinité de nouveaux clients qui demandent à avoir une place dans l'hôtel. Devant cette situation, le gérant téléphone à nouveau à chaque client en leur demander de déménager dans la chambre 2n. Toutes les chambres impaires sont donc vides, et le i-ième client arrivé depuis le bus peut occuper la 2i+1eme chambre. L'hôtel est à nouveau complet, tout le monde à sa chambre.
Une heure plus tard, c'est une infinité de bus infinis qui débarquent. Après quelques minutes de réflexions, le gérant décrocha son téléphone interne pour communiquer les nouveaux ordres : le client de la chambre n doit aller dans la chambre 2n. Maintenant que les chambres impaires sont libres, le gérant explique aux nouveaux arrivant la consigne : le i-ième passager du j-ième bus s'installera dans la chambre 2ⁱ⁺¹(2j+1)-1.

Le gérant passa l'heure suivante à réfléchir à comment réagir si c'était une infinité de bus infinités qui arrivaient dans chaque étage du parking infini... Le i-ème passager du j-ième bus et du k-ième étage devrait prendre la chambre 2^{(2^i)(2j+1)}(2k+1)-1... Ca devrait marcher, se dit-il, et il retourna se coucher, il avait bien mérité sa nuit.

Mais une heure plus tard, c'est un bus d'une nouvelle espèce qui se garait dans le parking de l'hôtel : un bus infiniment tordu sur lui-même. La place avant du bus était numérotée 0, celle du fond était numérotée 1, et quand on regardait deux places du bus, on s'apercevait qu'il y en avait toujours une autre entre les deux. Chaque place était numérotée par un réel de l'intervalle [0,1], et à chaque réel de cet intervalle correspond une place du bus. Au grand malheur du gérant, le bus était plein...
"Je n'avais pas prévu ça" se dit le gérant, devant le nombre de personne qui lui fallait loger... Il pris un haut parleur, et annonça à tous les passagers qui étaient descendus du bus et qui recouvraient alors de manière continue le parking : "Je vais essayer de loger un maximum de personne, mais tout le monde ne pourra pas entrer... Vous connaissez tous bien votre numéro de siège ? Parfait, si vous êtes une fraction, vous pouvez entrer, ma secrétaire va vous donner la marche à suivre". Une infinité de passagers quittèrent la foule pour s'engouffrer dans l'hôtel, mais la marée humaine sur le parking restait dense. Le gérant repris son mégaphone pour annoncer "Si votre place est un nombre algébrique, vous pouvez entrer". Le parking restait noir de monde, malgré la file indienne infinie qui quittait la foule. "Bon, tous ceux capables de me décrire leur numéro de place peuvent entrer, les autres, je suis désolé, mais vous ne pourrez pas entrer".

Le lendemain, le gérant commença à dessiner les plans de son futur hôtel, un hôtel continu où entre deux chambre se trouve toujours une autre chambre. Le lendemain de sa construction, c'était un bus numéroté par des fonctions réels continues qui se garait dans le parking...

---

Quelques explications tout de même :

* Comment peut-on placer l'ensemble des rationnels (les fractions) de [0,1] dans l'hôtel ? L'hôtel, qu'il soit vide ou plein, peut se voir comme l'ensemble des entiers naturels 0, 1, 2, 3... (S'il est plein, on libère les chambres impaires par le procédé chambre n -> chambre 2n).
Si une place du bus est un rationnel (différent de 0 et 1), elle est de la forme p/q (avec 0<p<q). En écrivant ces nombres sous la forme d'un triangle, on peut décider que le passager n°1/2 prendra la chambre 1, le passager n°1/3 prendra la chambre 2, le passager n°2/3 prendra la chambre 3 etc.

Quand on peut faire une telle correspondance entre un ensemble de nombre et , on dit que cet ensemble est dénombrable.

* L'ensemble des nombres algébrique (qui sont racine d'un polynôme à coefficients entiers), tout comme celui des nombre que l'on peut décrire est également dénombrable, mais la démonstration est moins évidente.

* Pourquoi ne peut-on pas mettre en correspondance l'intervalle [0,1] (indénombrable) avec (dénombrable) ? La façon la plus simple de le comprendre est la preuve diagonale de Cantor.
Partons du principe que chaque réel possède un développement décimal. Celui-ci est infini (même s'il n'est pas forcément unique, d'où le paradoxe 0,9999...=1, mais ça ne va pas vraiment jouer ici).
Si on pouvait mettre en correspondance cet intervalle avec , on pourrait arbitrairement décider d'un premier, d'un deuxième, etc. Imaginons que l'on peut faire cette correspondance. On peut alors mettre cette suite de réels dans un tableau, avec le développement décimal explicité :

En prenant la suite des chiffres présente sur la diagonale, on peut construire un nouveau nombre (en jaune). A partir de celui-ci, on change chaque occurrence de 0 par un 1, et tous les autres chiffres deviennent 0. Ce nouveau nombre construit est bien un réel de l'intervalle [0,1], et n'est pas présent dans le tableau (par construction). Tous les réels de [0,1] ne peuvent donc pas être organisés dans un tel tableau, puisqu'il en existe (au moins) un qui n'y est pas : C'est donc qu'on ne peut pas organiser les réels de [0,1] de cette façon ! L'ensemble des réels de [0,1] ne peut être mis en correspondance avec .

---

Sources :
Pour la science n°278 Décembre 2000, L'infini est-il paradoxal en mathématiques ?

22 mars 2008

Graphe connexe de degré maximum 2

Un blog comme celui-ci peut-il faire suivre des chaîne du genre "révélez 6 secrets sur vous et faites passer le questionnaire"... ? La réponse est oui ! C'est quand même bizarre que ça s'appelle "chaîne"... J'aurai plutôt dit "arbre"...
A la demande de Bertaga et du Doc', voici 6 choses que je n'avais pas encore révélé là, et que vous n'avez pas besoin de savoir sur moi (spécial maths, c'est le lieu pour).

1 - Mon intérêt pour les maths doit dater de mon année de CM2, année durant laquelle notre professeur nous a expliqué ce qu'étaient les différentes bases de numération, notament le binaire... A moins que ça soit à cause de mon prof de 5eme qui nous a parlé de géométrie non euclidienne...

2 - En CM1, je n'ai jamais pu apprendre une autre table de multiplication que celle de 2 (à part peut-être celles de 0 et de 1)... Celle de 3 m'était hors de portée, et de toutes façon, les maths, ça sert à rien, hein ?...

3 - Je pratique dans la vie de tous les jours l'art de faire des digressions mathématiques à partir de n'importe quoi, surtout si je suis en présence de personne pas forcément attirées par ces histoires de fractales, de problèmes NP, de séries divergentes ou de lois de Benford.

4 - Je déteste les sudokus.
- Ah bon, pourtant, tu fais des maths, tu dois aimer les problèmes de logique, non ?...
- Oui, mais les journaux en ont tellement fait avec leurs cahier détachables spécial sudokus réalisés en trois minutes grâce à un logiciel adapté que j'ai dû faire saturation...

5 - A l'ouverture de ce blog, je ne connaissais pas le sens de "intégrale curviligne". J'avais juste entendu le terme de loin, et je le trouvais joli à l'oreille. En même temps, je n'ai jamais goûté de choux romanesco, et je n'aime pas la vache qui rit...

6 - Mais je ne fais pas que des maths, je suis poète... La preuve, j'ai gagné un concours de poésie il n'y a pas plus tard que la semaine dernière ! (Je sais, je suis lourd avec cette histoire...)

Et je passe le relai à PP? pour voir si on peut aussi mettre une chaîne sur une blog de photos...
(Et si tout va bien, demain, l'article de la semaine)

16 mars 2008

"Et si le 9 était la clé"

"Et si le 9 était notre matrice?..."
Non, je n'ai rien contre TF1... A moins que...

Phenoménal ! (Table de 9)
envoyé par El_Jj

"Les tables de multiplications, c'est un cauchemar", "Ca vous parait obscur, normal, c'est des maths"... Passons... Je passe également sur leur notion de "preuve" plutôt empirique.

Pas de note anti-Jean-Luc Reichmann, j'en ai déjà fait une, c'est juste un moyen détourné de parler des petits trucs que vous connaissez peut-être déjà : les critères de divisibilités !
Ca sert toujours, même si ils ont tendance à ne pas nous donner le résultat de la division.

Mais histoire d'avoir une petite prétention mathématique, je vais donner quelques preuves pas forcément rigoureuses, mais compréhensibles. Les seules choses intuitives à savoir, c'est que un nombre de la forme k×n est toujours divisible par k (c'est même sa définition), et que k×n+r est divisible par k seulement si r est aussi divisible par k.

Divisibilité par 9 :
16623 : 1+6+6+2+3=18, 1+8=9 -> 16623 est divisible par 9
1425 : 1+4+2+5=12, 1+2=3 -> 1525 n'est pas divisible par 9
Un nombre est divisible par 9 ssi la somme de chiffres est divisible par 9.

Pour voir d'où vient ce prodige digne de Matrix, il suffit de décomposer les nombre en somme de puissance de 10, et quelques petits développements/factorisations suffisent :
16623 = 1×10000 + 6×1000 + 6×100 + 2×10 + 3
= 1×(9999+1) + 6×(999+1) + 6×(99+1) + 2×(9+1) + 3
= [1×9999 + 6×999 + 6×99 + 2×9] + [1+6+6+2+3]
= 9[1×1111 + 6×111 + 6×11 + 2×1] + [1+6+6+2+3]
Les crochets de gauche étant sous la forme 9X, c'est divisible par 9. Il faut donc que la somme de droite soit divisible par 9 pour que cela fonctionne.

On peut aussi expliquer ce prodige en remarquant que quand on ajoute 9 à un nombre (qui ne finit pas par 0), on au joute 1 aux nombre de dizaines et ou soustrait 1 au chiffre des unités. Si ça se termine par un 0, on le change juste en 9.
Puisque la somme des chiffres de 9 est égale à 9, la somme des chiffres reste donc toujours égale à 9. (Et hop, la belle preuve par récurrence)

Divisibilité par 3 :
16623 : 1+6+6+2+3=18, 1+8=9 -> 16623 est divisible par 3
1425 : 1+4+2+5=12, 1+2=3 -> 1525 est divisible par 3
Un nombre est divisible par 3 ssi la somme de chiffres est divisible par 3.
(Que l'on trouve 0, 3, 6 ou 9 à la fin)

Pour voir d'où vient ce prodige digne de Matrix Revolutions, il suffit juste de comprendre le semblant d'explication pour le critère de divisibilité par 9, celui par 3 fonctionne pareil.

Divisibilité par 2, par 5 ou par 10 : 
Un nombre est divisible par 2 ssi il se termine par 0, 2, 4, 6 ou 8
Un nombre est divisible par 5 ssi il se termine par 0, ou 5
Un nombre est divisible par 10 ssi il se termine par 0
Celles-là, si vous ne les connaissiez pas, je me demande comment vous avez fait pour lire cet article jusqu'à ici...

D'où vient ce prodige digne de Matrix Reloaded ? Il suffit de couper son nombre en 2 : d'un côté le chiffre des unités (u), et de l'autre, ben, le reste (r). Le nombre sera alors de la forme 10r+u. Puisque 10 est divisible par 2, 10r est divisible par 2, et il nous faut donc u, le nombre des unités, divisible par 2 : les seules possibilités sont 0, 2, 4, 6 ou8.

Et ça marche pareil avec 5 et 10

A noter quand même que le critère de divisibilité par 10 est la réunion du critère de divisibilité par 2 et par 5 !

Divisibilité par 4, par 25 ou par 100 :
Un nombre est divisible par 25 ssi il se termine par 00, 25, 50 ou 75.
Un nombre est divisible par 4 ssi il se termine par 00, 04, 08, 12, 16, ..., 96 (Que ses deux derniers chiffres sont divisibles par 4)
Un nombre est divisible par 100 ssi il se termine par 00

D'où vient se prodige digne de Matrix Reverse (Qui n'est pas sorti, c'est dire à quel point c'est prodigieux) ? Il suffit juste de reprendre ce qu a été dit juste au dessus, en remplaçant 10 par 100 et 2 par 4 ou par 25...

On généralise facilement pour trouver un critère de divisibilité par 8, 16, 100, 125, 625, 1000... :
Un nombre est divisible par 2ⁿ ssi ses n derniers chiffres sont divisibles par 2ⁿ.
Un nombre est divisible par 5ⁿ ssi ses n derniers chiffres sont divisibles par 5ⁿ.
Un nombre est divisible par 10ⁿ ssi il se termine par n zéros

Divisibilité par 11 :
154915145 -> +1-5+4-9+1-5+1-4+5 = -11 -> 154915145 est divisible par 11
123456789 -> +1-2+3-4+5-6+7-8+9 = 5 -> 123456789 n'est pas divisible par 11
Un nombre est divisible par 11 ssi la différence entre la somme des chiffres de rangs pair et la somme de ceux de rangs impair est divisible par 11.
(Dans la pratique, on regarde ce qu'il se passe en intercalant des + et des - entre tous les chiffres)

D'où vient ce prodige digne de Matrix fait du ski ? On fait la classique décomposition de notre nombre en somme de puissance de 10, et après, il faut remarquer quelques petites choses :
* 100-1 = 99 = 11×9
10000-1 = 9999 = 1111×9
Et ainsi de suite, tout nombre de la forme 10²ⁿ-1 est divisible par 11.
* 10+1 = 11×1
1000+1 = 11×91
Tout nombre de la forme 10²ⁿ⁺¹+1 est divisible par 11
(Car 10²ⁿ⁺¹+1 = 10.10²ⁿ+1 = 10.(10²ⁿ-1+1)+1 =10.(10²ⁿ-1)+10+1 = 10.11k+11)
* En prenant par exemple un nombre à 6 chiffres de la forme abcdef, on a :
abcde= a×10000 + b×1000 + c×100 + d×10 + e
= a×(9999+1) + b×(1001-1) + c×(99+1) + d×(11-1) + e
= [9999a+1001b+99c+11d] + [a-b+c-d+e]
Les crochets de gauche donnent quelque chose de divisible par 11, il faut donc nécessairement la divisibilité à droite !

Divisibilité par 6, par 12, par 15... :
Un nombre est divisible par 6 s'il est divisible par 2 et par 3. (et ses critères associés)
Un nombre est divisible par 12 s'il est divisible par 3 et par 4.
Un nombre est divisible par 15 s'il est divisible par 3 et par 5.

Si n et p sont des nombres premiers entre eux (que la fraction n/p est irréductible), le critère de divisibilité par n×p sera l'association du critère de divisibilité par n et de celui par p.
Cela nous donne facilement des critères pour la divisibilité par 18, 22, 30, 33...

Avec tout ça, on peut facilement savoir si un nombre est divisible par 1, 2, 3, 4, 5, 6, 8, 9, 10, 11... De quoi savoir facilement si un nombre inférieur à 100 est premier, en testant la divisibilité par 2, 3 et 5 (Les seules exceptions étant 49=7×7 et 91=7×13)
Il nous manquerait juste un critère de divisibilité par 7...

Critère de divisibilité par 7
36491 :
3649-2×1=3647
364-2×7=350
35-2×0=35
3-2×5=-7
-> 36491 est divisible par 7

Un nombre est divisible par 7 ssi "nombre de dizaines"-2×"chiffre des unités" est divisible par 7

(Critère totalement inutilisable pour des nombres longs, heureusement, il y en a d'autre)

1 507 985 948 :
+1-507+985-948 = -469 (= -67×7)

-> 1 507 985 948 est divisible par 7

Un nombre est divisible par 7 ssi, après avoir séparé les chiffres par groupes de 3 et intercalé des + et des -, on trouve un multiple de 7.

Dans la pratique, on réserve le premier critère pour savoir si le résultat des opérations issu du deuxième critère est divisible ou non par 7.

Quel est ce prodige digne de Matrix chez les ch'tis ?
Le deuxième critère reprend la démonstration du critère de divisibilité par 11
Le premier critère est déjà plus tordu, et se démontre rapidement en utilisant des modulos (mais je vais pas le faire, désolé)

Bref, maintenant, vous connaissez parfaitement tous les critères de divisibilité !...
Et vous savez que TF1 est une chaîne totalement stupide...

---

Sources :
Wikipédia (pour avoir aussi le critère de divisibilité par 3ⁿ, 17, 19, 23, 31, 37 etc.)