Choux romanesco, Vache qui rit et intégrales curvilignes

25 novembre 2007

Quand les tortues font des maths

Quel est donc le point commun entre la tortue étoilée d'Inde (Geochelone elegans) et le Gömböc, objet mathématique nouvellement fabriqué par deux Hongrois ?

Tout le monde connaît le jouet pour enfant culbuto : un objet tridimensionnel qui revient toujours dans la même position, peut-importe la manière dont on le pose sur la table. On dit qu'il ne possède que deux points d'équilibre : un point d'équilibre stable (vers lequel il reviendra toujours) et un point d'équilibre instable (au moindre mouvement, il s'éloignera de ce point d'équilibre).
La source de ce prodige est simple : le culbuto est lesté en sa base de manière à toujours revenir en son point d'équilibre, il possède un contre poids. Un culbuto n'est donc pas homogène (possédant la même densité partout).
Pour un mathématicien, tout est source de problème, le culbuto n'en est pas exempt : existe t'il un objet tridimensionnel qui possède la propriété du culbuto (seulement deux points d'équilibres), mais qui serait en plus homogène ?

Et la réponse, démontrée par deux Hongrois, Gábor Domokos et Péter Várkonyi, est affirmative : un tel objet homogène tridimensionnel à deux points d'équilibre existe, et sera appelé Gömböc (quadri-sphère, dans la langue natale de Loránt Deutsch - le hongrois). Le résultat, trouvé après une dizaine d'années de recherche, s'est ponctué par la fabrication de l'objet basé sur leur équations (qu'ils comptent vendre, il faut bien rentabiliser les recherches). A noté qu'il n'existe pas qu'un seul Gömböc, mais  qu'il peut prendre plusieurs formes, relativement proche. Un concours a même été lancé pour trouver un Gömböc constitué de polyèdres (10 000$ à la clé).

Tout a commencé dans les années 90, où Gábor Domokos (ingénieur), aidé de Jim Papadoupolos, s'est posé la grande question : quel est le nombre minimal de point d'équilibre que peut posséder une forme en deux dimensions ?
Si on prend le cas du cercle, on est en face d'un nombre infini de points d'équilibres.
Si on prend le cas du carré, on est en face de 8 points d'équilibres : 4 stables (les côtés) et 4 instables (les pointes). Pour un triangle équilatéral, on en trouve de la même façon 6.
Si on prend le cas de l'ellipse, on est en face de 4 points d'équilibres : 2 stables (sur le petit axe) et 2 instables (sur le grand axe)
En 1994, ils découvrent que le nombre minimal de points d'équilibres pour n'importe quel forme à deux dimensions est de 4.
Et c'est donc tout naturellement que Domokos s'est penché sur le cas des formes en 3 dimensions.

Et le rapport avec les tortues, dans cette histoire ? Et bien, cette trouvaille mathématique permet de classer d'une nouvelle façon les animaux à carapaces, par rapport à la facilité qu'ils ont à se remettre sur pattes quand ils sont retournés. Ainsi, la tortue étoilée d'Inde, qui possède une carapace proche du Gömböc, peut sans grands efforts se remettre sur pattes !

---

Sources :
Sciences & Avenir - Décembre 2007
Le site officiel (avec une vidéo de l'objet)
Images prises ici et là

18 novembre 2007

Vive les castors

Non, l'informatique, ce n'est pas que Windows et ses bugs ou Mac et ses non-bugs, c'est aussi la programmation. Et la programmation, ce n'est pas qu'un écran noir devant lequel un informaticien à lunette tape d'étranges lignes de code, c'est bien plus que ça... Surtout que la programmation a été inventée avant l'informatique, grâce à Turing et sa machine...
Et les castors, dans tout ça ? Patience, ils arrivent...

Bref, une machine de Turing, qu'est ce que c'est ?
C'est une machine théorique composée
- d'un ruban (de longueur infinie, constitué de cases contenant des symboles ("0","1",...). Initialement, presque toutes les cases sont remplies de "0")
- d'une tête de lecture/écriture
- d'une table d'actions suivie par la tête de lecture.

Initialement, la tête de lecture est à la place 0 du ruban, et l'état de la machine est 0.
La machine lit alors la case sur laquelle se trouve la tête de lecture, et, suivant le symbole lu et l'état de la machine, exécute une action décrite dans la table, composée de trois étapes:
- La tête écrit un nouveau symbole sur la case où elle se trouve
- La tête effectue un mouvement vers la droite où la gauche
- L'état de la machine change
Les deux dernière étapes peuvent être remplacées par une étape "STOP" qui arrête toute exécution de la machine

En pratique, qu'est ce que ça donne ? Un petit exemple :
On part d'un ruban rempli de "0", de l'état 0, et on prend cette table d'action :

Étape 1 (état 0) : la tête est en position 0, elle lit "0". Elle va donc écrire "1", se déplacer à droite, et se mettre dans l'état 1
Étape 2 (état 1) : la tête est en position 1, elle lit "0". Elle écrit alors "1", se déplace à gauche, et revient en état 0.
Et ainsi de suite...

Rien de tel qu'une "vraie" machine de Turing pour voir ce que ce programme donne ;
Copiez-y ce programme :
0 . 1 x D
0 x 1 . D
1 . 0 x G
1 x 2 . D
2 . 0 x D
2 x 3 . =

On remarque alors que ce programme ne sert à rien, puisqu'il ne s'arrête jamais... Mais on peut tout à fait faire des programmes qui servent à quelque chose, c'est un langage de programmation comme un autre (peut-être juste un peu plus compliqué, mais pas plus limité... L'exemple du crible d'Érathostène est donné sur la page linkée). On pourrait, un jour de gros ennui, programmer Windows avec une machine de Turing...

Historiquement, la machine de Turing, concept de base de l'informatique théorique, a été inventée par Alan Turing bien avant l'invention de l'ordinateur. Elle servait alors à donner une définition d'un algorithme. Aujourd'hui, on s'en sert toujours en informatique théorique pour résoudre des problèmes de complexité ou de calculabilité.

Et cette histoire de castors, alors, qu'est ce que c'est ?
Un "castor affairé", c'est LA machine de Turing à n états et à 2 symboles ("0" et "1") qui est capable d'écrire le plus de "1" à partir d'un ruban rempli de "0", et qui s'arrête au bout d'un moment.
(Il faut imaginer tout un tas de castors occupés à grignoter des bandes selon leur ensemble de règles, et chercher le castor le plus bosseur parmis ceux-là...)

Par exemple, le castor affairé à 2 états est celui-ci :
0 . 1 x D
0 x 1 x G
1 . 0 x G
1 x 2 x =

Cette machine de Turing est capable d'écrire 4 "1", en 6 étapes.
Il est impossible de trouver une machine à 2 états et 2 symboles capable d'écrire encore plus de "1", et capable de s'arrêter seule.

Maintenant, vous pouvez tenter de trouver le castor affairé pour n=3, n=4 ou n=5... Enfin, ça, c'est ce que l'on peut penser, puisque trouver un castor affairé est quelque chose de très difficile.

Pour n=3, le castor écrira 6 "1", en 21 étapes :
0 . 1 x d
0 x 3 x d
1 . 1 x g
1 x 2 . d
2 . 2 x g
2 x 0 x g

Pour n=4, on peut trouver une machine qui peut en écrire 13, en 107 étapes :
0 . 1 x d
0 x 1 x g
1 . 0 x g
1 x 2 . g
2 . 4 x d
2 x 3 x g
3 . 3 x d
3 x 0 . d

Ces castors affairés permettent de définir la fonction de Radó et la fonction BB(n) :
Rado(n), ou Σ(n), désigne le plus grand nombre de 1 que l'on peut écrire avec une machine de Turing à n états
BB(n) (De "Busy Beaver", "Castor affairé" en anglais) ou S(n) donne le nombre d'étapes de la machine de Turing correspondant à Rado(n).
Les premiers termes sont dont :
Rado(0)=0
    BB(0)=0
Rado(1)=1
    BB(1)=1
Rado(2)=4
    BB(2)=6
Rado(3)=6
    BB(3)=21
Rado(4)=13
    BB(4)=107
A première vue, ces suites n'ont pas l'air de grandir si vite que ça, et pourtant...
Pour n=5, on ne connait pas les valeurs exactes, la seule chose que l'on sait, c'est que Rado(5)>4098 BB(5)>47 176 870, record trouvé en 1989 par Marxen et Buntrock, qui tient toujours.
Pour n=6, le record date de novembre 2007 (ce mois-ci, en fait), avec Rado(6)> 2.5 × 10⁸⁸¹ et BB(6)>8.9 × 10¹⁷⁶².
Il est improbable que l'on connaisse un jour la valeur exacte de BB(5) ou BB(6), sans parler de BB(7) ou de BB(100)...

 

La particularité de ces suites, c'est qu'elles ne sont pas calculables : on ne peut pas fabriquer d'algorithme permettant d'en avoir la valeur exacte.
De plus, ces suites croissent plus vite que n'importe quelles suites calculables, comme la suite des factorielles, des suites construites avec des puissance, avec la notation de Knuth ou celle de Conway. (Rappelez-vous)

 

Bref... La suite BB(n) permet à coup sûr de gagner au jeu du "Mon papa, c'est le plus fort !" !

---

Sources :
Historique de tous les records de castors affairés.
Wikipédia, avec la preuve de l'incalculabilité de Σ(n)

10 novembre 2007

Démystification de Fibonacci

Le nombre d'or ! 1,618 033 et des poussières, que l'on retrouverait dans l'architecture, la nature et tout ce qui est beau sur notre bonne vieille Terre.
La suite de Fibonacci ! 0,1,1,2,3,5,8,13,..., suite que l'on retrouve miraculeusement dans la nature, ses liens étroits avec le nombre d'or (le rapport de deux termes consécutifs de la suite de Fibonacci tend vers le nombre d'or)
Il est tant de détruire toute les mystifications qui peuvent roder autour de ce nombre et de cette suite !

(A noter que cet article a été essentiellement conçue pour que je mette toutes les démo nécéssaires à la compréhension totale de cette note, et n'est peut-être pas tout à fait faite pour être lue...)

---

La suite de Fibonacci, rappellons-le, est cette suite :
F(0)=0
F(1)=1
F(n+2)=F(n+1)+F(n)

Ce n'est qu'un cas particulier des suites récurrentes linéaires d'ordre 2, c'est à dire, les suites de type :
U(n+2)=a.U(n+1)+b.U(n)  (R)
(Avec a et b fixés, b de préférence non nul. Pour les besoins de la suite de cette note, a et b seront tous les deux positifs. C'est en fait une première généralisation des suites géométriques chères aux lycéens.)
Maintenant, ce qui serait parfait, ça serait de connaître le terme général de telles suites. Mon petit doigt (*) me dit qu'une suite de la forme pourrait remplir parfaitement le rôle.

r est donc une racine du polynôme du second degré X²-aX-b.
Son discriminant est a²+4b, positif, donc nos deux racines sont distinctes et réelles :

On peut remarquer que si deux suite u_n et v_n vérifient la relation (R), toute combinaisons linéaires (λ.u_n+µ.v_n) de ces deux suites fonctionneront.

Donc, une suite correspondant à la relation (R) et de type :

Maintenant, il n'y a plus qu'à trouver les coefficients λ et µ, que l'on peut trouver quand on connait les deux premiers termes de la suite qui nous intéresse.
Histoire de généraliser la suite de Fibonacci, on peut prendre u₀=0 et u₁=1.

Bref,

Avec a=b=1, on retrouve l'expression générale de la suite de Fibonacci (appelée formule de Binet), qui fait intervenir le nombre d'or (racine positive de X²-X-1) :

---

Deuxième mystère à résoudre : pourquoi donc le rapport de deux nombres consécutifs de la suite de Fibonacci tendent vers le nombre d'or ? Et bien, c'est pas trop compliqué à montrer :

(car r₂<r₁)

En prenant la suite de Fibonacci (a=b=1), on se retrouve sans problèmes avec le nombre d'or !

---

Il est tant de venir au cœur du problème : la suite de Fibonacci, le nombre 89 et les séries de Jj !

En effet, ma surprise fut énorme lorsqu'au gré de mes pérégrinations sur internet, je suis tombé sur ce résultat surprenant :

J'aurai pu en rester là, mais comme je suis né en 87 et non en 89, ce résultat ne me plaisait pas. Après avoir un peut tourné autour, j'ai trouvé qu'en changeant dans la formule la suite de Fibonacci par la suite de Fibonacci généralisée de paramètre a=1 et b=3, on tombait sur 1/87.
Et pour les gens nés en 86 ? pour ceux nés en 36 ? Et pour tous les autres ? Peut-on trouver une suite de Fibonacci généralisée qui fonctionne pour qui veut essayer ? Voilà pourquoi j'ai dû créer les séries de Jj !

Les séries de Jj, nommées ainsi en mon honneur (parce que j'ai passé une soirée dessus, et que j'ai pas vraiment cherché à savoir si quelqu'un avant moi avait déjà passé une soirée dessus) est cette série :

Mais ne vous avisez pas de prendre n'importe quel a et b, il faut se limiter aux cas 0≤a≤9 , 0≤b≤9.

* Démonstration du résultat :

* Pour démontrer que la série converge bien, rien ne vaut le critère d'Alembert :
La série converge ssi

Ce qui donne b<100-10a, qui correspond bien à 0≤a≤9 , 0≤b≤9.

---

La semaine prochaine, promis, un véritable article !

* Mon petit doigt : Wikipédia

03 novembre 2007

Les jeunes filles trottent dans les facs, et trouvent les maths débiles

Chapitre 7 : Jeux de mots incompréhensibles

* Un éléphant et son père se baladent dans la savane. L'un des deux est castré. Lequel ?
R : Le père car l'heureux père barrit sans trique.

* Qu'est-ce qui est jaune, normé et complet ?
R : Un espace de Bananach.

* Qu’est-ce que l’on obtient quand on cherche la primitive d’une fonction ascenseur ?
R : Une fonction en escalier...

* Comment savoir si une porcherie est complète ?
R : En étudiant une suite de cochon...

* Qu'est-ce qu'un Kinder Surprise sans jouet dedans ?
R : un Kinder injectif, car son noyau est réduit à zéro.

* Deux logiciens se rencontrent dans les couloirs de l'Université :
- Salut, comment ça va ?
- Très bien ! Ma femme vient tout juste d'accoucher !
- Ca alors ! C'est un garçon ou une fille ?
- Oui !

* Il ne faut pas traiter quelqu'un de compact, car un compact est un fermé borné.

* Deux mathématiciens prennent un verre dans un café et discutent du niveau exécrable de M. Toutlemonde en maths. L'un est plutôt optimiste, l'autre pessimiste. Bref, ils ne sont pas sur la même longueur d'onde. Le pessimiste s'éclipse pour aller aux toilettes, l'optimiste en profite pour appeler la serveuse et lui dit: "Quand mon collègue reviendra, je vous poserai une question et vous n'avez qu'à répondre "x au cube sur trois. Voilà 5 euros pour vous." La serveuse s'éloigne en répétant "x au cube sur trois, x au cube sur trois..." Le pessimiste revient et l'optimiste lui dit:"Pour te prouver que les gens ne sont pas nuls en maths, je te propose un pari : je vais poser une question à cette serveuse, et si elle répond juste, tu me devra 20 euros. Dans le cas contraire, c'est moi qui te devrai 20 euros." Le pessimiste et d'accord, et l'optimiste demande donc à la serveuse : "Quelle est la primitive de x au carré?" La serveuse, comme prévu, répond: "x au cube sur trois". Le pessimiste est évidemment épaté. La serveuse s'en va en faisant un clin d'œil à l'optimiste et en ajoutant : "Plus une constante".

02 novembre 2007

Elles réclament des chambres pour leurs maths

Chapitre 6 : Jeux de mots compréhensibles

Au cours du bal de fin d'année, une toute petite, toute timide, partie imaginaire, voir tout seul dans son coin une partie réelle, dont elle est secrètement amoureuse. Elle s'approche alors de lui, et lui demande.
" Tu viens danser ?"

*Qu'est-ce qu'un ours polaire ?
R : Un ours cartésien après un changement de coordonnées.

* Mon premier est un mammifère à queue plate qui ne peut pas s'asseoir.
Mon premier est un mammifère à queue plate qui ne peut pas s'asseoir.
Mon premier est un mammifère à queue plate qui ne peut pas s'asseoir.
Mon tout est le rapport de la circonférence au diamètre.
Qui suis-je ?
R : PI (3 castors sans chaise)

* Monsieur Dehun et Madame Egalzéro ont une fille. Comment l'appellent-ils ?
R : Hélène.

* Jésus vient de réunir ses apôtres pour ce qui sera son dernier repas. Tout d'un coup, il s'élève, et déclame à haute voix : "x²-x-2=0".
Le lendemain, Jésus est sûr sa croix, et l'un de ses apôtres s'approche de Jésus :
"Excuse-moi, Jésus, mais hier, on a pas bien compris ce que tu as voulu dire...
- Normal, c'est une parabole !"

* La vie est complexe : elle a une partie réelle et une partie imaginaire.

* Tout ce qui est hideux est négatif.

* π est irrationnel, et vous voulez que le monde tourne rond ?

* L'éléphant est énorme, mais le mammouth est n+1-orme.

01 novembre 2007

Les meilleures étudiantes préféraient qu'on leur change les maths

Chapitre 5 : Les ampoules

* Combien faut-il de mathématiciens pour changer une ampoule ?
R1 : Aucun. C'est laissé au lecteur en exercice.
R2 : Aucun. Un mathématicien ne peut pas changer une ampoule, mais il peut prouver que cela est faisable.
R3 : Un. Il la donne à un physicien et ramène ainsi le problème à un problème précédemment résolu.
R4 : La solution est triviale.
R5 : Un seul, une fois que vous avez réussi à lui présenter le problème dans des termes qu'il peut comprendre.

* Combien faut-il d'analystes numériques pour changer une ampoule ?
R : 3,9967 (après six itérations)

* Combien faut-il de mathématiciens constructivistes pour changer une ampoule ?
R : Aucun. Ils ne croient pas au rotations infinitésimales.

* Combien faut-il de géomètres classiques pour changer une ampoule ?
R : Aucun. Cela ne peut pas être fait à la règle et au compas.

* Combien faut-il d'analystes pour changer une ampoule ?
R : Trois. Un pour prouver l'existence, un pour prouver l'unicité et un pour déterminer les conditions initiales.

* Combien faut-il de Bourbakistes pour changer une ampoule ?
R : Changer une ampoule est un cas particulier d'un problème plus général concernant l'entretien et la réparation d'un système électrique.
Pour déterminer un minorant et un majorant du nombre de personnes nécessaires, nous devons vérifier si les conditions du lemme 2.1 (disponibilité du personnel) et ceux du corollaire 2.3.55 (motivation du personnel) sont vérifiées.
Si et seulement si ces conditions sont réunies, on obtient le résultat en appliquant le théorème de la section 3.11.23.
Le majorant obtenu est, bien sûr, à prendre en compte dans un espace mesuré, muni de la topologie *-faible.